1073. 负二进制数相加（Rating 1807）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

1073. 负二进制数相加

Rating 1807

思路

开始想仿照 bit0 + bit1 + carry_bit 的形式进行枚举，枚举过程中发现

1 + 1 + 0 = 110

那么按照这种思路计算 11 + 11 的话，会发现永远都算不完，1会一直往高位累加，于是就卡住了…

翻看了下题解，发现几个月前自己独立解答过还写过题解：枚举所有可能的相加情况

这次的思考过程中我忽略了一个重要的点，即

carry_bit 可以是 -1 !

这样就可以避免一直往前加1点情况了。

对于第 i 个 bit 位，我们设 s = bit0 + bit1 + carry_bit

bit0 或 bit1 有 0, 1 两种可能；由于 carry_bit 可能为 -1, 所以其有 -1, 0, 1 三种可能

所以第 i 个 bit 位上的 s 就有 -1, 0, 1, 2, 3 共五种情况需要讨论

• 当 s == -1 时，即 -(-2)^i，通过等式变换可以写作 (-2)^(i + 1) + (-2)^(i)，即等价于本位 bit 为 1，carry_bit 为 1
• 当 s == 0 时，本位 bit 为 0，carry_bit为 0
• 当 s == 1 时，本位 bit 为 1，carry_bit为 0
• 当 s == 2 时，即 2 x (-2)^i，通过等式变换可以写作 -(-2)^(i + 1)，即本位 bit 为 0，carry_bit为 -1
• 当 s == 3 时，即 3 x (-2)^i，通过等式变换可以写作 (-2)^i - (-2)^(i + 1)，即本位 bit 为 1，carry_bit为 -1

代码

'''
templete
s = bit0 + bit1 + cry -> bit, cry

- s == -1 : 0 + 0 - (-2)^i = (-2)^i + (-2)^(i + 1)              ->  0 + 0 - 1  = bit 1, cry 1
- s == 0  : 0 + 0 + 0 = 0                                       ->  0 + 0 + 0  = bit 0, cry 0
- s == 1  : 0 + 0 + (-2)^i = (-2)^i                             ->  0 + 0 + 1  = bit 1, cry 0
- s == 2  : 0 + (-2)^i + (-2)^i = -(-2)^(i + 1)                 ->  0 + 1 + 1  = bit 0, cry -1
- s == 3  : (-2)^i + (-2)^i + (-2)^i = (-2)^i -(-2)^(i + 1)     ->  1 + 1 + 1  = bit 1, cry -1
'''
class Solution:
    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:
        def calc_bit_n_cry(s: int) -> (int, int): # 分5种情况进行讨论，对于不同的s，返回相对应的本位 bit 和carry_bit
            if s == -1:
                return 1, 1
            if s == 0:
                return 0, 0
            if s == 1:
                return 1, 0
            if s == 2:
                return 0, -1
            if s == 3:
                return 1, -1
            return 0, 0

        arr1, arr2 = arr1[::-1], arr2[::-1] # 翻转数组，方便从头开始枚举
        ret = [] # 记录答案
        ind, cry = 0, 0 # 记录 index 和 carry_bit
        while ind < len(arr1) and ind < len(arr2): # 遍历2个数组
            s = arr1[ind] + arr2[ind] + cry # 计算s
            bit, cry = calc_bit_n_cry(s) # 计算本位 bit 和 carry_bit
            ret.append(bit) # 更新答案
            ind += 1 # 更新 index
        while ind < len(arr1): # 如果 arr1 还没遍历完，继续遍历
            s = arr1[ind] + cry
            bit, cry = calc_bit_n_cry(s)
            ret.append(bit)
            ind += 1
        while ind < len(arr2): # 如果 arr2 还没遍历完，继续遍历
            s = arr2[ind] + cry
            bit, cry = calc_bit_n_cry(s)
            ret.append(bit)
            ind += 1
        while cry != 0: # 最后记得处理非0的 carry_bit
            s = cry
            bit, cry = calc_bit_n_cry(s)
            ret.append(bit)
        while len(ret) > 1 and ret[-1] == 0: # 去除多余的前导0，对于答案是0的情况需要至少保留1个0
            ret.pop(-1)
        return ret[::-1] # 翻转数组后输出答案