负二进制数相加

难度: Medium

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

Submission

运行时间: 29 ms

内存: 16.1 MB

class Solution:
    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:
       i = len(arr1) - 1
       j = len(arr2) - 1
       carry = 0
       ans = []
       while i >= 0 or j>=0 or carry:           
           x = carry
           if i >= 0:
               x += arr1[i]
           if j >= 0:
                x += arr2[j]
           if x >= 2: #当三个数相加x>=2,相应位得数为x-2,进位carry为-1
                ans.append(x-2)
                carry = -1
           elif x >= 0:#当三个数相加0<=x<2,相应位数为x, 进位carry为0
                ans.append(x)
                carry = 0
           else: #当x<0,相应位数为1，进位carry为1
                ans.append(1)
                carry = 1
           i -= 1
           j -= 1
       while len(ans) > 1 and ans[-1] == 0:#将前置0排除
            ans.pop()
       return ans[::-1]

Explain

这个题解的核心思路是按位对齐两个数组 arr1 和 arr2，从最低位（即数组末尾）开始逐位相加，并处理进位。不同于常规二进制加法的是，这里的进位可以是负的，因为基数是-2。按照负二进制的规则，每位的累加结果可以是以下几种情况： 1. 累计和为2或更大时，当前位结果为x-2（因为-2 * (-1)相当于+2，所以要减去2来抵消），进位为-1。 2. 累计和为0或1时，当前位结果为x，进位为0。 3. 累计和小于0时，当前位结果为1，进位为1（因为 -2 * 1 = -2，需要向前借一位来抵消这个-2，所以进位为1）。最后，如果结果数组的最高位是0（除了数字0本身），需要移除这些前导0。最后的结果需要反转数组，因为添加结果是从低位到高位的顺序。

时间复杂度: O(max(m, n))

空间复杂度: O(max(m, n))

class Solution:
    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:
       i = len(arr1) - 1
       j = len(arr2) - 1
       carry = 0
       ans = []
       while i >= 0 or j >= 0 or carry:
           x = carry
           if i >= 0:
               x += arr1[i] # 加上arr1当前位
           if j >= 0:
                x += arr2[j] # 加上arr2当前位
           if x >= 2: # 当三个数相加x>=2,相应位得数为x-2,进位carry为-1
                ans.append(x-2)
                carry = -1
           elif x >= 0: # 当三个数相加0<=x<2,相应位数为x, 进位carry为0
                ans.append(x)
                carry = 0
           else: # 当x<0,相应位数为1，进位carry为1
                ans.append(1)
                carry = 1
           i -= 1
           j -= 1
       while len(ans) > 1 and ans[-1] == 0: # 将前置0排除
            ans.pop()
       return ans[::-1] # 反转结果数组以匹配最高位到最低位的输出要求

Explore

在负二进制中，每位的权值是基于 -2 的幂次方。当某位的累计和达到2或更大时，意味着这一位超过了它能表示的最大值1，因此需要调整。将当前位的值设置为 x-2 是为了抵消超过的部分，因为每进位到下一位其实是负权值的增加（即 -2 的下一次幂），所以需要以 -1 来表示这种“向前借位”的情况，这反映了负二进制的特性，即下一位增加的是负的值。

算法设计中，循环条件包括 i >= 0 或 j >= 0 或 carry，这确保了即使 arr1 和 arr2 的所有位都已经处理完毕，只要存在非零的进位（carry），循环仍将继续执行。这样可以处理和消除所有的进位，直到没有进位剩余，从而确保最终结果的准确性。

当累计和小于0时，当前位设置为1并进位为1是因为需要确保这一位的负效果被正确抵消。这种方法在连续多个进位的情况下也是有效的，因为每次处理都是基于当前的累计和进行的，无论是连续的还是单个的进位，都会被算法逐一处理，直到所有的进位都被解决。所以，这种处理方式不会引入错误。

在负二进制加法中，可能出现多余的0作为高位，这通常发生在最终的进位处理后。例如，如果最后一个进位导致最高两位都是0，这些0就成了无意义的前导0。在常规数字表达中，前导0不改变数值，但会影响数的表示。因此，为了得到一个更简洁和标准的表示形式，需要从结果中移除这些前导0。