前往
大廳
主題

LeetCode - 1611. Minimum One Bit Operations to Make Integers Zero 解題心得

Not In My Back Yard | 2024-04-22 15:00:01 | 巴幣 0 | 人氣 48

題目連結:


題目意譯:
給定一整數 n,你必須藉由以下若干次的操作來將其轉換成 0:
    將 n 的二進位表示法中最右側的位元(即第 0 位元)改變其數值;
    將 n 的二進位表示法中第 i 位改變數值,前提是第 i - 1 位元是 1,而第 i - 2 位元到第 0 位元都是 0。

回傳將 n 轉換成 0 最少所需的操作數。

限制:
0 ≦ n ≦ 10 ^ 9



範例測資:
範例 1:
輸入: n = 3
輸出: 2
解釋: 3 的二進位表示法為 "11"。
用第二種操作將 "11" -> "01",因為第 0 個位元是 1。
用第一種操作將 "01" -> "00"。

範例 2:
輸入: n = 6
輸出: 4
解釋: 6 的二進位表示法為 "110"。
用第二種操作將 "110" -> "010",因為第 1 個位元是 1 且第 0 位元到第 0 位元都是 0。
用第一種操作將 "010" -> "011"。
用第二種操作將 "011" -> "001",因為第 0 個位元是 1。
用第一種操作將 "001" -> "000"。


解題思維:
首先,我們先來判斷最單純的兩個情況:
    如果 n == 0,則不需要任何操作;
    如果 n 是 2 的某個冪次,即在 n 的二進位表示法中只有一個位元是 1(假設其為第 i 位元),則需要 2 ^ (i + 1) - 1 次操作。
    
上面的第二個情況可以用數學歸納法證明。因為可以看到為了將第 i 位元改變狀態,我們會需要先將第 i - 1 位元變成 1、其後位元是 0(這邊次數是 2 ^ i - 1);用一次操作把第 i 位元變成 0,再把第 i - 1 位元變回 0(因故又有 2 ^ i - 1 次操作)。詳細證明過程省略。



接下來「第二單純」的情況就是 n 的二進位表示法中只有兩個位元是 1(假設為第 i 位元和第 j 位元,其中 i > j)。可以看到這個情況其實有點像是在處理 n 是 2 的冪次,但是是在把第 i - 1 位元變成 1 的過程中做一半的感覺。

因此,我們可以繼續所述之過程把第 i - 1 位元變成 1 為止(除非 j 本來就是 i - 1 了),也就是:
    將第 j + 1 位元設為 1,將第 j 位元變回 0。次數是 2 ^ (j + 1) - 1 + 1 = 2 ^ (j + 1);
    將第 j + 2 位元設為 1,將第 j + 1 位元變回 0。次數是 2 ^ (j + 2);
    ……
    將第 i - 1 位元設為 1,將第 i - 2 位元變回 0。次數是 2 ^ (i - 1);
最後再
    將第 i 位元設為 0,將第 i - 1 位元變回 0。次數是 2 ^ i。
因此總次數為
    2 ^ (j + 1) + 2 ^ (j + 2) + …… + 2 ^ (i - 1) + 2 ^ i



那剩下的情況呢?有了以上基礎之後也變得單純了,因為現在我們可以在 n 的二進位表示法中找出最左側的兩個 1(假設是第 i 位元和第 j 位元,其中 i > j)。而這兩個 1 為了要變成上面「第二單純」的情況需要其餘的 1 都先被消掉。

因此此時我們會產生出一個子問題——(n - 2 ^ i - 2 ^ j) 變成 0 的所需最少次數。因此我們可以遞迴解出這個子問題之後再根據上面的敘述處理第 i 、 j 位元即可。



等等那為什麼不直接只在 n 的二進位表示法中找出最左側的第 i 位元,然後先做子問題 (n - 2 ^ i) 再來處理第 i 位元呢?

因為這樣一來,原本「第 j 位元」(即第二左側的那一個 1)會在子問題中先被消掉,但是我們本來大可以直接套用「第二單純」的情況來得到更少的操作數。因為正如先前所述,第 j 位元的存在可以視為是處理第 i 位元時做一半的感覺。

而為了處理第 i 、 j 位元,其餘的 1 是「不得不」消掉。所以子問題可以放心做,不會有所「浪費」。

因故我們只能每次取最左側的兩個 1 來得到新的子問題來遞迴解。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作