LeetCode LCR 002. 二进制求和

约 7 分钟
文章信息 5 个分类 5 个标签
分类
LeetCode 简单 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
字符串 数学 LCR 位运算 模拟
目录

题目描述

✅ LCR 002. 二进制求和

题意分析

给两个只含 '0'、'1' 的字符串 a 和 b，把它们当作二进制非负整数相加，返回同样以字符串表示的和。

输入用字符串给出而不是整数，这本身就是最强的信号：长度可以到 $10^4$ 量级，远远超过 long 甚至 __int128 能容纳的范围，所以「先转成整数、加完再转回去」的路根本走不通。必须在字符表示上直接完成加法。

两个串的长度可以不同，且低位在末尾、高位在开头。人手算竖式时是从右往左对齐、逐位相加并向左传递进位，代码要做的就是把这套竖式机械化：需要一个能表示「当前位的和」以及「要带到更高位去的量」的状态。

边界集中在三处：两串长度不等时，短的那一串在高位要按 $0$ 补齐；最高位相加还可能再产生一个进位，这个进位必须成为结果的新首位（1 + 1 = 10）；以及结果是从低位往高位生成的，最后必须反转，否则得到的是逆序串。题目保证输入非空且无前导零，所以不用额外做清洗。

解法：位运算压缩状态

核心思路

直接照搬竖式：从两个字符串的末尾同时往前走，每一步把「a 的当前位 + b 的当前位 + 上一步留下的进位」加在一起。这个和最多是 $1 + 1 + 1 = 3$，所以本位写 sum % 2，向上传 sum / 2（在二进制下就是 sum & 1 和 sum >> 1）。

关键的状态只有一个：carry 表示「已经处理完的低位部分，还欠更高位多少个单位」。把它设计成循环变量而不是布尔标志，好处是可以用 carry += ... 的写法把「加低位进位」和「加两个操作数」合成一句，取模、整除两步就同时算出了本位与新进位。

真正让代码变短的技巧是循环条件写成 i >= 0 || j >= 0 || carry > 0。它一次性统一了三件事：两串长度不等时短串越界后按 $0$ 处理、长串继续单独往前走、以及最高位溢出的那个额外进位。于是整段代码不需要任何补零预处理，也不需要循环结束后的收尾判断。

不变量是：每轮循环开始时，answer 里已经写好的字符恰好是最终结果的最低若干位（逆序存放），而 carry 是这部分之外还欠上层的量。当三个条件同时不成立，说明两个串都走完且不再欠进位，答案就完整了。

因为是从低位往高位追加的，最终必须反转一次。反转比每次往头部插入要好——后者在数组/StringBuilder 上是 $O(n)$ 的搬移，整体会退化成 $O(n^2)$。

解题步骤

  • 两个下标各自指向串尾：i = a.length() - 1、j = b.length() - 1。从低位起算是竖式的前提，进位只能由低往高传。
  • 循环条件写 i >= 0 || j >= 0 || carry > 0，三者是「或」的关系。用「或」而不是「与」，才能让短串走完后长串继续；带上 carry > 0，才能让最高位的进位自然变成结果的新首位。
  • 取位时判断是否越界：i >= 0 ? a.charAt(i) - '0' : 0。越界补 $0$ 等价于在高位补零对齐，省掉了预处理。
  • 用 carry += ... 累加：carry 进入循环体时是上一轮遗留的进位，累加完两个操作数后它临时变成了「本位的总和」，取值范围 $0$ 到 $3$。
  • 本位写 carry % 2，然后 carry /= 2。顺序不能反：先取模拿到本位，再整除把 carry 恢复成「进位」的语义。这两行结束后 carry 只可能是 $0$ 或 $1$。
  • 下标同步递减：--i, --j 放在循环的步进部分，越界后继续变负也不影响，因为取位处已经判过。
  • 收尾反转再转成字符串。整个过程只做一次 $O(n)$ 反转。

以 a = "1010"（十进制 $10$）、b = "1011"（十进制 $11$）走一遍，期望结果 $21$ 即 "10101"。初始 i = j = 3、carry = 0、缓冲区为空。第一轮：carry = 0 + 0 + 1 = 1，写下 1，carry = 0，缓冲区 "1"，下标变 $2$。第二轮：carry = 0 + 1 + 1 = 2，写下 0，carry = 1，缓冲区 "10"，下标变 $1$。第三轮：carry = 1 + 0 + 0 = 1，写下 1，carry = 0，缓冲区 "101"，下标变 $0$。第四轮：carry = 0 + 1 + 1 = 2，写下 0，carry = 1，缓冲区 "1010"，下标变 $-1$。此时 i、j 都越界，但 carry > 0 仍成立，于是第五轮：两侧都补 $0$，carry = 1，写下 1，carry = 0，缓冲区 "10101"。三个条件全部不成立，循环退出，反转得到 "10101" —— 最高位那个 1 正是靠 carry > 0 这一项才被写进去的。

代码实现

