LeetCode 题解工作台
负二进制数相加
给出基数为 -2 的两个数 arr1 和 arr2 ，返回两数相加的结果。 数字以 数组形式 给出：数组由若干 0 和 1 组成，按最高有效位到最低有效位的顺序排列。例如， arr = [1,1,0,1] 表示数字 (-2)^3 + (-2)^2 + (-2)^0 = -3 。 数组形式 中的数字 …
2
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·数学
答案摘要
我们遍历两个数组，从最低位开始，记两个数组当前位的数字为 和 ，进位为 ，三个数相加的结果为 。 - 先将进位 置为 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·数学 题型思路
题目描述
给出基数为 -2 的两个数 arr1 和 arr2，返回两数相加的结果。
数字以 数组形式 给出：数组由若干 0 和 1 组成，按最高有效位到最低有效位的顺序排列。例如，arr = [1,1,0,1] 表示数字 (-2)^3 + (-2)^2 + (-2)^0 = -3。数组形式 中的数字 arr 也同样不含前导零：即 arr == [0] 或 arr[0] == 1。
返回相同表示形式的 arr1 和 arr2 相加的结果。两数的表示形式为：不含前导零、由若干 0 和 1 组成的数组。
示例 1：
输入：arr1 = [1,1,1,1,1], arr2 = [1,0,1] 输出：[1,0,0,0,0] 解释：arr1 表示 11，arr2 表示 5，输出表示 16 。
示例 2：
输入：arr1 = [0], arr2 = [0] 输出：[0]
示例 3：
输入：arr1 = [0], arr2 = [1] 输出：[1]
提示：
1 <= arr1.length, arr2.length <= 1000arr1[i]和arr2[i]都是0或1arr1和arr2都没有前导0
解题思路
方法一：模拟
我们遍历两个数组，从最低位开始，记两个数组当前位的数字为 和 ，进位为 ，三个数相加的结果为 。
- 先将进位 置为 。
- 如果 ，由于 ，所以我们可以将 减去 ，并向高位进位 。
- 如果 ，由于 ，所以我们可以将 置为 ，并向高位进位 。
然后，我们将 加入到答案数组中，然后继续处理下一位。
遍历结束后，去除答案数组中末尾的 ，并将数组反转，即可得到最终的答案。
时间复杂度 ，其中 和 分别是两个数组的长度。忽略答案的空间消耗，空间复杂度 。
相似题目：
class Solution:
def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:
i, j = len(arr1) - 1, len(arr2) - 1
c = 0
ans = []
while i >= 0 or j >= 0 or c:
a = 0 if i < 0 else arr1[i]
b = 0 if j < 0 else arr2[j]
x = a + b + c
c = 0
if x >= 2:
x -= 2
c -= 1
elif x == -1:
x = 1
c += 1
ans.append(x)
i, j = i - 1, j - 1
while len(ans) > 1 and ans[-1] == 0:
ans.pop()
return ans[::-1]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidates should demonstrate an understanding of how base -2 impacts the addition and carry operations.
- question_mark
Candidates should be able to explain how to handle the negative base while adding bits and adjusting the carry.
- question_mark
Look for clarity in how the candidate handles the reversal of the result and removal of leading zeros.
常见陷阱
外企场景- error
Misunderstanding the carry rules for base -2 can lead to incorrect results, especially for large numbers.
- error
Failing to account for negative values when calculating carries, especially when they exceed 1 or fall below 0.
- error
Not removing leading zeros from the final result array, which can result in an incorrect format.
进阶变体
外企场景- arrow_right_alt
Implement the solution without reversing the final array.
- arrow_right_alt
Optimize the solution for space complexity by avoiding the creation of unnecessary arrays.
- arrow_right_alt
Extend the problem to handle multiple base -2 numbers rather than just two.