列表

详情


991. 坏了的计算器

在显示着数字 startValue 的坏计算器上,我们可以执行以下两种操作:

给定两个整数 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}.

 

提示:

相似题目

只有两个键的键盘

原站题解

去查看

上次编辑到这里,代码来自缓存 点击恢复默认模板
class Solution { public: int brokenCalc(int startValue, int target) { } };

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;
    }
}

上一题