貪心算法 壞了的計算器

題目

難度：簡單

在顯示著數(shù)字的壞計算器上，我們可以執(zhí)行以下兩種操作：

雙倍（Double）：將顯示屏上的數(shù)字乘 2； 遞減（Decrement）：將顯示屏上的數(shù)字減 1 。

最初，計算器顯示數(shù)字 X。

返回顯示數(shù)字 Y 所需的最小操作數(shù)。

示例 1：

輸入：X = 2, Y = 3
輸出：2
解釋：先進(jìn)行雙倍運算，然后再進(jìn)行遞減運算 {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
解釋：執(zhí)行遞減運算 1023 次

提示：

1 <= X <= 10^9 1 <= Y <= 10^9

題解一

為什么這道題采用逆向思維更優(yōu)？

1.剛開始的時候覺得很簡單，用了兩個while，結(jié)果報錯了。因為可以先減去再去乘以就會節(jié)省次數(shù)

正向思維：在X/Y時要實現(xiàn)操作數(shù)最小，要將X逼近Y的1/2值或1/4值或1/8值或...再進(jìn)行*2操作，難點在于要判斷要逼近的是1/2值還是1/4值還是其他值，邏輯復(fù)雜 逆向思維：在Y>X時Y只管/2，到了Y\<X時在+1逼近 說白了就是，正向思維采用的是先小跨度的-1操作，再大跨度的*2操作；逆向思維采用的是先大跨度的/2操作，再小跨度的-1操作 然而事實上往往是先大后小的解決問題思維在實現(xiàn)起來會比較簡單 cur=y;存儲yn=0;次數(shù)

2.什么時候可以先減去再去乘以？Y是一個偶數(shù) 3.所以先把cur+1成為偶數(shù) 4.再/2處理，小于X之后跳出循環(huán) 5.這時候n+x-cur即為結(jié)果x-cur為x與cur之間還需要進(jìn)行的幾次操作

class Solution {
    public int brokenCalc(int X, int Y) {
        int cur=Y,n=0;
        while(X<cur){
            n++;
            if(cur%2==1){
                cur++;
            }
            else{
                cur/=2;
            }
        }




        return n+X-cur;
    }
}

解法二：遞歸

class Solution {
    public int brokenCalc(int X, int Y) {
        if (X >= Y) {
            return X - Y;
        }


        if (Y % 2 == 1) {
            return 2 + brokenCalc(X, (Y + 1) / 2);
        } else {
            return 1 + brokenCalc(X, Y / 2);
        }
    }
}

解法三：分步

只需要討論 Y > X時的情況。分為兩步統(tǒng)計， cnt1為多少個乘法，cnt2為多少個減法。 顯然我們必須把 X 乘到恰好比 Y 大的數(shù)，否則再怎么減也達(dá)不到要求……因此先求 cnt1. 那么，關(guān)鍵是 cnt2 怎么求呢？我們假設(shè)減法穿插在各個乘法之間，如果在第一次乘法前減，那么最終等價于減去 2cnt12^{cnt1}2cnt1, 如果在第二次乘法前減，最終等價于減去 2cnt1?12^{cnt1 - 1}2cnt1?1，以此類推。由于每次可以減多個1，因此最終要乘個系數(shù)，減了 a 2cnt12^{cnt1}2cnt1 + b 2cnt1?12^{cnt1 - 1}2cnt1?1 + .... 那么這個系數(shù) a,b,c等等是多少呢，貪心即可，a越大越好，其次到b, c...

class Solution {
    public int brokenCalc(int X, int Y) {
        if (Y <= X) return X - Y;
        int cnt1 = 0;
        while (X < Y) {
            X *= 2;
            cnt1 ++;
        }
        if (X == Y) return cnt1;
        int r = X - Y;
        int cnt2 = 0;
        for (int i = cnt1; i >= 0; i --) {
            int t = (int)Math.pow(2, i);
            int coeff = r / t;
            r = r % t;
            cnt2 += coeff;
            if (r == 0) break;
        }
        return cnt1 + cnt2;
    }
}