Hard

题目描述

给定一个整数 n，你必须使用以下操作任意次数将其变为 0：

  • 改变 n 的二进制表示中最右边（第 0 位）的位。
  • 如果第 (i-1) 位为 1 且第 (i-2) 到第 0 位都为 0，则可以改变第 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。
"010" -> "011" 使用第 1 种操作。
"011" -> "001" 使用第 2 种操作，因为第 0 位是 1。
"001" -> "000" 使用第 1 种操作。

约束条件：

  • 0 <= n <= 10^9

提示：

  • 将 n 转换为零的最快方法是从最左边开始删除所有设置位。尝试一些简单的例子来学习删除一个设置位需要多少步骤的规律。
  • 首先考虑 n=2^k 的情况，然后解决所有 n。

解题思路

这道题的核心是理解格雷码（Gray Code）的性质。根据操作规则，我们需要找到一个转换序列将 n 变为 0。

关键观察：

  1. 对于 n = 2^k（只有最高位为1），设 f(2^k) 表示将其变为0的最少操作数，可以推导出：f(2^k) = 2^(k+1) - 1

  2. 这个问题本质上是格雷码的逆向操作。格雷码有一个重要性质：相邻两个数字只有一位不同。

  3. 对于任意数字 n，我们可以使用递推公式：

    • 找到 n 的最高位 k
    • f(n) = f(2^k) - f(n ^ 2^k)

    这个公式的含义是：要清除最高位，我们需要 f(2^k) 步操作，但由于还有其他位，我们需要减去处理剩余位的操作数。

算法步骤：

  1. 如果 n = 0，返回 0
  2. 找到 n 的最高位位置 k
  3. 递归计算：f(2^k) - f(n ^ 2^k)
  4. 其中 f(2^k) = 2^(k+1) - 1

这种方法利用了格雷码的性质，通过递推关系高效求解。

代码实现

class Solution {
public:
    int minimumOneBitOperations(int n) {
        if (n == 0) return 0;
        
        // 找到最高位
        int k = 0;
        while ((1 << (k + 1)) <= n) k++;
        
        // f(2^k) = 2^(k+1) - 1
        // f(n) = f(2^k) - f(n ^ 2^k)
        return (1 << (k + 1)) - 1 - minimumOneBitOperations(n ^ (1 << k));
    }
};

class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        if n == 0:
            return 0
        
        # 找到最高位
        k = 0
        while (1 << (k + 1)) <= n:
            k += 1
        
        # f(2^k) = 2^(k+1) - 1
        # f(n) = f(2^k) - f(n ^ 2^k)
        return (1 << (k + 1)) - 1 - self.minimumOneBitOperations(n ^ (1 << k))

public class Solution {
    public int MinimumOneBitOperations(int n) {
        if (n == 0) return 0;
        
        // 找到最高位
        int k = 0;
        while ((1 << (k + 1)) <= n) k++;
        
        // f(2^k) = 2^(k+1) - 1
        // f(n) = f(2^k) - f(n ^ 2^k)
        return (1 << (k + 1)) - 1 - MinimumOneBitOperations(n ^ (1 << k));
    }
}

/**
 * @param {number} n
 * @return {number}
 */
var minimumOneBitOperations = function(n) {
    if (n === 0) return 0;
    
    let k = 0;
    let temp = n;
    while (temp > 0) {
        k++;
        temp >>= 1;
    }
    k--;
    
    return (1 << (k + 1)) - 1 - minimumOneBitOperations(n ^ (1 << k));
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(log n)递归深度等于 n 的二进制位数
空间复杂度O(log n)递归调用栈的深度

相关题目