推 pandix: 大師 11/30 11:27
推 NTHUlagka: 大師 12/01 13:27
1611. Minimum One Bit Operations to Make Integers Zero
給你一個數字，你可以針對它的二進制位元進行以下兩種操作
1.設定個位數的數字
2.設定第n位數的數字，條件是第n-1位是1而且第n-2位以後全部都是0
回傳將數字歸零的最小操作數
Input: n = 3 Output: 2
11 -> 01 -> 00
Input: n = 6 Output: 4
110 -> 010 -> 011 -> 001 -> 000
Intuition
類似河內塔的概念去解
用遞迴的想法去思考會比較簡單
Approach
先觀察數字找出規律，例如0b10
10
11
01
00
就是先把次大的變成一
然後首位歸零
再來把剛才的次大歸零
再把再來看一個更大的數字0b1000
1000
←
1001
←
1010
←
1100
↓
0100
→
0010
→
0001
→
0000
把次大的數字變成一的過程就是1從個位數持續往左推
之後再將1往右拉
持續下去一直到所有數字不見
從規律我們可以看出
消除A(n) = 把次大變一 + 1 + 把次大歸零
用公式這樣表示
A(n)=A(n-1) + 1 + A(n-1)
這個與河內塔的公式是一樣的
可以知道速解法就是A(n) = 2^n - 1
但是這一題跟河內塔的差異是
數字不一定是完全的1後面結尾全部接0
有可能後面也會有數字
例如0b100100100
只看最後0b100的話
是要把A(3)往後拉
→
100
但是看0b100100的話就會反過來A(3)往前推A(6)往後拉
→ ←
100100
計算就是A(6) - A(3)
看整個數字0b100100100的話
```
→ ←→
100100100
```
計算就是A(9) - (A(6) - A(3))
可以知道從個位數往前計算
遇到一個新的1就把當前結果變相反數
再加上歸零需要的步數就是答案
另外這一題可以用位元運算符計算會比轉成字串再跑回圈還快
靠北這一題計算很簡單
但是解釋好難
然後這題的leetcode文章轉成ptt超麻煩
二進制在leetcode可以直接寫$$100100_2$$
可是在ptt就要用0b100100
數學公式也是可以直接寫下標 $$a_n=a_{n-1}+1+a_{n-1}$$
到ptt就要全部重寫
TS Code:
function minimumOneBitOperations (n: number): number {
let result = 0
let operation = 2
do {
if (n & 1) result = result * -1 + operation - 1
operation = operation * 2
n = n >> 1
} while (n > 0)
return result
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.229.33 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1701314500.A.E9E.html