comments | difficulty | edit_url | rating | source | tags | |||
---|---|---|---|---|---|---|---|---|
true |
困难 |
2345 |
第 209 场周赛 Q4 |
|
给你一个整数 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
本题实际上求的是格雷码为
我们先来回顾一下二进制码转换成二进制格雷码,其法则是保留二进制码的最高位作为格雷码的最高位,而次高位格雷码为二进制码的高位与次高位相异或,而格雷码其余各位与次高位的求法相类似。
假设某个二进制数表示为
那么,格雷码转换成二进制码的逆变换是什么呢?
我们可以发现,格雷码的最高位保留,所以
int rev(int x) {
int n = 0;
for (; x != 0; x >>= 1) {
n ^= x;
}
return n;
}
时间复杂度
class Solution:
def minimumOneBitOperations(self, n: int) -> int:
ans = 0
while n:
ans ^= n
n >>= 1
return ans
class Solution {
public int minimumOneBitOperations(int n) {
int ans = 0;
for (; n > 0; n >>= 1) {
ans ^= n;
}
return ans;
}
}
class Solution {
public:
int minimumOneBitOperations(int n) {
int ans = 0;
for (; n > 0; n >>= 1) {
ans ^= n;
}
return ans;
}
};
func minimumOneBitOperations(n int) (ans int) {
for ; n > 0; n >>= 1 {
ans ^= n
}
return
}
function minimumOneBitOperations(n: number): number {
let ans = 0;
for (; n > 0; n >>= 1) {
ans ^= n;
}
return ans;
}
class Solution:
def minimumOneBitOperations(self, n: int) -> int:
if n == 0:
return 0
return n ^ self.minimumOneBitOperations(n >> 1)
class Solution {
public int minimumOneBitOperations(int n) {
if (n == 0) {
return 0;
}
return n ^ minimumOneBitOperations(n >> 1);
}
}
class Solution {
public:
int minimumOneBitOperations(int n) {
if (n == 0) {
return 0;
}
return n ^ minimumOneBitOperations(n >> 1);
}
};
func minimumOneBitOperations(n int) int {
if n == 0 {
return 0
}
return n ^ minimumOneBitOperations(n>>1)
}
function minimumOneBitOperations(n: number): number {
if (n === 0) {
return 0;
}
return n ^ minimumOneBitOperations(n >> 1);
}