LeetCode 1073. 负二进制数相加

约 10 分钟
文章信息 6 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节跳动
标签
数组 数学
目录

题目描述

✅ 1073. 负二进制数相加

题意分析

输入是两个数组，每个数组是一个数的「以 -2 为底」的表示：下标 0 是最高位，最后一个下标是最低位，第 k 位（从右数，右起第 0 位）的权重是 $(-2)^k$。要求把两个数相加，输出仍然是同样格式的数组，并且不能带前导零（除非结果本身就是 0，此时输出单个 0）。

约束里两点信息最关键。第一，每一位只可能是 0 或 1，没有负数位，也没有大于 1 的位，说明结果必须被「规范化」回 0/1 表示，逐位相加后一定要做某种搬运处理。第二，数组长度最大只有一千出头，且题目给的表示保证无前导零，说明这题的难点完全不在规模上，而在于权重是负数带来的搬运规则和普通加法不一样，属于一道「把定义读懂就能写」的模拟题。

边界有三处：两个数组长度不等，短的那一侧要按 0 补齐；搬运量在最高位耗尽之后还可能不为零，需要继续往前生成新的高位；结果可能出现一串高位全是 0（比如两个相等的数相减式抵消），必须把它们裁掉，但要保留至少一位，否则空数组是非法输出。

解法：进位模拟

核心思路

最朴素的想法是把两个数组各自还原成十进制整数，相加之后再转回负二进制。瓶颈很明显：数组长度可达一千多位，$(-2)^{1000}$ 远远溢出 64 位整数，除非上大整数否则根本存不下，而上了大整数又要额外写一套负进制转换，反而更复杂。

换个角度观察：负二进制和普通二进制的区别只在权重的符号，而「对齐低位、逐位相加、把超出 0/1 范围的部分搬到高一位」这套框架是通用的。差别只在搬运的系数。普通二进制里，低位的 2 等于高一位的 1，所以多出的 2 往高位搬时系数是 $+1$；负二进制里，低一位的权重是 $(-2)^k$，高一位是 $(-2)^{k+1} = -2 \cdot (-2)^k$，所以低位多出的 2 只相当于高一位的 $-1$。搬运会带负号，这就是全部的特殊之处。

由此可以显式写出这个算法维护的不变量：设从右往左处理到第 $k$ 位，sum 表示「本位两数字之和加上从第 $k-1$ 位搬上来的量」，那么恒有「已经确定的低 $k+1$ 位所代表的值 + $carry \cdot (-2)^{k+1}$ = 两数在低 $k+1$ 位上的真实和」。要维持这个等式，本位必须取 bit = sum & 1（保证落在 {0,1} 内且和 sum 同奇偶），剩下的 sum - bit 是 2 的倍数，它等于 $(sum - bit) \cdot (-2)^k$，换算到第 $k+1$ 位就是 $-(sum - bit)/2$ 个单位，于是 carry = -(sum - bit) / 2。

还要确认 carry 不会发散。两个输入位最大各为 1，所以 sum 的取值范围受 carry 控制：只要 carry ∈ {-1, 0, 1}，sum 就落在 $[-1, 3]$ 内，代回公式算出的新 carry 依然落在 ${-1, 0, 1}$ 里（$sum=-1$ 时 bit=1、carry=1；$sum=3$ 时 bit=1、carry=-1；$sum=2$ 时 bit=0、carry=-1）。初始 carry=0 满足条件，所以整个过程中搬运量始终是这三个值之一，循环一定会终止。

解题步骤

  • 用两个下标 i、j 分别指向两个数组的末尾，也就是各自的最低位，另设 carry = 0。之所以从末尾开始，是因为题目的数组是高位在前，而搬运只能从低位流向高位，必须逆序扫描。
  • 循环条件写成 i >= 0 || j >= 0 || carry != 0。三个条件是「或」的关系，原因是短的数组先耗尽时长的还要继续，而两个都耗尽后残余的搬运量还会生成新的最高位，任何一条漏掉都会截断结果。
  • 每轮先令 sum = carry，再把还没越界的那一侧的当前位加进来。用 if (i >= 0) 守卫等价于「短数组的高位按 0 补齐」，省掉了真正去补零的预处理。
  • 取 bit = sum & 1 作为本位并追加到结果里，然后 carry = -(sum - bit) / 2。用按位与而不是取模，是因为 sum 可能是 -1，而 Java 和 Go 的 % 对负数返回负余数，-1 % 2 得 -1，会让本位变成非法的 -1；& 在补码下对 -1 直接得到 1，正是我们要的那个同奇偶的合法位。
  • 循环结束后，结果数组是低位在前的顺序，此时从尾部（对应最高位）开始裁剪多余的 0。裁剪循环的条件必须带上 size > 1，保证结果全零时仍留下一个 0，而不是退化成空数组。
  • 最后把低位在前的结果整体反转，得到题目要求的高位在前的输出。

