LeetCode991. Broken Calculator

1、题目链接

https://leetcode.com/problems/broken-calculator/

2、解题思路

题目意思是说有一个坏了的计算器，你只能做两种计算：

(1)、每次乘2

(2)、每次减1

然后给你两个数字X，Y，让你使用计算器将X变成Y的最小次数

不知道有没有看出来这道题是一个比较经典的贪心问题，我们来分析一下，正常来说如果X比Y还大，那么我们就只能使用(2)来达到最终的结果；如果X比Y小，那么我们如果每次都乘2的话，可能本来X就比较接近Y的，但是2倍之后就很大了，就拿题目中的例子来说，加入X=3，Y=10，如果X做2次乘法到12的话，需要再做两次减法，但是如果你先做1次乘法到6，再做一次减法到5，最后再做1次乘法到10就可以了，所以我们正面直接从小到大是不太好操作的，所以这里我们如果是逆向操作，当X比Y小的话，每次做除法或着加法；当X比Y大的话直接返回Y-X，于是就有了：

3、代码

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

4、结果

QQ20190710-185815@2x.png