标签: 数学
难度: Medium
给你一个整数 n ，以二进制字符串的形式返回该整数的 负二进制（base -2）表示。
注意，除非字符串就是 "0"，否则返回的字符串中不能含有前导零。
示例 1：
输入：n = 2 输出："110" 解释：(-2)2 + (-2)1 = 2
示例 2：
输入：n = 3 输出："111" 解释：(-2)2 + (-2)1 + (-2)0 = 3
示例 3：
输入：n = 4 输出："100" 解释：(-2)2 = 4
提示：
0 <= n <= 109运行时间: 24 ms
内存: 0.0 MB
class Solution:
def baseNeg2(self, N: int) -> str:
if N == 0:
return "0"
str_builder = []
while N:
r = N % (-2)
N = N // (-2)
if r < 0:
r = -r
N += 1
str_builder.append(str(r))
str_builder.reverse()
return "".join(str_builder)
该题解采用的是负二进制的转换方法。算法从整数N开始，通过不断除以-2，并取余数的方式来构建负二进制的表示。这里的关键是处理余数r，因为当余数为负时，需要调整N和余数r以保持余数非负。这是由于在负基数的情况下，标准的除法和余数操作可能生成负的余数。每次迭代中，计算N除以-2的商和余数，如果余数是负的，就调整N（增加1）和r（取其绝对值），以便正确地形成负二进制数。迭代继续直到N变为0。最后，将累积的数字逆序拼接成字符串，以符合从最高位到最低位的顺序。
时间复杂度: O(log N)
空间复杂度: O(log N)
class Solution:
def baseNeg2(self, N: int) -> str:
if N == 0:
return '0' # 如果输入为0，直接返回'0'
str_builder = [] # 存储每一位数字
while N:
r = N % (-2) # 计算余数
N = N // (-2) # 计算负二进制的'商'
if r < 0: # 如果余数是负的，调整
r = -r # 取余数的绝对值
N += 1 # 将商增加1来调整
str_builder.append(str(r)) # 将当前位添加到结果列表
str_builder.reverse() # 反转列表以匹配正确的顺序
return ''.join(str_builder) # 将列表转换为字符串并返回
在使用负二进制表示法中，由于基数是负数（-2），常规的求余操作可能得到负的余数。例如，对于某次迭代中的N值，如果余数r为负，那么直接使用这个负余数会导致结果错误。因此，为了确保每一位的数字非负（0或1），当得到负余数时，我们需要调整N和余数r。将余数r取绝对值后，N需要增加1，这是因为增加1后，N除以-2的结果会补偿由于取绝对值引入的差异，从而维持算法的正确性。这种调整保证了余数始终为0或1，符合负二进制的表示要求。
在这个算法中，不论N的初始值是正数、负数还是零，处理逻辑都是一致的。算法通过不断除以-2并处理余数来适应所有整数输入。即使N是负数，算法依然按照同样的方式执行，因为余数和商的调整逻辑（如处理余数为负的情况）能够正确地处理N为负数的情况。因此，不需要对负数输入进行特别的处理，算法本身已经设计成能够自然地处理任何整数（包括负数）。
这个描述不是很准确。由于N每次都是除以-2，实际上N的绝对值在每次迭代后减少至少一半，但由于是除以一个负数，所以N的符号会在每次迭代中交替变化。如果N是正数，那么在除以-2之后，N会变为一个较小的负数；如果N是负数，除以-2后会变为一个较小的正数。这种变化使得N的绝对值逐步减小，直至最终变为0。因此，更准确地描述是：每次迭代后，N的绝对值大约减少一半，而N的符号会交替变化。