LeetCode 991. 坏了的计算器
目录
题目描述
题意分析
屏幕上显示着一个数
startValue，只有两个按钮可用：一个把当前数乘以二，一个把当前数减去一。问最少按多少次按钮，能让屏幕显示target。注意两个操作是不对称的：乘二只能让数变大（起始值为正），减一只能让数变小一格。所以要把小数变大只能靠乘二，而乘二的步长又是成倍的，很容易一下子跳过目标，此时又得用一连串减一往回蹭——什么时候乘、什么时候减，正是这道题的全部难点。
约束信号：两个数都能到 $10^9$。这个范围直接封死了在数值空间上做广度优先搜索的路子，状态数太多。最少操作数本身甚至可能接近 $10^9$——例如从 $10^9$ 减到 $1$；但这段连续减一可以直接用差值计算。真正需要选择操作的
target > startValue情形，则提示存在不断折半的对数级构造。边界要点清楚：
startValue可能已经大于或等于target，此时乘二只会让差距更大，唯一的办法是一路减一，答案就是两者之差；target也可能恰好等于startValue，答案为 0。
解法：逆向贪心
核心思路
正着做很难下手。从
startValue出发，每一步都有两个分支，而且乘二会让数越来越大、减一会让数越来越小，状态空间在正方向上根本没有上界，无法界定搜索范围，也说不清什么时候该停止乘二。换个方向就豁然开朗：把两个操作反过来，从
target走回startValue。「乘二」的逆操作是「除以二」，「减一」的逆操作是「加一」。逆向之后，最关键的性质出现了——分支消失了：其一，若当前的
target是奇数，它绝不可能是上一步乘二得到的（乘二的结果必为偶数），所以正向的上一步只能是减一，逆向就只能加一。这里没有选择余地。其二，若当前的
target是偶数且仍大于startValue，那么除以二严格不劣于加一。证明如下：任何把target降到startValue的逆向方案中，至少要用一次除法（只加不除只会越来越大）。设第一次除法之前先做了 $k$ 次加一，那么代价是 $k+1$，结果是 $\frac{t+k}{2}$，而且为了能整除，$k$ 必须是偶数。换个顺序：先除一次再加 $\frac{k}{2}$ 次，代价是 $1+\frac{k}{2}$，结果同样是 $\frac{t}{2}+\frac{k}{2}=\frac{t+k}{2}$。两者结果完全相同，但当 $k>0$ 时 $1+\frac{k}{2} < k+1$，先除严格更省。所以偶数时闭着眼睛除就行。其三，一旦
target降到不大于startValue，逆向就只剩加一可用（除以二只会让它更小，越走越远）。此时还差startValue - target，就补这么多次加一。于是维持这条不变量：循环的每一轮，当前的
target值都是「从startValue出发按已计数的操作次数所能到达的、通往最优解的中间值」，且每一步的选择要么唯一、要么已被证明不劣。 既然每一步都不存在更优的替代选择，贪心走完得到的总步数就是最小值。复杂度也随之明朗：奇数一步之后必然变偶数，偶数一步就折半，所以每两步至少让
target减半，总轮数是对数级。
解题步骤
- 初始化操作计数
ops = 0，进入while (target > startValue)循环。为什么循环条件是严格大于：只有当目标还在起点上方时，逆向才需要用到除法把它降下来；一旦不大于起点，后续操作完全确定，用一个减法算完即可，不必再循环。- 若
target是奇数，令target++，计数加一。为什么只能加一：奇数不可能由乘二产生，正向的最后一步必定是减一，逆向别无选择。- 若
target是偶数，令target折半，计数加一。为什么不考虑先加再除：前面的交换论证表明，把加一挪到除法之后做，结果相同而代价更小，所以最优解里绝不会出现「偶数时先加一」。- 循环结束后返回
ops + (startValue - target)。为什么补的是差值：此时target已经不大于startValue，逆向只剩加一可用，需要加startValue - target次；对应到正向，就是从startValue开始先做这么多次减一。注意target可能在最后一次折半时跌到startValue以下，这个差值可能大于 0，不能想当然认为它是 0。以
startValue = 3、target = 10走一遍：初始ops = 0。第一轮，$10 > 3$ 进入循环，10 是偶数，折半得 5，ops = 1。第二轮，$5 > 3$，5 是奇数，加一得 6，ops = 2。第三轮，$6 > 3$，6 是偶数，折半得 3，ops = 3。第四轮判断 $3 > 3$ 不成立，退出循环。返回 $3 + (3-3) = 3$。把这条路径翻回正向读：$3 \xrightarrow{\times 2} 6 \xrightarrow{-1} 5 \xrightarrow{\times 2} 10$，恰好三步，且可以验证两步做不到（两步最多只能到 $3\times2\times2=12$、$3\times2-1=5$、$(3-1)\times2=4$、$3-2=1$，都不是 10）。再走一组会用到最后那个差值的
startValue = 5、target = 8：ops = 0，$8>5$ 且 8 是偶数，折半得 4，ops = 1；此时 $4 > 5$ 不成立，退出循环。返回 $1 + (5-4) = 2$。正向读作 $5 \xrightarrow{-1} 4 \xrightarrow{\times 2} 8$，两步完成。若忘了补上这个差值 1，就会错答成 1。
代码实现
// 若 target 为奇数，只能 +1。
class Solution {
public int brokenCalc(int startValue, int target) {
int ops = 0;
while (target > startValue) {
if ((target & 1) == 1) {
target++;
} else {
target >>= 1;
}
ops++;
}
return ops + (startValue - target);
}
}
// 若 target 为奇数，只能 +1。
func brokenCalc(startValue int, target int) int {
ops := 0
for target > startValue {
if target%2 == 1 {
target++
} else {
target /= 2
}
ops++
}
return ops + (startValue - target)
}
复杂度分析
- 时间复杂度：当
target > startValue时是 $O(\log target)$，因为每一到两轮至少会发生一次折半；当target <= startValue时是 $O(1)$。最后的startValue - target只做一次算术计算，并没有逐次模拟这些操作。- 空间复杂度：$O(1)$，全程只维护当前
target和操作数ops。
关键点总结
- 正向的“乘 2 / 减 1”不好选择，逆向后变成“偶数除 2 / 加 1”，奇偶性会强迫下一步，贪心选择因此是确定的。
- 当
target > startValue且为偶数时直接折半；为奇数时必须先加一把它变成偶数。- 一旦
target <= startValue，逆向只剩连续加一，次数可直接用startValue - target计算，无需模拟。- 面试时应主动给出交换论证：偶数目标若先加一，会变成奇数而无法除二；任何多余的加一都不会优于立刻折半。
易错点总结
- 从
startValue正向贪心：例如startValue = 5, target = 8，先乘二到 10 再减两次共 3 步并不是最优；最优是先减到 4，再乘二到 8，只要 2 步。正向的局部规则很难证明，逆向选择才由奇偶性唯一决定。- 奇数目标直接除以 2：整数除法会丢失信息。
target = 9的逆向第一步只能是+1到 10，再除以 2；直接变成 4 对应不到任何合法正向操作。- 循环条件写成
target != startValue：当最后一次除法把目标降到起点以下时会继续错误折半甚至死循环；应在target <= startValue时一次性补差值。- 忘记给奇数的
+1计数：startValue = 3, target = 10应走10 -> 5 -> 6 -> 3共 3 步，漏计会答成 2。
相似题目
| 题目 | 难度 | 与本题的联系 |
|---|---|---|
| 397. 整数替换 | 中等 | 同样依据奇偶性逆向缩小整数，但奇数时有两个候选 |
| 1342. 将数字变成 0 的操作次数 | 简单 | 奇偶性直接决定操作，可练习按位分析 |
| 1658. 将 x 减到 0 的最小操作数 | 中等 | 也通过等价变换降低选择难度，但转化为最长子数组问题 |