1073. 负二进制数相加
2023-05-17 本文已影响0人
红与树
精神成人，知识成才，态度成全。
LC每日一题，参考1073. 负二进制数相加，难度分1807。
题目
给出基数为 -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 组成的数组。
输入：arr1 = [1,1,1,1,1], arr2 = [1,0,1]
输出：[1,0,0,0,0]
解释：arr1 表示 11，arr2 表示 5，输出表示 16 。
输入：arr1 = [0], arr2 = [0]
输出：[0]
输入：arr1 = [0], arr2 = [1]
输出：[1]
解题思路
- 模拟进位：
- 从右往左遍历 arr1 和 arr2，分别取出当前位的值 x 和 y ,carry 为进位。
- 计算当前位的和 sum = x + y + carry，并将结果的个位添加到结果列表的最前面。
- 如果 sum 大于等于 2，需要将 carry 设置为 -1；sum = 0 或 1 carry 为 0 , sum = -1 则 carry 为 1。
- 处理完全部位数后，需要移除结果列表高位的前导 0 。
模拟进位
class Solution {
public int[] addNegabinary(int[] arr1, int[] arr2) {
// i、j 分别是 arr1 和 arr2 数组的索引，carry 是进位的值
int i = arr1.length - 1, j = arr2.length - 1, carry = 0;
// 使用链表存储逆序的二进制结果
LinkedList<Integer> list = new LinkedList<>();
// 从右向左遍历 arr1 和 arr2 数组，并计算两数之和
while (i >= 0 || j >= 0 || carry != 0) {
// x、y 分别是 arr1 和 arr2 数组当前索引位置的值，若索引越界则默认为0
int x = i >= 0 ? arr1[i--] : 0;
int y = j >= 0 ? arr2[j--] : 0;
// 将 x、y 和进位的 carry 相加，得到二进制和 sum
int sum = x + y + carry;
// 将 sum 的末位加入链表的头部，可逆序得到二进制结果
list.addFirst(sum & 1);
// 计算负二进制加法中的进位 carry
// 如果 sum >= 2，则需要向前进位，此时 carry 取 -1
// 如果 sum <= -2，则需要向前借位，此时 carry 取 1
carry = -(sum >> 1);
}
// 去掉二进制结果的前导0
while (list.size() > 1 && list.peekFirst() == 0) {
list.removeFirst();
}
// 将链表转化为整数数组，返回结果
int[] result = new int[list.size()];
int k = 0;
for (int num : list) {
result[k++] = num;
}
return result;
}
}
复杂度分析
- 时间复杂度：
O(n)，n为最长的那个数组的长度。 - 空间复杂度：
O(n)，借助的链表需要存储结果的空间为n。
