LeetCode 991. 坏了的计算器

约 4 分钟
文章信息 7 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 微软 百度
标签
数学 贪心

题目描述

✅ 991. 坏了的计算器

image-20260928225458447

image-20260928225458448

题意分析

从正整数 startValue 出发，每次只能乘 2 或减 1，求到达 target 的最少操作数。把操作顺序倒过来，就等价于从 target 回到 startValue：乘 2 的逆操作是偶数除以 2，减 1 的逆操作是加 1，路径长度不变。

解法：逆向贪心

核心思路

[!blue]

设当前逆向数值为 target。当它大于起点时，最终必须让数值下降，不能一直加 1。若它是奇数，除以 2 不合法，因此第一步只能加 1，将它变成偶数。

若它是偶数，立即除以 2 不会错过更优解。任何先增加再除以 2 的方案，在第一次除法之前必须增加偶数次，设为 2r 次，之后到达 (target + 2r) / 2。改成先除以 2、再增加 r 次，仍到达同一数值，却把这部分操作从 2r + 1 次降为 r + 1 次。所以可以把除法提前，选择立即减半。

当 target <= startValue 时，已经需要把数值向上补到起点。每次加 1 最多补一单位，而除以 2 只会让差距更大，因此至少需要 startValue - target 次加法，直接连续加 1 恰好达到这个下界。

循环只处理目标较大的部分，记录已执行的逆操作次数 ops；结束后一次加上剩余差值，即为原问题的最少操作数。

解题步骤

  • 初始化 ops = 0，当 target > startValue 时继续循环。
  • 当前目标为奇数则加 1，为偶数则除以 2；每执行一个逆操作，ops 加 1。
  • 目标降到不大于起点后停止，返回 ops + startValue - target。
  • 若起初目标已经不大于起点，循环不会执行；两者相等时答案为 0。

代码实现

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);
    }
}

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)
}

复杂度分析

  • 时间复杂度：$O(\log(target+1))$ 上界。循环中偶数一步减半，奇数至多两步变为原值的一半向上取整；目标起初不大于起点时为 $O(1)$。
  • 空间复杂度：$O(1)$。只维护当前目标和操作次数。

关键点总结

[!green]

  • 逆向操作与正向操作逐一对应，最短路径长度保持不变。
  • 奇数加 1 是唯一合法的第一步；偶数立即除以 2 由操作交换证明最优。
  • 目标不大于起点后，直接补差值就是最优解，不再继续套用奇偶分支。

易错点总结

[!yellow]

  • 奇数加 1 后再除以 2 是两次操作，不能只记一次。
  • 奇数直接使用整数除法不对应合法逆操作，会丢掉必要的加 1。
  • 结束条件是目标不大于起点，而非必须完全相等；低于起点时要补上剩余差值。
  • 正向只要能乘 2 就优先乘 2 缺少上述最优性保证，不能直接照搬逆向规则。

相似题目

题目 难度 关联与区别
397. 整数替换 中等 同样反向处理倍增可减少分支，本题逆操作为除2或加1，原题整数替换还允许两种奇数调整。
2139. 得到目标值的最少行动次数 中等 同样从目标反推并尽量利用除2，原题额外限制倍增次数。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/77741792
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！