1073. 负二进制数相加

精神成人，知识成才，态度成全。

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]

解题思路

• 模拟进位：

1. 从右往左遍历 arr1 和 arr2，分别取出当前位的值 x 和 y ,carry 为进位。
2. 计算当前位的和 sum = x + y + carry，并将结果的个位添加到结果列表的最前面。
3. 如果 sum 大于等于 2，需要将 carry 设置为 -1；sum = 0 或 1 carry 为 0 , sum = -1 则 carry 为 1。
4. 处理完全部位数后，需要移除结果列表高位的前导 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。