【力扣题解】2139. 得到目标值的最少行动次数

😊博主目前也在学习，有错误欢迎指正😊
🌈保持热爱 奔赴星海🌈

一、题目

1、题目描述

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

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

• 递增，将当前整数的值加 1（即， x = x + 1）。
• 加倍，使当前整数的值翻倍（即，x = 2 * x）。
  在整个游戏过程中，你可以使用 递增 操作 任意 次数。但是只能使用 加倍 操作 至多 maxDoubles 次。
  给你两个整数 target 和 maxDoubles ，返回从 1 开始得到 target 需要的最少行动次数。

2、基础框架

• Java版本框架代码如下：

class Solution {
    public int minMoves(int target, int maxDoubles) {
        
    }
}
1
2
3
4
5

3、原题链接

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

二、解题报告

1、思路分析

       (1)当maxDoubles为零时，直接返回target - 1即可，因为target只能通过累加获得。
       (2)当maxDoubles大于零时，每次都把target除以二，若target为奇数，说明获取到target需要翻倍后再加一，所以res需要加二，若target为偶数，说明获取到target直接翻倍即可。每次计算maxDoubles减一，target除以二。直到target为一或者maxDoubles为零即可。
       (3)若maxDoubles为零时target仍然大于一，说明得到target只能通过累加的方法得到，所以循环结束后热死加上target - 1；

2、代码详解

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

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

三、本题知识

数学推断