LeetCode 1073. Adding Two Negabinary Numbers【模拟】中等

给出基数为 -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 <= 1000
arr1[i] 和 arr2[i] 都是 0 或 1
arr1 和 arr2 都没有前导0

此题与LeetCode 1017. Convert to Base -2【数学】中等有联系，可以参考相关题解。

解法模拟

1. 思路与算法

为了叙述方便，记 a r r 1 [ i ] arr1[i] arr1[i] 和 a r r 2 [ i ] arr2[i] arr2[i] 分别是 a r r 1 arr1 arr1 和 a r r 2 arr2 arr2 从低到高的第 i i i 个数位。在加法运算中，我们需要将它们相加。

对于普通的二进制数相加，我们可以从低位到高位进行运算，在运算的过程中维护一个变量 c a r r y carry carry 表示进位。当运算到第 i i i 位时，令 x = a r r 1 [ i ] + a r r 2 [ i ] + c a r r y x=arr1[i]+arr2[i]+carry x=arr1[i]+arr2[i]+carry ：

如果 x = 0 , 1 x=0,1 x=0,1 ，第 i i i 位的结果就是 x x x ，并且将 c a r r y carry carry 置 0 0 0 ；
如果 x = 2 , 3 x = 2, 3 x=2,3 ，第 i i i 位的结果是 x − 2 x - 2 x−2 ，需要进位，将 c a r r y carry carry 置 1 1 1 。

而本题中是「负二进制数」，第 i i i 位对应的是 ( − 2 ) i (-2)^i (−2)i ，而第 i + 1 i+1 i+1 位对应的是 ( − 2 ) i + 1 (-2)^{i+1} (−2)i+1 ，是第 i i i 位的 − 2 -2 −2 倍。因此，当第 i i i 位发生进位时， carry \textit{carry} carry 应当置为 − 1 -1 −1 ，而不是 1 1 1 。

此时， a r r 1 [ i ] arr1[i] arr1[i] 和 a r r 2 [ i ] arr2[i] arr2[i] 的范围都是 { 0 , 1 } \{0, 1\} {0,1} ，而 carry \textit{carry} carry 的范围从 { 0 , 1 } \{0, 1\} {0,1} 变成了 { − 1 , 0 } \{-1, 0\} {−1,0} ，因此 x x x 的范围从 { 0 , 1 , 2 , 3 } \{0, 1, 2, 3\} {0,1,2,3} 变成了 { − 1 , 0 , 1 , 2 } \{-1, 0, 1, 2\} {−1,0,1,2} 。那么：

如果 x = 0 , 1 x=0,1 x=0,1 ，第 i i i 位的结果就是 x x x ，并且将 c a r r y carry carry 置 0 0 0 ；
如果 x = 2 x = 2 x=2 ，第 i i i 位的结果是 x − 2 x−2 x−2 ，需要进位，将 c a r r y carry carry 置 − 1 -1 −1（用于偶数位是减，用于奇数位相当于加），即逢 2 2 2 进负 1 1 1 ；
如果 x = − 1 x = -1 x=−1 ，此时第 i i i 位的结果应该是什么呢？可以发现，由于： − ( − 2 ) i = ( − 2 ) i + 1 + ( − 2 ) i -(-2)^i = (-2)^{i+1} + (-2)^i −(−2)i=(−2)i+1+(−2)i等式左侧表示第 i i i 位为 − 1 -1 −1 的值，右侧表示第 i i i 和 i + 1 i+1 i+1 位为 1 1 1 的值。因此，。
最终， carry \textit{carry} carry 的范围为 { − 1 , 0 , 1 } \{-1, 0, 1\} {−1,0,1} ，多出一个 x = 3 x=3 x=3 的情况，但它与 x = 2 x=2 x=2 的情况是一致的。

2. 细节

在最坏的情况下，当我们计算完 a r r 1 arr1 arr1 和 a r r 2 arr2 arr2 的最高位的 x x x 时，得到的结果为 x = 3 x=3 x=3 ，此时产生 − 1 -1 −1 的进位，而 − 1 -1 −1 在之后又会产生 1 1 1 的进位，因此，答案的长度最多为 arr 1 \textit{arr}1 arr1 和 a r r 2 arr2 arr2 中较长的长度加 2 2 2 。

题目描述中 a r r 1 [ i ] arr1[i] arr1[i] 和 a r r 2 [ i ] arr2[i] arr2[i] 表示的是 a r r 1 arr1 arr1 和 a r r 2 arr2 arr2 从高到低的第 i i i 个数位，与题解相反。因此，在实际的代码编写中，使用两个指针从 a r r 1 arr1 arr1 和 a r r 2 arr2 arr2 的末尾同时开始进行逆序的遍历，得到逆序的答案，去除前导零，再将答案反转即可得到顺序的最终答案。

class Solution { 
public:
    vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {
        int i = arr1.size() - 1, j = arr2.size() - 1;
        int carry = 0;
        vector<int> ans;
        while (i >= 0 || j >= 0 || carry) {
            int x = carry;
            if (i >= 0) x += arr1[i];
            if (j >= 0) x += arr2[j];
            if (x >= 2) { // 逢2进-1
                ans.push_back(x - 2);
                carry = -1;
            } else if (x >= 0) {
                ans.push_back(x);
                carry = 0;
            } else { // x = -1
                ans.push_back(1);
                carry = 1;
            }
            --i, --j;
        }
        while (ans.size() > 1 && ans.back() == 0) ans.pop_back();
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

复杂度分析：

时间复杂度： O ( m + n ) O(m+n) O(m+n) ，其中 m m m 和 n n n 分别是数组 a r r 1 arr1 arr1 和 arr 2 \textit{arr}2 arr2 的长度。
空间复杂度： O ( 1 ) O(1) O(1) 。注意这里不包括返回值占用的空间。

memcpy0