class Solution {
public:
int minMoves(int target, int maxDoubles) {
}
};
2139. 得到目标值的最少行动次数
你正在玩一个整数游戏。从整数 1 开始，期望得到整数 target 。
在一次行动中，你可以做下述两种操作之一：
x = x + 1）。x = 2 * x）。在整个游戏过程中，你可以使用 递增 操作 任意 次数。但是只能使用 加倍 操作 至多 maxDoubles 次。
给你两个整数 target 和 maxDoubles ，返回从 1 开始得到 target 需要的最少行动次数。
示例 1：
输入：target = 5, maxDoubles = 0 输出：4 解释：一直递增 1 直到得到 target 。
示例 2：
输入：target = 19, maxDoubles = 2 输出：7 解释：最初，x = 1 。 递增 3 次，x = 4 。 加倍 1 次，x = 8 。 递增 1 次，x = 9 。 加倍 1 次，x = 18 。 递增 1 次，x = 19 。
示例 3：
输入：target = 10, maxDoubles = 4 输出：4 解释： 最初，x = 1 。 递增 1 次，x = 2 。 加倍 1 次，x = 4 。 递增 1 次，x = 5 。 加倍 1 次，x = 10 。
提示：
1 <= target <= 1090 <= maxDoubles <= 100原站题解
cpp 解法, 执行用时: 4 ms, 内存消耗: 5.8 MB, 提交时间: 2023-05-05 17:24:05
class Solution {
public:
int minMoves(int target, int maxDoubles) {
int ans = 0;
while (maxDoubles && target != 1) {
++ans;
if (target % 2 == 1) {
--target;
}
else {
--maxDoubles;
target /= 2;
}
}
ans += (target - 1);
return ans;
}
};
python3 解法, 执行用时: 44 ms, 内存消耗: 15.8 MB, 提交时间: 2023-05-05 17:23:46
# 反向操作+贪心
class Solution:
def minMoves(self, target: int, maxDoubles: int) -> int:
ans = 0
while maxDoubles and target != 1:
ans += 1
if target % 2 == 1:
target -= 1
else:
maxDoubles -= 1
target //= 2
ans += (target - 1)
return ans
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-05-05 17:21:37
// 加倍留在数字更大的时候
func minMoves(v, maxDoubles int) (ans int) {
for v > 1 {
if maxDoubles == 0 {
return ans + v - 1
}
if v%2 > 0 {
v--
ans++
}
maxDoubles--
v /= 2
ans++
}
return
}