以 arr1 = [1,1,1,1,1]、arr2 = [1,0,1] 走一遍。这两个数分别是 $16-8+4-2+1 = 11$ 和 $4+0+1 = 5$，和应为 16。初始 i=4、j=2、carry=0。第一轮 sum = 0 + arr1[4] + arr2[2] = 0 + 1 + 1 = 2，bit = 2 & 1 = 0，结果暂存 [0]，carry = -(2-0)/2 = -1；第二轮 i=3、j=1，sum = -1 + 1 + 0 = 0，bit = 0，结果 [0,0]，carry = 0；第三轮 i=2、j=0，sum = 0 + 1 + 1 = 2，bit = 0，结果 [0,0,0]，carry = -1；第四轮 i=1，arr2 已耗尽，sum = -1 + 1 = 0，bit = 0，结果 [0,0,0,0]，carry = 0；第五轮 i=0，sum = 0 + 1 = 1，bit = 1，结果 [0,0,0,0,1]，carry = 0。此时三个循环条件全部不成立，退出。尾部元素是 1，裁剪循环不执行，反转后得到 [1,0,0,0,0]，即 $(-2)^4 = 16$，与预期一致。注意第一轮的 carry 是 -1 而不是普通加法里的 +1，这正是负进制的体现。

代码实现

class Solution {
    // 进位可由 carry = -(sum - bit) / 2 得到。
    public int[] addNegabinary(int[] arr1, int[] arr2) {
        int i = arr1.length - 1;
        int j = arr2.length - 1;
        int carry = 0;

        List<Integer> res = new ArrayList<>();

        while (i >= 0 || j >= 0 || carry != 0) {
            int sum = carry;
            if (i >= 0) {
                sum += arr1[i--];
            }
            if (j >= 0) {
                sum += arr2[j--];
            }

            int bit = sum & 1;
            res.add(bit);
            carry = -(sum - bit) / 2;
        }

        while (res.size() > 1 && res.get(res.size() - 1) == 0) {
            res.remove(res.size() - 1);
        }

        int[] answer = new int[res.size()];
        for (int k = 0; k < res.size(); k++) {
            answer[k] = res.get(res.size() - 1 - k);
        }

        return answer;
    }
}

func addNegabinary(arr1 []int, arr2 []int) []int {
    // 进位可由 carry = -(sum - bit) / 2 得到。
    i := len(arr1) - 1
    j := len(arr2) - 1
    carry := 0

    res := make([]int, 0)

    for i >= 0 || j >= 0 || carry != 0 {
        sum := carry
        if i >= 0 {
            sum += arr1[i]
            i--
        }
        if j >= 0 {
            sum += arr2[j]
            j--
        }

        bit := sum & 1
        res = append(res, bit)
        carry = -(sum - bit) / 2
    }

    for len(res) > 1 && res[len(res)-1] == 0 {
        res = res[:len(res)-1]
    }

    for l, r := 0, len(res)-1; l < r; l, r = l+1, r-1 {
        res[l], res[r] = res[r], res[l]
    }

    return res
}

复杂度分析

  • 时间复杂度：$O(n)$，其中 $n$ 为两个数组长度的较大值。因为搬运量始终被限制在 ${-1,0,1}$ 内，主循环最多比 $n$ 多跑常数轮，裁剪和反转各扫一遍结果，都是线性的。
  • 空间复杂度：$O(n)$，凭的是除了长度不超过 $n+2$ 的结果容器外没有其他辅助结构，逐位相加只用了几个整型变量。

