2139. 得到目标值的最少行动次数

Alex_Shen
2022-03-29 / 0 评论 / 0 点赞 / 122 阅读 / 521 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-03-31,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

你正在玩一个整数游戏。从整数 1 开始,期望得到整数 target 。

在一次行动中,你可以做下述两种操作之一:

递增,将当前整数的值加 1(即, x = x + 1)。
加倍,使当前整数的值翻倍(即,x = 2 * x)。
在整个游戏过程中,你可以使用 递增 操作 任意 次数。但是只能使用 加倍 操作 至多 maxDoubles 次。

给你两个整数 target 和 maxDoubles ,返回从 1 开始得到 target 需要的最少行动次数。

示例 1:

输入:target = 5, maxDoubles = 0
输出:4
解释:一直递增 1 直到得到 target 。

思路:

反向计算,如果可以除以2就除以2,否则减一。

如果除以二操作次数剩余0次,直接加上target(全是减一操作)

代码:

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

评论区