貪心算法 壞了的計(jì)算器

題目

難度：簡(jiǎn)單

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

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

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

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

示例 1：

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

提示：

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

題解一

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

1.剛開始的時(shí)候覺得很簡(jiǎn)單，用了兩個(gè)while，結(jié)果報(bào)錯(cuò)了。因?yàn)榭梢韵葴p去再去乘以就會(huì)節(jié)省次數(shù)

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

2.什么時(shí)候可以先減去再去乘以？Y是一個(gè)偶數(shù) 3.所以先把cur+1成為偶數(shù) 4.再/2處理，小于X之后跳出循環(huán) 5.這時(shí)候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時(shí)的情況。分為兩步統(tǒng)計(jì)， cnt1為多少個(gè)乘法，cnt2為多少個(gè)減法。 顯然我們必須把 X 乘到恰好比 Y 大的數(shù)，否則再怎么減也達(dá)不到要求……因此先求 cnt1. 那么，關(guān)鍵是 cnt2 怎么求呢？我們假設(shè)減法穿插在各個(gè)乘法之間，如果在第一次乘法前減，那么最終等價(jià)于減去 2cnt12^{cnt1}2cnt1, 如果在第二次乘法前減，最終等價(jià)于減去 2cnt1?12^{cnt1 - 1}2cnt1?1，以此類推。由于每次可以減多個(gè)1，因此最終要乘個(gè)系數(shù)，減了 a 2cnt12^{cnt1}2cnt1 + b 2cnt1?12^{cnt1 - 1}2cnt1?1 + .... 那么這個(gè)系數(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;
    }
}