LeetCode:991. Broken Calculator

此文为LeetCode 991. Broken Calculator的题解。

题意

有一台坏掉的计算器,能够显示一个数字,我们可以对这个数字做两个操作:

  • 二: 将显示的数字乘以2, 或者;
  • 减一: 将显示的数字减1.

初始时,计算器显示数字 X.

返回要得到数字Y需要的最小操作次数。

题解

如果X>Y,则只能执行减一操作。否则,如果Y是奇数,则上一步操作一定是X减一;如果Y是偶数,则上一步操作只能是X乘二

只需要通过上述规则,由Y反推X即可。

代码

/**
 * https://www.robberphex.com/broken-calculator/
 * Runtime: 0 ms, faster than 100.00% of Java online submissions for Broken Calculator.
 * Memory Usage: 33 MB, less than 8.71% of Java online submissions for Broken Calculator.
 */
class Solution {
    public int brokenCalc(int X, int Y) {
        int res = 0;
        // 如果X<Y,则只能-1,故直接走return句
        while (X < Y) {
            if (Y % 2 == 1) {
                Y += 1;
            } else {
                Y /= 2;
            }
            res++;
        }
        return res + X - Y;
    }

    public static void main(String[] args) {
        int res = new Solution().brokenCalc(2, 3);
        System.out.println(res);
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.