| 日期 |
2022年9月23日 |
| 是否独立完成 |
否 |
| 涉及算法 |
位运算、找规律 |
题面
LeetCode 1611. 使整数变为 0 的最少操作次数
给你一个整数 n，你需要重复执行多次下述操作将其转换为 0 ：
- 翻转
n 的二进制表示中最右侧位（第 0 位）。
- 如果第
(i-1) 位为 1 且从第 (i-2) 位到第 0 位都为 0，则翻转 n 的二进制表示中的第 i 位。
返回将 n 转换为 0 的最小操作次数。
示例 1：
1
2
3
4
5
| 输入：n = 3
输出：2
解释：3 的二进制表示为 "11"
"11" -> "01" ，执行的是第 2 种操作，因为第 0 位为 1 。
"01" -> "00" ，执行的是第 1 种操作。
|
示例 2：
1
2
3
4
5
6
7
| 输入：n = 6
输出：4
解释：6 的二进制表示为 "110".
"110" -> "010" ，执行的是第 2 种操作，因为第 1 位为 1 ，第 0 到 0 位为 0 。
"010" -> "011" ，执行的是第 1 种操作。
"011" -> "001" ，执行的是第 2 种操作，因为第 0 位为 1 。
"001" -> "000" ，执行的是第 1 种操作。
|
题解
冥思苦想了半天，尝试了两三种方法，还是写不出来，一下午就耗这了。看了题解，勉强做出来。
(以下摘自**LeetCode @自在飞花 **前辈的题解)
设 cal(xxxxx) 表示将二进制为 xxxxx 的数字变为 0 的最小操作次数。
如果 xxxxx 形如 11xxx，则只能通过 11xxx -> 11000 -> 1000 -> 0 (只列出了转换序列中的关键步骤) 这样的顺序来改变。
即 cal(11xxx)=cal(xxx)+1+cal(1000)。解释一下：
cal(xxx) 表示将 11xxx 变为 11000 的操作数1 表示将 11000 变为 1000 的操作数cal(1000) 表示将 1000 变为 0 的操作数
如果 xxxxx 形如 10xxx，则只能通过 10xxx -> 11000 -> 1000 -> 0 (只列出了转换序列中的关键步骤) 这样的顺序来改变。
即 cal(10xxx)=cal(1000)−cal(xxx)+cal(11000)。解释一下：
cal(1000) - cal(xxx) 表示将 xxx 变为 1000 的操作数。因为任意一点到达 S 点有且只有一条路径，所有从 xxx 到 1000 的值为 cal(1000) - cal(xxx)。cal(11000) 表示将 11000 变为 0 的操作数。
而我之所以没做出来就是因为想不到把cal(xxx)减掉的思路。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class Solution {
private:
int highbit(int x) {
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
return x - (x >> 1);
}
unordered_map<int, int> map;
unordered_map<int, int> memory;
int steps(int n) {
int m = n;
if (map.count(n)) return map[n];
if (!memory.count(n)) {
int high = highbit(n);
while (n > 0) {
if (n & high) {
if (n & (high >> 1)) {
memory[n] = steps(n ^ high ^ (high >> 1)) + 1 + map[high >> 1];
n = n ^ high ^ (high >> 1);
}
else {
memory[n] = map[high >> 1] - steps(n ^ high) + steps(high + (high >> 1));
n = n ^ high;
}
}
high >>= 1;
}
}
return memory[m];
}
public:
int minimumOneBitOperations(int n) {
map[1] = 1;
for (int i = 1; i < 31; i++) map[1 << i] = 2 * map[1 << (i - 1)] + 1;
memory[0] = 0;
memory[1] = 1;
return steps(n);
}
};
|