class Solution {
public:
int brokenCalc(int startValue, int target) {
}
};
991. 坏了的计算器
在显示着数字 startValue
的坏计算器上,我们可以执行以下两种操作:
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 <= x, y <= 109
相似题目
原站题解
java 解法, 执行用时: 0 ms, 内存消耗: 38.7 MB, 提交时间: 2022-12-14 12:51:56
class Solution { public int brokenCalc(int X, int Y) { if (Y <= X) return X-Y; if (Y % 2 == 0) return 1 + brokenCalc(X, Y/2); else return 1 + brokenCalc(X, Y+1); } }
java 解法, 执行用时: 0 ms, 内存消耗: 38.5 MB, 提交时间: 2022-12-14 12:50:28
class Solution { public int brokenCalc(int startValue, int target) { int operations = 0; while (startValue < target) { if (target % 2 != 0) { target++; } else { target /= 2; } operations++; } operations += startValue - target; return operations; } }
python3 解法, 执行用时: 32 ms, 内存消耗: 14.9 MB, 提交时间: 2022-12-14 12:49:38
''' 逆向思维,除了对 startValue 执行乘 2 或 减 1 操作之外,我们也可以对 target 执行除 2(当 target 是偶数时)或者加 1 操作。 ''' class Solution: def brokenCalc(self, startValue: int, target: int) -> int: ans = 0 while target > startValue: ans += 1 if target % 2 == 1: target += 1 else: target //= 2 return ans + startValue - target
java 解法, 执行用时: 0 ms, 内存消耗: 38.5 MB, 提交时间: 2022-12-14 12:46:54
class Solution { public int brokenCalc(int X, int Y) { int ans = 0; while (Y > X) { ans++; if (Y % 2 == 1) Y++; else Y /= 2; } return ans + X - Y; } }