难度: Medium
给你一个正整数 n ，你可以执行下述操作 任意 次：
n 加上或减去 2 的某个 幂返回使 n 等于 0 需要执行的 最少 操作数。
如果 x == 2i 且其中 i >= 0 ，则数字 x 是 2 的幂。
示例 1：
输入：n = 39 输出：3 解释：我们可以执行下述操作： - n 加上 20 = 1 ，得到 n = 40 。 - n 减去 23 = 8 ，得到 n = 32 。 - n 减去 25 = 32 ，得到 n = 0 。 可以证明使 n 等于 0 需要执行的最少操作数是 3 。
示例 2：
输入：n = 54 输出：3 解释：我们可以执行下述操作： - n 加上 21 = 2 ，得到 n = 56 。 - n 加上 23 = 8 ，得到 n = 64 。 - n 减去 26 = 64 ，得到 n = 0 。 使 n 等于 0 需要执行的最少操作数是 3 。
提示：
1 <= n <= 105运行时间: 18 ms
内存: 16.1 MB
class Solution:
def minOperations(self, n: int) -> int:
b = list(bin(n)[2:])
res = count = 0
idx = len(b) - 1
while idx >= 0:
if b[idx] == '1':
res += 1
b[idx] = '0'
if idx == 0 or b[idx - 1] != '1':
idx -= 1
continue
while idx > 0 and b[idx - 1] == '1':
idx -= 1
b[idx] = '0'
idx -= 1
if idx >= 0:
b[idx] = '1'
else:
res += 1
else:
idx -= 1
return res
这个题解采用了一种贪心的思路。首先，将整数 n 转换为二进制表示。然后从最低位开始遍历，每次遇到 1 时，进行一次操作，将该位变为 0。如果这个 1 的左边还有 1，则需要额外进行一次操作，将左边的 1 都变为 0，最左边的 0 变为 1。这样做的原因是，每次操作都是加上或减去 2 的某个幂，所以在二进制表示中，就是在某个位置加上或减去 1。这个过程一直进行，直到整个二进制表示中没有 1 为止。
时间复杂度: O(log n)
空间复杂度: O(log n)
class Solution:
def minOperations(self, n: int) -> int:
b = list(bin(n)[2:]) # 将 n 转换为二进制表示
res = 0 # 结果计数器
idx = len(b) - 1 # 从最低位开始遍历
while idx >= 0:
if b[idx] == '1': # 如果当前位是 1
res += 1 # 需要一次操作
b[idx] = '0' # 将当前位变为 0
if idx == 0 or b[idx - 1] != '1':
idx -= 1
continue
while idx > 0 and b[idx - 1] == '1':
idx -= 1
b[idx] = '0'
idx -= 1
if idx >= 0:
b[idx] = '1'
else:
res += 1
else:
idx -= 1
return res
在二进制中，每个1表示2的幂次的和。为了将数字减到0，我们需要消除所有的1。每次遇到1时进行加或减操作，实质上是消除当前位上的1，即将其变为0。通过对每个1位执行操作，逐步将所有的1清零，最终会使得二进制表示中没有1，即数字变为0。这种方法通过逐位处理保证了最终n等于0。
这种操作是基于贪心策略的考虑。当连续的1（如1101中的11）存在时，仅将当前位的1变为0（变为1001）还不足以最优化操作次数。继续进行操作，将左边的1也变为0（变为0001），然后将最左边的0（如果存在）变为1（变为1001），是为了在下一轮操作中减少1的数量，从而更快达到目标。这种操作通过在可能的情况下减少连续1的数量，提高了减少到零的效率。
是的，对于每个位的处理都是必需的。虽然后面的位可能全是0，但处理每个位是为了确保当前位上的1被正确地转换或消除。此外，即便后面都是0，当前位上的1如果不处理，仍然会保留其数值，使n不为0。因此，必须处理每个位上的1，直到所有的1都被消除。
当最高位为1且左边没有更高的位时，这个1表示数字中最大的2的幂。处理这种情况的方法是简单的：将此1转换为0。因为没有更高的位，所以不需要额外的操作来增加更高位的1或减少位数。这个操作将直接减少n的值，逐步接近0。在这种情况下，只需要一次操作即可处理最高位的1。