题目描述

给出基数为 -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。

注意

• 1 <= arr1.length <= 1000
• 1 <= arr2.length <= 1000
• arr1 和 arr2 都不含前导零
• arr1[i] 为 0 或 1
• arr2[i] 为 0 或 1

算法

(模拟) $O(n)$

1. 模拟高精度加法，只不过进位需要高位减 1。还需要额外检查数位上是否出现了 -1，如果出现了，则需要高位加 1 来将当前位变为 1。
2. 最后去除前导 0。

时间复杂度

• 高精度加法，时间复杂度为 $O(n)$。

空间复杂度

• 需要额外的空间（当然也可以优化掉），空间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:

    vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {
        reverse(arr1.begin(), arr1.end());
        reverse(arr2.begin(), arr2.end());
        int n = arr1.size(), m = arr2.size();
        if (n < m)
            arr1.resize(m);
        else
            arr2.resize(n);

        n = max(n, m);
        vector<int> res(n + 2, 0);
        for (int i = 0; i < n; i++) {
            res[i] += arr1[i] + arr2[i];
            res[i + 1] -= res[i] / 2;
            res[i] %= 2;
        }

        for (int i = 0; i < n + 1; i++) {
            if (res[i] < 0) {
                res[i] += 2;
                res[i + 1]++;
            }
            res[i + 1] -= res[i] / 2;
            res[i] %= 2;
        }
        n += 2;
        while(n > 1 && res[n - 1] == 0)
            n--;
        res.resize(n);
        reverse(res.begin(), res.end());
        return res;
    }
};