LeetCode 题解工作台
坏了的计算器
在显示着数字 startValue 的坏计算器上，我们可以执行以下两种操作： 双倍（Double）： 将显示屏上的数字乘 2； 递减（Decrement）： 将显示屏上的数字减 1 。 给定两个整数 startValue 和 target 。返回显示数字 target 所需的最小操作数。 示例 1：…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
我们可以采用逆向计算的方式，从 开始，如果 是奇数，那么 $\textit{target} = \textit{target} + 1$，否则 $\textit{target} = \textit{target} / 2$，累加操作次数，直到 $\textit{target} \leq \textit{startValue}$，此时的操作次数加上 $\textit{startValue} - …
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
在显示着数字 startValue 的坏计算器上，我们可以执行以下两种操作：
- 双倍（Double）：将显示屏上的数字乘 2；
- 递减（Decrement）：将显示屏上的数字减
1。
给定两个整数 startValue 和 target 。返回显示数字 target 所需的最小操作数。
示例 1：
输入：startValue = 2, target = 3
输出：2
解释：先进行双倍运算，然后再进行递减运算 {2 -> 4 -> 3}.
示例 2：
输入：startValue = 5, target = 8
输出：2
解释：先递减，再双倍 {5 -> 4 -> 8}.
示例 3：
输入：startValue = 3, target = 10
输出：3
解释：先双倍，然后递减，再双倍 {3 -> 6 -> 5 -> 10}.
提示：
1 <= startValue, target <= 109
解题思路
方法一：逆向计算
我们可以采用逆向计算的方式，从 开始，如果 是奇数，那么 ，否则 ，累加操作次数，直到 ，此时的操作次数加上 即为最终结果。
时间复杂度 ，其中 为 。空间复杂度 。
class Solution:
def brokenCalc(self, startValue: int, target: int) -> int:
ans = 0
while startValue < target:
if target & 1:
target += 1
else:
target >>= 1
ans += 1
ans += startValue - target
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(\log target) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Checks if you can apply a greedy strategy in reverse to minimize operations.
- question_mark
Wants validation of invariants at each step to ensure correctness.
- question_mark
Assesses understanding of O(log target) efficiency for large input ranges.
常见陷阱
外企场景- error
Trying to move forward greedily can overshoot the target and increase operations.
- error
Failing to handle odd targets properly when halving in reverse.
- error
Overcomplicating with unnecessary data structures instead of counting operations directly.
进阶变体
外企场景- arrow_right_alt
Allow an additional multiply by 3 operation and analyze how the greedy pattern changes.
- arrow_right_alt
Compute minimal operations for a range of targets from a fixed startValue.
- arrow_right_alt
Introduce negative numbers as targets and adjust the greedy invariant for decrementing.