题目:
给你一个整数 n
,以二进制字符串的形式返回该整数的 负二进制(base -2
)表示。
注意,除非字符串就是 "0"
,否则返回的字符串中不能含有前导零。
提示:
0 <= n <= 109
思考:
手写出以2和3为例的负二进制计算方法:
Python中计算商和余数的函数divmod(dividend, divisor) ,当除数为负数时,会确保余数也是负数,例如divmod(3, -2) 的商为-2,余数为-1。但显然我们在计算负二进制时,余数应该取1或0,通过观察可以看出:
- 当divmod函数计算的余数为-1时,我们实际使用的余数是1,商是函数计算结果加一
- 当divmod函数计算的余数为0时,我们实际使用的余数和商与函数计算结果一致
每一步的商是下一步的被除数,计算出每一步的余数加到列表末端,直到商为0为止。将储存余数的列表倒置,并转换成字符串返回即可。代码如下:
class Solution(object):
def baseNeg2(self, n):
"""
:type n: int
:rtype: str
"""
if n == 0:
return "0"
num = []
while n:
n, remainder = divmod(n, -2)
if remainder < 0:
n += 1
num.append(-remainder)
else:
num.append(remainder)
num.reverse() # 将列表反转
res = "".join(map(str, num)) # 把每个元素变成字符串然后连起来
return res
提交通过: