LeetCode 题解工作台
负二进制转换
给你一个整数 n ，以二进制字符串的形式返回该整数的 负二进制（ base -2 ） 表示。 注意， 除非字符串就是 "0" ，否则返回的字符串中不能含有前导零。 示例 1： 输入： n = 2 输出： "110" 解释： (-2) 2 + (-2) 1 = 2 示例 2： 输入： n = 3 输出…
1
题型
7
代码语言
3
相关题
当前训练重点
中等 · 数学·driven
答案摘要
我们可以判断 从低位到高位的每一位，如果该位为 ，那么答案的该位为 ，否则为 。如果该位为 ，那么我们需要将 减去 。接下来我们更新 $n = \lfloor n / 2 \rfloor$, $k = -k$。继续判断下一位。 最后，我们将答案反转后返回即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数学·driven 题型思路
题目描述
给你一个整数 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
解题思路
方法一：模拟
我们可以判断 从低位到高位的每一位，如果该位为 ，那么答案的该位为 ，否则为 。如果该位为 ，那么我们需要将 减去 。接下来我们更新 , 。继续判断下一位。
最后，我们将答案反转后返回即可。
时间复杂度 ，其中 为给定的整数。忽略答案的空间消耗，空间复杂度 。
相似题目：
class Solution:
def baseNeg2(self, n: int) -> str:
k = 1
ans = []
while n:
if n % 2:
ans.append('1')
n -= k
else:
ans.append('0')
n //= 2
k *= -1
return ''.join(ans[::-1]) or '0'
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(log n) because each division reduces n roughly by a factor of 2. Space complexity is O(log n) to store the resulting digits in the output string. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Are you tracking how negative remainders affect digit placement?
- question_mark
How do you handle normalization of digits when division yields negative remainders?
- question_mark
Can you produce a result string without leading zeros efficiently?
常见陷阱
外企场景- error
Forgetting to adjust negative remainders leads to incorrect digit sequences.
- error
Appending digits in the wrong order without reversing at the end.
- error
Returning strings with unnecessary leading zeros instead of minimal length.
进阶变体
外企场景- arrow_right_alt
Convert numbers to other negative bases like -3 or -5 using the same remainder adjustment strategy.
- arrow_right_alt
Output the base -2 digits as an array of integers instead of a string.
- arrow_right_alt
Handle signed integers including negative numbers in base -2 representation.