该题解采用的是负二进制的转换方法。算法从整数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) # 将列表转换为字符串并返回