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
}