Medium

题目描述

给你一个正整数 n，你可以执行以下操作任意次：

  • 从 n 中加上或减去一个 2 的幂。

返回使 n 等于 0 的最少操作次数。

当 x == 2^i 且 i >= 0 时，数字 x 是 2 的幂。

示例 1：

输入：n = 39
输出：3
解释：我们可以执行以下操作：
- 将 2^0 = 1 加到 n 上，现在 n = 40。
- 从 n 中减去 2^3 = 8，现在 n = 32。
- 从 n 中减去 2^5 = 32，现在 n = 0。
可以证明，使 n 等于 0 需要的最少操作次数是 3。

示例 2：

输入：n = 54
输出：3
解释：我们可以执行以下操作：
- 将 2^1 = 2 加到 n 上，现在 n = 56。
- 将 2^3 = 8 加到 n 上，现在 n = 64。
- 从 n 中减去 2^6 = 64，现在 n = 0。
所以最少操作次数是 3。

约束条件：

  • 1 <= n <= 10^5

提示：

  • 我们能够在二进制表示中设置/取消设置位吗？
  • 如果有多个相邻的 1，我们如何在 2 次操作中最优地加减，使所有的 1 都被取消？
  • 奖励：尝试解决更高约束的问题：n ≤ 10^18。

解题思路

这道题的核心思想是通过位运算来分析二进制表示中的 1 的分布情况。

基础思路： 对于二进制中的每个单独的 1，我们需要 1 次操作来消除它。但关键观察是：如果有连续的多个 1，我们可以用更少的操作来处理。

优化策略： 当我们遇到连续的 1 时（如 111），与其分别消除每个 1（需要 3 次操作），不如：

  1. 先加上一个较小的 2 的幂，使连续的 1 变成一个更高位的 1
  2. 然后减去这个更高位的 2 的幂

例如：111 (二进制) = 7，我们可以：

  • 加上 1 得到 1000 (二进制) = 8
  • 减去 8 得到 0 这样只需要 2 次操作而不是 3 次。

算法实现： 我们可以逐位检查二进制表示：

  • 如果当前位是 0，跳过
  • 如果当前位是 1 且下一位也是 1，说明有连续的 1，我们选择"进位"策略（加法）
  • 如果当前位是 1 但是孤立的，直接减法消除

这个贪心策略是最优的，因为处理连续 1 的进位方法总是比逐个处理更高效。

代码实现

class Solution {
public:
    int minOperations(int n) {
        int operations = 0;
        
        while (n > 0) {
            if ((n & 1) == 0) {
                // 当前位是0，右移继续检查
                n >>= 1;
            } else if ((n & 3) == 3) {
                // 当前位和下一位都是1，使用加法策略
                operations++;
                n = (n + 1) >> 1;
            } else {
                // 当前位是1但下一位是0，使用减法策略
                operations++;
                n >>= 1;
            }
        }
        
        return operations;
    }
};

class Solution:
    def minOperations(self, n: int) -> int:
        operations = 0
        
        while n > 0:
            if n & 1 == 0:
                # 当前位是0，右移继续检查
                n >>= 1
            elif n & 3 == 3:
                # 当前位和下一位都是1，使用加法策略
                operations += 1
                n = (n + 1) >> 1
            else:
                # 当前位是1但下一位是0，使用减法策略
                operations += 1
                n >>= 1
        
        return operations

public class Solution {
    public int MinOperations(int n) {
        int operations = 0;
        
        while (n > 0) {
            if ((n & 1) == 0) {
                // 当前位是0，右移继续检查
                n >>= 1;
            } else if ((n & 3) == 3) {
                // 当前位和下一位都是1，使用加法策略
                operations++;
                n = (n + 1) >> 1;
            } else {
                // 当前位是1但下一位是0，使用减法策略
                operations++;
                n >>= 1;
            }
        }
        
        return operations;
    }
}

/**
 * @param {number} n
 * @return {number}
 */
var minOperations = function(n) {
    let operations = 0;
    
    while (n > 0) {
        if (n & 1) {
            // If n is odd, we need to add or subtract 1 (which is 2^0)
            // Check if adding 1 or subtracting 1 leads to fewer set bits
            if ((n & 3) === 3) {
                // If last two bits are 11, adding 1 is better
                n++;
            } else {
                // If last bit is 1 but second last is 0, subtracting 1 is better
                n--;
            }
            operations++;
        } else {
            // If n is even, divide by 2 (equivalent to right shift)
            n >>= 1;
        }
    }
    
    return operations;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(log n)
空间复杂度O(1)

时间复杂度：我们需要检查 n 的每一个二进制位，最多有 log n 位。 空间复杂度：只使用了常数级别的额外空间。

相关题目