【贪心】leetcode991. Broken Calculator

991. Broken Calculator

There is a broken calculator that has the integer startValue on its display initially. In one operation, you can:

multiply the number on display by 2, or
subtract 1 from the number on display.
Given two integers startValue and target, return the minimum number of operations needed to display target on the calculator.

题意：x可以进行乘以2操作和减1操作，求x变为y的最少操作次数

思路：贪心

可以逆向考虑：y可以进行加1操作，或者除以 2的操作（y是偶数的情况下）

可以证明：当y是偶数的情况下，除以2所得的操作次数一定比加1 的操作次数小

 

所以，当y是奇数的情况下，y只能加1；当y是偶数的情况下，y只能除以2

当y小于x时，只能进行加1操作。

时间复杂度O（logY）

class Solution {
    public int brokenCalc(int x, int y) {
        int res=0;
        while(y>x){
            if(y%2==1){
               y++;
            }else{
                y/=2;
            }
            res++;
        }
        return res+x-y;
   } 
}