原文链接: https://leetcode-cn.com/problems/minimum-one-bit-operations-to-make-integers-zero

英文原文

Given an integer n, you must transform it into 0 using the following operations any number of times:

• Change the rightmost (0th) bit in the binary representation of n.
• Change the ith bit in the binary representation of n if the (i-1)th bit is set to 1 and the (i-2)th through 0th bits are set to 0.

Return the minimum number of operations to transform n into 0.

 

Example 1:

Input: n = 0
Output: 0

Example 2:

Input: n = 3
Output: 2
Explanation: The binary representation of 3 is "11".
"11" -> "01" with the 2nd operation since the 0th bit is 1.
"01" -> "00" with the 1st operation.

Example 3:

Input: n = 6
Output: 4
Explanation: The binary representation of 6 is "110".
"110" -> "010" with the 2nd operation since the 1st bit is 1 and 0th through 0th bits are 0.
"010" -> "011" with the 1st operation.
"011" -> "001" with the 2nd operation since the 0th bit is 1.
"001" -> "000" with the 1st operation.

Example 4:

Input: n = 9
Output: 14

Example 5:

Input: n = 333
Output: 393

 

Constraints:

• 0 <= n <= 109

中文题目

给你一个整数 n，你需要重复执行多次下述操作将其转换为 0 ：

• 翻转 n 的二进制表示中最右侧位（第 0 位）。
• 如果第 (i-1) 位为 1 且从第 (i-2) 位到第 0 位都为 0，则翻转 n 的二进制表示中的第 i 位。

返回将 n 转换为 0 的最小操作次数。

 

示例 1：

输入：n = 0
输出：0

示例 2：

输入：n = 3
输出：2
解释：3 的二进制表示为 "11"
"11" -> "01" ，执行的是第 2 种操作，因为第 0 位为 1 。
"01" -> "00" ，执行的是第 1 种操作。

示例 3：

输入：n = 6
输出：4
解释：6 的二进制表示为 "110".
"110" -> "010" ，执行的是第 2 种操作，因为第 1 位为 1 ，第 0 到 0 位为 0 。
"010" -> "011" ，执行的是第 1 种操作。
"011" -> "001" ，执行的是第 2 种操作，因为第 0 位为 1 。
"001" -> "000" ，执行的是第 1 种操作。

示例 4：

输入：n = 9
输出：14

示例 5：

输入：n = 333
输出：393

 

提示：

• 0 <= n <= 109

通过代码

高赞题解

本场周赛题解 | 我的LeetCode比赛题解

方法一：递归

要注意到的是，因为必须首先将高位的$1$翻转为$0$，所以本题其实只存在一种合法的操作顺序，我们只要按照这一顺序进行操作即可。

手算几个数，可以发现$F(2^n)=2^{n+1}-1$，因此我们可以将其作为一个捷径。

我们需要考虑两种情况：

1. 把当前数变为$0$。我们首先要找到最高位的$1$，找到之后，我们需要的翻转次数，就是将之后的位置变为$10\dots0$，再将最高位翻转，然后将剩下的数变为$0$。因为剩下的数必然是$2$的幂次，就可以使用上面的捷径。
2. 把当前数变为$10\dots 0$。如果$1$对应的位置已经是$1$，我们只需要将后面的数变为$0$；否则，我们需要先把后面变为$10\dots0$，将最高位翻转，再将剩下的数变为$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);
    }
};

方法二：格雷码

如果进一步观察，可以发现，题目中给出的操作，实际上就是从Gray(n)变换为Gray(n-1)的操作。所以我们可以直接套用求逆格雷码的方法来进行求解。

时间复杂度$O(\log N)$。

class Solution {
public:
    int minimumOneBitOperations(int n) {
        int ans = 0;
        while (n) {
            ans ^= n;
            n >>= 1;    
        } 
        return ans;
    }
};

统计信息

通过次数	提交次数	AC比率
2177	3571	61.0%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言