这道题是LeetCode里的第991道题。
题目描述:
在显示着数字的坏计算器上,我们可以执行以下两种操作:
- 双倍(Double):将显示屏上的数字乘 2;
- 递减(Decrement):将显示屏上的数字减 1 。
最初,计算器显示数字
X
。返回显示数字
Y
所需的最小操作数。
示例 1:
输入:X = 2, Y = 3输出:2解释:先进行双倍运算,然后再进行递减运算 {2 -> 4 -> 3}.示例 2:
输入:X = 5, Y = 8输出:2解释:先递减,再双倍 {5 -> 4 -> 8}.示例 3:
输入:X = 3, Y = 10输出:3解释:先双倍,然后递减,再双倍 {3 -> 6 -> 5 -> 10}.示例 4:
输入:X = 1024, Y = 1输出:1023解释:执行递减运算 1023 次
如果这道题你是硬算的话 (由 X 到 Y),那我得佩服你,因为直接从正面硬算的话需要考虑的条件很多原因在于有乘 2 这个操作,我们不知道什么时候乘 2 才合适。这里我使用的是逆向思维(由 Y 到 X),逻辑就简单多了,因为对于 Y 来说,它要除 2,就必须是偶数。否则递增。
通过除 2,使 Y 不断的逼近 X。对于偶数,除 2 操作,不管怎么样,肯定比递增 Y 好。
解题代码:
class Solution { public int brokenCalc(int X, int Y) { if(X>Y)return X-Y; int res=0; while(X
提交结果:
个人总结:
这道题是一道贪心题,正面计算的算法肯定有。在这里我想说的是我自己的代码,最后的返回值我的并不是 " return res+X-Y; " 而是 " return res; ",while 循环条件我的也并不是 " X<Y " 而是 " X!=Y ",还有中间的 if 判断条件,我这样改算是优化了一下代码,缩短了计算的时间。