class Solution {
    public String addBinary(String a, String b) {
        var sb = new StringBuilder();
        int i = a.length() - 1, j = b.length() - 1;
        // carry 进入循环体时是上一轮的进位，累加后临时充当本位总和。
        for (int carry = 0; i >= 0 || j >= 0 || carry > 0; --i, --j) {
            carry += (i >= 0 ? a.charAt(i) - '0' : 0) + (j >= 0 ? b.charAt(j) - '0' : 0);
            sb.append(carry % 2);
            carry /= 2;
        }
        // 结果是从低位往高位追加的，最后统一反转一次。
        return sb.reverse().toString();
    }
}

func addBinary(a string, b string) string {
    i, j := len(a)-1, len(b)-1
    answer := []byte{}
    for carry := 0; i >= 0 || j >= 0 || carry > 0; i, j = i-1, j-1 {
        if i >= 0 {
            carry += int(a[i] - '0')
        }
        if j >= 0 {
            carry += int(b[j] - '0')
        }
        answer = append(answer, byte(carry%2+'0'))
        carry /= 2
    }
    for i, j := 0, len(answer)-1; i < j; i, j = i+1, j-1 {
        answer[i], answer[j] = answer[j], answer[i]
    }
    return string(answer)
}

复杂度分析

  • 时间复杂度：$O(\max(m, n))$，其中 $m$、$n$ 是两串长度。循环次数至多是较长串的长度加一（那个额外的最高位进位），每轮只做常数次算术；末尾的反转也是一次线性扫描。
  • 空间复杂度：$O(\max(m, n))$，全部来自存放结果的缓冲区，长度不会超过较长串加一。除此之外只有 i、j、carry 三个标量，不随输入增长。

关键点总结

  • 输入以字符串给出数值，几乎总是在说「数值超出内建整型」，此时必须在表示层做竖式，而不是先解析成数字。
  • 把进位设计成整数累加器而非布尔量，能让「加进位 / 出本位 / 出新进位」压缩成三行无分支的代码，换成十进制、三十六进制也只需改掉那个模数。
  • i >= 0 || j >= 0 || carry > 0 这个「三或」条件是进位模拟题的通用骨架，它把长度不等、末位进位两类边界一起吞掉，是这类题最值得背下来的一行。
  • 结果逆序生成、最后统一反转，是为了避免每次头插带来的 $O(n)$ 搬移；这条在字符串构造类题目里普遍适用。
  • 面试视角：这道题面试官真正看的是「你会不会漏掉最高位进位」和「你会不会为长度对齐写一堆补零代码」。写完后主动说一句「1 + 1 这种输入靠 carry > 0 这一项覆盖」，比让面试官自己举反例要好；如果被追问推广，能立刻说出「把 2 换成 10 就是 415 题、换成 36 就是三十六进制加法」是加分项。

易错点总结

  • 错误写法：循环条件写成 i >= 0 && j >= 0。输入 a = "1", b = "1011" 时短串走完就退出，返回 "0"，长串剩下的高位全部丢失。
  • 错误写法：循环条件漏掉 carry > 0。输入 a = "1", b = "1" 时下标走完即退出，返回 "0" 而不是 "10"，最高位的进位被吃掉。
  • 错误写法：先写 carry /= 2 再写 sb.append(carry % 2)。输入 a = "1", b = "1" 时本位写成了 $0$ 之后的进位值，结果变成 "11"。
  • 错误写法：把 carry 声明成 boolean 并用 if (carry) sum++。看似等价，但一旦推广到十进制（415 题）就必须整体重写；更常见的连带错误是忘记在写完本位后把它复位，导致 a = "1010", b = "1011" 得到全 1 的串。
  • 错误写法：忘记最后的反转。输入 a = "1", b = "11" 的正确答案是 "100"，漏掉反转会返回 "001"。注意用回文式的用例（如 "1010" + "1011" = "10101"）自测根本发现不了这个 bug，必须挑非回文的答案来验。
  • 错误写法：用 sb.insert(0, ...) 代替追加加反转。功能正确但每次插入都要整体搬移，长度 $10^4$ 时退化成 $O(n^2)$，大数据点会超时。
  • 错误写法：取位时写 a.charAt(i) 而不减 '0'。字符 '0' 的码值是 $48$，carry 会瞬间变成几十，carry % 2 输出的位与真实值无关。
  • 错误写法：为了对齐先把短串用 String 拼接补零。在长度 $10^4$ 下逐次拼接同样是 $O(n^2)$，而且补零逻辑本身还容易多补或少补一位。

相似题目

题目 难度 考察点
67. 二进制求和 简单 与本题同题，可直接套用同一份「三或」循环
415. 字符串相加 简单 底数换成 $10$，模数与除数从 $2$ 改成 $10$，其余骨架不变
66. 加一 简单 只加 $1$，进位一旦为零就能提前退出，全 $9$ 时需扩容一位
989. 数组形式的整数加法 简单 一侧是数组一侧是整数，进位要和 k 的剩余部分一起累加
43. 字符串相乘 中等 乘法要先按下标 i + j + 1 落位再统一处理进位，还需去前导零
1073. 负二进制数相加 中等 基数是 $-2$，进位可能为 $-1$，需要额外的借位规则