关键点总结

  • 进制转换类的题目，先把「低一位的一个单位等于高一位的多少」这条换算关系写清楚，进位系数就自然出来了：正二进制是 $+1$，负二进制是 $-1$，其他负进制同理套 $-(sum - bit)/base$。
  • 用 & 取本位而不是 %，是因为需要的是「与 sum 同奇偶且落在 {0,1} 的那个数」，而不是语言定义的余数。凡是中间量可能为负的取位操作，都要先问一句本语言的取模对负数是什么行为。
  • 循环条件把「两个输入都没走完」和「搬运未清空」并列，是所有加法类模拟题的通用写法，能一次性覆盖长度不等和最高位溢出两种情况，不需要额外的收尾代码。
  • 面试视角上，这题真正被考的是你能否当场推导出进位公式，而不是背下来。被问到时应该主动写出「$(-2)^{k+1} = -2 \cdot (-2)^k$，所以低位多出的 2 只值高位的 -1」这一步，再顺带说明 carry 的取值范围有界所以循环会终止，这两点讲到了基本就过了。
  • 前导零的裁剪要在反转之前做，并且必须保留最后一位。把「输出格式约束」当成算法的一部分单独处理，而不是混在主循环里，代码会清晰很多。

易错点总结

  • 错误写法：用 int bit = sum % 2; 取本位。用例 arr1 = [1]、arr2 = [1,1,1] 在中途会产生 sum = -1，此时 bit 变成 -1，结果数组里出现非法的 -1，且 carry 算成 $-(-1-(-1))/2 = 0$，高位直接丢失，输出的数值与正确答案不符。
  • 错误写法：把进位写成 carry = (sum - bit) / 2，漏掉负号。用例 arr1 = [1]、arr2 = [1] 应得 [1,1,0]（即 $4-2+0=2$），漏负号后会算成普通二进制的 [1,0]，被当成 $-2$，答案错误。
  • 错误写法：循环条件写成 while (i >= 0 && j >= 0)。用例 arr1 = [1,1,1,1,1]、arr2 = [1,0,1] 会在短数组耗尽时立刻停止，只输出低三位，前面的 1,1 被整个丢掉。
  • 错误写法：循环条件只写 while (i >= 0 || j >= 0)，忘了 carry != 0。用例 arr1 = [1]、arr2 = [1] 两位都处理完后仍有 carry = -1，这一轮不再执行，结果只剩 [0]，答案变成 0。
  • 错误写法：裁剪前导零时写成 while (res.size() > 0 && ...)。用例 arr1 = [0]、arr2 = [0] 会把唯一的 0 也裁掉，返回空数组，而题目要求返回 [0]。
  • 错误写法：忘记裁剪前导零直接反转返回。用例 arr1 = [1,1,1,1,1]、arr2 = [1,0,1] 中间会先在结果里堆出若干高位 0，输出成 [0,1,0,0,0,0] 之类带前导零的形式，判题按数组逐元素比较，直接判错。
  • 错误写法：只反转不裁剪，或者先反转再从头裁剪但没同步下标。用例 arr1 = [0]、arr2 = [1]，如果反转后误从数组头部裁掉 0，会把有效的低位一起裁掉，输出 [] 或错位结果。
  • 错误写法：在 sum += arr1[i--] 里把两侧的自减写成先减后取，比如 sum += arr1[--i]。用例 arr1 = [1,0]、arr2 = [1] 会跳过最低位直接读高位，第一轮就读到 arr1[0]，随后 i 变成 -1 提前退出，输出长度和数值都错。
  • 错误写法：为了「对齐」先把短数组用 0 补到和长数组一样长，但补在了数组末尾。用例 arr1 = [1,1,1]、arr2 = [1]，末尾补零相当于把 1 乘上了 $(-2)^2$，加数被篡改成 4，结果自然不对；补零只能补在高位一侧，也就是数组头部。
  • 错误写法：先把两个数组转成 long 再相加。用例是任意长度接近 1000 的输入，$(-2)^{999}$ 早已溢出，转换过程中数值回绕，输出的结果完全随机。

相似题目

题目 难度 考察点
2. 两数相加 中等 进位发生在链表节点之间，要边走边建新节点
43. 字符串相乘 中等 乘法的进位可能远大于 1，需先累加到位数组再统一归位
66. 加一 简单 只有一个加数，进位一旦为 0 就能提前收工
67. 二进制求和 简单 底数为正 2，进位恒为 0 或 1，可与本题对照体会符号
369. 给单链表加一 中等 单链表无法回退，要靠哨兵或定位最后一个非 9 节点
371. 两整数之和 中等 禁用加号，进位改由异或与左移迭代产生
415. 字符串相加 简单 主要噪声在字符与数值的来回转换，而非进位规则
445. 两数相加 II 中等 高位在前且不许反转链表，需要用栈对齐低位
989. 数组形式的整数加法 简单 一侧是普通整数，可以把它整体当作初始进位带入
LCR 002. 二进制求和 简单 用来练手写字符串拼接方向与结果反转