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

}

LeetCode:991. Broken Calculator

https://www.robberphex.com/broken-calculator/

作者

Robert Lu

发布于

2019-06-30

许可协议

评论