class Solution {
public:
int minimumOneBitOperations(int n) {
}
};
1611. 使整数变为 0 的最少操作次数
给你一个整数 n，你需要重复执行多次下述操作将其转换为 0 ：
n 的二进制表示中最右侧位（第 0 位）。(i-1) 位为 1 且从第 (i-2) 位到第 0 位都为 0，则翻转 n 的二进制表示中的第 i 位。返回将 n 转换为 0 的最小操作次数。
示例 1：
输入：n = 3 输出：2 解释：3 的二进制表示为 "11" "11" -> "01" ，执行的是第 2 种操作，因为第 0 位为 1 。 "01" -> "00" ，执行的是第 1 种操作。
示例 2：
输入：n = 6 输出：4 解释：6 的二进制表示为 "110". "110" -> "010" ，执行的是第 2 种操作，因为第 1 位为 1 ，第 0 到 0 位为 0 。 "010" -> "011" ，执行的是第 1 种操作。 "011" -> "001" ，执行的是第 2 种操作，因为第 0 位为 1 。 "001" -> "000" ，执行的是第 1 种操作。
提示：
0 <= n <= 109原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-09-21 23:18:01
func minimumOneBitOperations(n int) (res int) {
for ; n > 0; n = n >> 1 {
res ^= n
}
return
}
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-09-21 23:17:34
func minimumOneBitOperations(n int) int {
if n== 0 {
return 0
}
arrK := make([]int, 32)
arrK[0] = 1
for i := 1; i <= 31; i++ {
arrK[i] = arrK[i-1]*2 + 1
}
return getNum(arrK, n)
}
func getNum(arrK []int, num int) int {
k := findK(num)
if 1<<k == num {
return arrK[k]
}
n := num % (1 << k)
return arrK[k] - getNum(arrK, n)
}
func findK(num int) int {
k := 0
for {
if num >= 1<<k {
k++
} else {
return k - 1
}
}
}
java 解法, 执行用时: 4 ms, 内存消耗: 38.9 MB, 提交时间: 2023-09-21 23:17:24
class Solution {
HashMap<Integer, Integer> map = new HashMap<>();
TreeSet<Integer> set = new TreeSet<>();
public int minimumOneBitOperations(int n) {
map.put(0, 0);
int last2Powk = 1;//记录上一个2^k的数值
while(last2Powk <= n){
map.put(last2Powk, map.get(last2Powk / 2) * 2 + 1);
set.add(last2Powk);
last2Powk *= 2;
}
return helper(n);
}
public int helper(int n){
if(map.containsKey(n)) return map.get(n);
int low = set.floor(n);//找到小于n的最大的2的整次幂
return helper(low) - helper(n % low);
}
// 格雷码
public int minimumOneBitOperations2(int n) {
int res = 0;
while(n != 0){
res ^= n;
n >>= 1;
}
return res;
}
}
python3 解法, 执行用时: 64 ms, 内存消耗: 16.2 MB, 提交时间: 2023-09-21 23:13:35
class Solution:
'''
从左边第二位起，将每位与左边一位解码后的值异或，
作为该位解码后的值（最左边一位依然不变）。直到最低位。
依次异或转换后的值（二进制数）就是格雷码转换后二进制码的值。
'''
def minimumOneBitOperations0(self, n: int) -> int:
if not n:return 0
head = 1<<int(math.log2(n))
return head + self.minimumOneBitOperations((n^head)^(head>>1))
# 递归格雷码
def minimumOneBitOperations(self, n: int) -> int:
if not n:return 0
return n^self.minimumOneBitOperations(n>>1)
# 大数版本
def minimumOneBitOperations3(self, n: int) -> int:
gray_to_byte8 = [0, 1, 3, 2, 7, 6, 4, 5, 15, 14, 12, 13, 8, 9, 11, 10, 31, 30, 28, 29, \
24, 25, 27, 26, 16, 17, 19, 18, 23, 22, 20, 21, 63, 62, 60, 61, 56, \
57, 59, 58, 48, 49, 51, 50, 55, 54, 52, 53, 32, 33, 35, 34, 39, 38, \
36, 37, 47, 46, 44, 45, 40, 41, 43, 42, 127, 126, 124, 125, 120, 121, \
123, 122, 112, 113, 115, 114, 119, 118, 116, 117, 96, 97, 99, 98, 103, \
102, 100, 101, 111, 110, 108, 109, 104, 105, 107, 106, 64, 65, 67, 66, \
71, 70, 68, 69, 79, 78, 76, 77, 72, 73, 75, 74, 95, 94, 92, 93, 88, 89, \
91, 90, 80, 81, 83, 82, 87, 86, 84, 85, 255, 254, 252, 253, 248, 249, \
251, 250, 240, 241, 243, 242, 247, 246, 244, 245, 224, 225, 227, 226, \
231, 230, 228, 229, 239, 238, 236, 237, 232, 233, 235, 234, 192, 193, \
195, 194, 199, 198, 196, 197, 207, 206, 204, 205, 200, 201, 203, 202, \
223, 222, 220, 221, 216, 217, 219, 218, 208, 209, 211, 210, 215, 214, \
212, 213, 128, 129, 131, 130, 135, 134, 132, 133, 143, 142, 140, 141, \
136, 137, 139, 138, 159, 158, 156, 157, 152, 153, 155, 154, 144, 145, \
147, 146, 151, 150, 148, 149, 191, 190, 188, 189, 184, 185, 187, 186, \
176, 177, 179, 178, 183, 182, 180, 181, 160, 161, 163, 162, 167, 166, \
164, 165, 175, 174, 172, 173, 168, 169, 171, 170]
if not n:return 0
head = 0
ls = []
for i in int(n).to_bytes(int((math.log2(n))//8+1),"big"):
ls.append(gray_to_byte8[i^(head<<7)])
head = ls[-1]&1
return int.from_bytes(ls,'big')
cpp 解法, 执行用时: 0 ms, 内存消耗: 6.2 MB, 提交时间: 2023-09-21 23:08:01
/**
* 格雷码
* 如果进一步观察，可以发现，题目中给出的操作，实际上就是从Gray(n)变换为Gray(n-1)的操作。
* 所以我们可以直接套用求逆格雷码的方法来进行求解。
*/
class Solution {
public:
int minimumOneBitOperations(int n) {
int ans = 0;
while (n) {
ans ^= n;
n >>= 1;
}
return ans;
}
};
cpp 解法, 执行用时: 4 ms, 内存消耗: 6.2 MB, 提交时间: 2023-09-21 23:06:25
/**
* 递归
* 要注意到的是，因为必须首先将高位的1翻转为0，所以本题其实只存在一种合法的操作顺序，
* 我们只要按照这一顺序进行操作即可。
* 手算几个数，可以发现F(2^n)=2^{n+1}−1，因此我们可以将其作为一个捷径。
* 我们需要考虑两种情况：
* 1.把当前数变为0。我们首先要找到最高位的1，找到之后，我们需要的翻转次数，
* 就是将之后的位置变为10…0，再将最高位翻转，然后将剩下的数变为0。
* 因为剩下的数必然是2的幂次，就可以使用上面的捷径。
* 2.把当前数变为10…0。如果1对应的位置已经是1，我们只需要将后面的数变为0；
* 否则，我们需要先把后面变为10…0，将最高位翻转，再将剩下的数变为0。
* 实现这两个函数，递归计算即可。
*/
class Solution {
int f(int n) {
if (n <= 1)
return n;
int t = 32 - __builtin_clz(n) - 1;
return (1 << t) + g(n ^ (1 << t), t - 1);
}
int g(int n, int t) {
if (t == 0)
return 1 - n;
if (n & (1 << t))
return f(n ^ (1 << t));
return (1 << t) + g(n, t - 1);
}
public:
int minimumOneBitOperations(int n) {
return f(n);
}
};