Medium

题目描述

有一台坏掉的计算器，在其显示屏上初始显示整数 startValue。在一次操作中，你可以：

  • 将显示屏上的数字乘以 2，或者
  • 将显示屏上的数字减去 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 <= 10^9

解题思路

这是一个贪心算法问题。关键观察是我们需要反向思考：从 target 开始逆推到 startValue。

核心思路：

  1. 当 startValue >= target 时，我们只能使用减法操作，需要 startValue - target 次操作。

  2. 当 startValue < target 时，我们从 target 开始反向操作：

    • 如果当前数字是偶数，我们除以 2（对应正向的乘以 2）
    • 如果当前数字是奇数，我们加 1 然后除以 2（对应正向的先减 1 再乘以 2）

为什么这样贪心是最优的？

  • 乘法操作能够快速增大数值，所以我们尽量使用乘法
  • 当 target 是奇数时，我们无法通过乘以 2 得到，所以必须先通过加 1 变成偶数
  • 反向思考避免了复杂的分支判断，每一步都是确定性的最优选择

这种反向贪心策略保证了操作次数最少，时间复杂度为 O(log target)。

代码实现

class Solution {
public:
    int brokenCalc(int startValue, int target) {
        int operations = 0;
        
        while (target != startValue) {
            if (target < startValue) {
                operations += startValue - target;
                break;
            }
            
            if (target % 2 == 0) {
                target /= 2;
            } else {
                target += 1;
            }
            operations++;
        }
        
        return operations;
    }
};

class Solution:
    def brokenCalc(self, startValue: int, target: int) -> int:
        operations = 0
        
        while target != startValue:
            if target < startValue:
                operations += startValue - target
                break
            
            if target % 2 == 0:
                target //= 2
            else:
                target += 1
            operations += 1
        
        return operations

public class Solution {
    public int BrokenCalc(int startValue, int target) {
        int operations = 0;
        
        while (target != startValue) {
            if (target < startValue) {
                operations += startValue - target;
                break;
            }
            
            if (target % 2 == 0) {
                target /= 2;
            } else {
                target += 1;
            }
            operations++;
        }
        
        return operations;
    }
}

var brokenCalc = function(startValue, target) {
    if (startValue >= target) {
        return startValue - target;
    }
    
    let operations = 0;
    
    while (target > startValue) {
        if (target % 2 === 0) {
            target = target / 2;
        } else {
            target = target + 1;
        }
        operations++;
    }
    
    return operations + startValue - target;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(log target) - 每次操作都会将 target 减半（平均情况）
空间复杂度O(1) - 只使用常数额外空间

相关题目