[Leetcode 1073] Adding Two Negabinary Numbers

原题说明

Given two numbers arr1 and arr2 in base -2, return the result of adding them together.

Each number is given in array format:  as an array of 0s and 1s, from most significant bit to least significant bit.  For example, arr = [1,1,0,1] represents the number (-2)^3 + (-2)^2 + (-2)^0 = -3.  A number arr in array format is also guaranteed to have no leading zeros: either arr == [0] or arr[0] == 1.

Return the result of adding arr1 and arr2 in the same format: as an array of 0s and 1s with no leading zeros.

Example 1:

Input: arr1 = [1,1,1,1,1], arr2 = [1,0,1]
Output: [1,0,0,0,0]
Explanation: arr1 represents 11, arr2 represents 5, the output represents 16.

Note:

1. 1 <= arr1.length <= 1000
2. 1 <= arr2.length <= 1000
3. arr1 and arr2 have no leading zeros
4. arr1[i] is 0 or 1
5. arr2[i] is 0 or 1

解题思路

这道题主要考察bit manipulation，也就是位数的转换。
与base 2相比，只需要每次carry变换符号即可，因为相邻位上-2^n与-2^(n+1)的符号相反。
但要注意，我们一定要使用current & 1 以及 -(current >> 1) 来计算当前位的值以及carry的值，
如果使用%和除法的话，对于负数将得到错误的结果。

示例代码 (cpp)

class Solution {
public:
    vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {
        vector<int> rets;
        int carry = 0;
        int i = arr1.size() - 1;
        int j = arr2.size() - 1;
        while (i >= 0 || j >= 0 || carry != 0) {
            int current = carry;
            if (i >= 0) {
                current += arr1[i];
            }
            if (j >= 0) {
                current += arr2[j];
            }
            // 当current = -1时，使用 current % 1将得到-1
            rets.push_back(current & 1);
            // 当current = -1时，使用 -current / 2将得到0
            carry = -(current >> 1);
            --i;
            --j;
        }
        // 把前缀为0的位数去除，只保留最后一位
        while (rets.size() > 1 && rets.back() == 0) {
            rets.pop_back();
        }
        reverse(rets.begin(), rets.end());
        return rets;
    }
};

示例代码 (java)

class Solution {
    public int[] addNegabinary(int[] arr1, int[] arr2) {
        int i = arr1.length - 1, j = arr2.length - 1, carry = 0;
        Stack<Integer> stack = new Stack<>();
        while (i >= 0 || j >= 0 || carry != 0) {
            int v1 = i >= 0 ? arr1[i--] : 0;
            int v2 = j >= 0 ? arr2[j--] : 0;
            carry = v1 + v2 + carry;
            stack.push(carry & 1);
            carry = -(carry >> 1);
        }
        while (!stack.isEmpty() && stack.peek() == 0) stack.pop();
        int[] res = new int[stack.size()];
        int index = 0;
        while (!stack.isEmpty()) {
            res[index++] = stack.pop();
        }
        return res.length == 0 ? new int[1] : res;
    }
}

示例代码 (python)

class Solution:
    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:
        res = []
        carry = 0
        while arr1 or arr2 or carry:
            carry += (arr1 or [0]).pop() + (arr2 or [0]).pop()
            res.append(carry & 1)
            carry = -(carry >> 1)
        while len(res) > 1 and res[-1] == 0:
            res.pop()
        return res[::-1]

复杂度分析

时间复杂度: O(M + N)
空间复杂度: O(1)

视频讲解

我们在Youtube上更新了视频讲解，欢迎关注！