Medium

题目描述

给你两个以 -2 为基数（negabinary）表示的数 arr1 和 arr2，请你返回两数相加的结果。

每个数字以数组形式给出：数组由若干 0 和 1 组成，按最高有效位到最低有效位的顺序排列。例如，arr = [1,1,0,1] 表示数字 (-2)^3 + (-2)^2 + (-2)^0 = -3。数组形式的数字也同样不含前导零：以 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 都不含前导零

解题思路

解题思路

负二进制数的加法与普通二进制不同，主要区别在于进位处理。在 -2 进制中，位权为 (-2)^i，这意味着奇数位是负权重，偶数位是正权重。

核心思想：

  1. 从最低位开始相加：像普通加法一样，从右到左逐位处理
  2. 进位规则特殊：当某位的和 ≥ 2 时，需要向高位进位，但由于是 -2 进制，进位值为 -1（而不是普通二进制的 +1）
  3. 处理负进位：当某位出现负值时，需要向更高位借位

具体算法：

  • 用双指针从两个数组的末尾开始遍历
  • 维护一个 carry 变量表示进位
  • 每一位的计算：sum = digit1 + digit2 + carry
  • 当前位结果：sum % 2
  • 新的进位：sum / 2（注意这里可能是负数）
  • 继续处理直到所有位都处理完且无进位

关键在于理解负二进制的进位机制：当 sum ≥ 2 时，我们设当前位为 0，向高位进位 -1，这样总值保持不变。

代码实现

class Solution {
public:
    vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {
        vector<int> result;
        int i = arr1.size() - 1, j = arr2.size() - 1;
        int carry = 0;
        
        while (i >= 0 || j >= 0 || carry != 0) {
            int sum = carry;
            if (i >= 0) sum += arr1[i--];
            if (j >= 0) sum += arr2[j--];
            
            result.push_back(sum & 1);
            carry = -(sum >> 1);
        }
        
        // Remove leading zeros
        while (result.size() > 1 && result.back() == 0) {
            result.pop_back();
        }
        
        reverse(result.begin(), result.end());
        return result;
    }
};

class Solution:
    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:
        result = []
        i, j = len(arr1) - 1, len(arr2) - 1
        carry = 0
        
        while i >= 0 or j >= 0 or carry != 0:
            total = carry
            if i >= 0:
                total += arr1[i]
                i -= 1
            if j >= 0:
                total += arr2[j]
                j -= 1
            
            result.append(total & 1)
            carry = -(total >> 1)
        
        # Remove leading zeros
        while len(result) > 1 and result[-1] == 0:
            result.pop()
        
        return result[::-1]

public class Solution {
    public int[] AddNegabinary(int[] arr1, int[] arr2) {
        List<int> result = new List<int>();
        int i = arr1.Length - 1, j = arr2.Length - 1;
        int carry = 0;
        
        while (i >= 0 || j >= 0 || carry != 0) {
            int sum = carry;
            if (i >= 0) sum += arr1[i--];
            if (j >= 0) sum += arr2[j--];
            
            result.Add(sum & 1);
            carry = -(sum >> 1);
        }
        
        // Remove leading zeros
        while (result.Count > 1 && result[result.Count - 1] == 0) {
            result.RemoveAt(result.Count - 1);
        }
        
        result.Reverse();
        return result.ToArray();
    }
}

var addNegabinary = function(arr1, arr2) {
    const result = [];
    let i = arr1.length - 1, j = arr2.length - 1;
    let carry = 0;
    
    while (i >= 0 || j >= 0 || carry !== 0) {
        let sum = carry;
        if (i >= 0) sum += arr1[i--];
        if (j >= 0) sum += arr2[j--];
        
        result.push(sum & 1);
        carry = -(sum >> 1);
    }
    
    // Remove leading zeros
    while (result.length > 1 && result[result.length - 1]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(max(m, n))
空间复杂度O(max(m, n))

其中 m 和 n 分别为 arr1 和 arr2 的长度。时间复杂度主要由遍历两个数组决定，空间复杂度由结果数组的长度决定。