Medium

题目描述

你正在玩一个整数游戏。你从整数 1 开始，想要达到整数 target。

在一次移动中，你可以：

  • 将当前整数加一（即 x = x + 1）
  • 将当前整数翻倍（即 x = 2 * x）

你可以使用加一操作任意次数，但是你最多只能使用翻倍操作 maxDoubles 次。

给定两个整数 target 和 maxDoubles，返回从 1 开始达到 target 所需的最小移动次数。

示例 1：

输入：target = 5, maxDoubles = 0
输出：4
解释：持续加一直到达到目标值。

示例 2：

输入：target = 19, maxDoubles = 2
输出：7
解释：初始时，x = 1
加一 3 次，x = 4
翻倍一次，x = 8
加一一次，x = 9
再翻倍一次，x = 18
加一一次，x = 19

示例 3：

输入：target = 10, maxDoubles = 4
输出：4
解释：初始时，x = 1
加一一次，x = 2
翻倍一次，x = 4
加一一次，x = 5
再翻倍一次，x = 10

约束条件：

  • 1 <= target <= 10^9
  • 0 <= maxDoubles <= 100

解题思路

这道题的关键是逆向思考：从目标值开始，逐步减少到1，这样更容易找到最优策略。

核心思路

  1. 逆向操作：从 target 开始，执行相反的操作回到 1

    • 加一的逆操作是减一
    • 翻倍的逆操作是除以2（仅当数字为偶数时）

  2. 贪心策略：优先使用除法操作，因为：

    • 除法能够更快地减少数字大小
    • 当 maxDoubles > 0 且当前数字为偶数时，除以2比减一更优

  3. 算法流程：

    • 如果当前数字为偶数且还有除法次数，执行除法
    • 否则执行减一操作
    • 直到数字变为1

  4. 边界处理：

    • 当 maxDoubles = 0 时，只能执行减一操作
    • 当数字为奇数时，必须先减一使其变为偶数

这种贪心策略是正确的，因为除法操作的效果远大于减一操作，应该尽可能多地使用。

代码实现

class Solution {
public:
    int minMoves(int target, int maxDoubles) {
        int moves = 0;
        
        while (target > 1) {
            if (maxDoubles > 0 && target % 2 == 0) {
                target /= 2;
                maxDoubles--;
            } else {
                target--;
            }
            moves++;
        }
        
        return moves;
    }
};

class Solution:
    def minMoves(self, target: int, maxDoubles: int) -> int:
        moves = 0
        
        while target > 1:
            if maxDoubles > 0 and target % 2 == 0:
                target //= 2
                maxDoubles -= 1
            else:
                target -= 1
            moves += 1
        
        return moves

public class Solution {
    public int MinMoves(int target, int maxDoubles) {
        int moves = 0;
        
        while (target > 1) {
            if (maxDoubles > 0 && target % 2 == 0) {
                target /= 2;
                maxDoubles--;
            } else {
                target--;
            }
            moves++;
        }
        
        return moves;
    }
}

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

复杂度分析

复杂度类型复杂度说明
时间复杂度O(log target + maxDoubles)每次除法操作将target减半，最多执行maxDoubles次；减一操作最多执行target-1次，但由于除法的存在，实际执行次数远小于此
空间复杂度O(1)只使用常数级别的额外空间

相关题目