class Solution {
public:
vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {
}
};
1073. 负二进制数相加
给出基数为 -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原站题解
java 解法, 执行用时: 5 ms, 内存消耗: 43.2 MB, 提交时间: 2023-05-18 11:39:21
class Solution {
public int[] addNegabinary(int[] arr1, int[] arr2) {
int i = arr1.length - 1, j = arr2.length - 1;
List<Integer> ans = new ArrayList<>();
for (int c = 0; i >= 0 || j >= 0 || c != 0; --i, --j) {
int a = i < 0 ? 0 : arr1[i];
int b = j < 0 ? 0 : arr2[j];
int x = a + b + c;
c = 0;
if (x >= 2) {
x -= 2;
c -= 1;
} else if (x == -1) {
x = 1;
c += 1;
}
ans.add(x);
}
while (ans.size() > 1 && ans.get(ans.size() - 1) == 0) {
ans.remove(ans.size() - 1);
}
Collections.reverse(ans);
return ans.stream().mapToInt(x -> x).toArray();
}
}
golang 解法, 执行用时: 4 ms, 内存消耗: 3.1 MB, 提交时间: 2023-05-18 11:39:08
func addNegabinary(arr1 []int, arr2 []int) (ans []int) {
i, j := len(arr1)-1, len(arr2)-1
for c := 0; i >= 0 || j >= 0 || c != 0; i, j = i-1, j-1 {
x := c
if i >= 0 {
x += arr1[i]
}
if j >= 0 {
x += arr2[j]
}
c = 0
if x >= 2 {
x -= 2
c -= 1
} else if x == -1 {
x = 1
c += 1
}
ans = append(ans, x)
}
for len(ans) > 1 && ans[len(ans)-1] == 0 {
ans = ans[:len(ans)-1]
}
for i, j = 0, len(ans)-1; i < j; i, j = i+1, j-1 {
ans[i], ans[j] = ans[j], ans[i]
}
return ans
}
python3 解法, 执行用时: 44 ms, 内存消耗: 16.1 MB, 提交时间: 2023-05-18 11:38:52
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]
python3 解法, 执行用时: 40 ms, 内存消耗: 16.2 MB, 提交时间: 2023-05-18 11:38:26
# 模拟
class Solution:
def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:
i, j = len(arr1) - 1, len(arr2) - 1
carry = 0
ans = list()
while i >= 0 or j >= 0 or carry:
x = carry
if i >= 0:
x += arr1[i]
if j >= 0:
x += arr2[j]
if x >= 2:
ans.append(x - 2)
carry = -1
elif x >= 0:
ans.append(x)
carry = 0
else:
ans.append(1)
carry = 1
i -= 1
j -= 1
while len(ans) > 1 and ans[-1] == 0:
ans.pop()
return ans[::-1]