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

}