LeetCode 67. 二进制求和

约 4 分钟
文章信息 12 个分类 4 个标签
分类
LeetCode CodeTop 简单 未解决 10-20 面试经典 150 题 腾讯 字节 微软 亚马逊 拼多多 快手
标签
字符串 数学 位运算 模拟

题目描述

✅ 67. 二进制求和

image-20260928214544474

题意分析

把两个二进制字符串相加，返回和的二进制字符串。每串最多有 $10^4$ 位，不能先转成定长整数；直接逐位相加即可。两串长度可能不同，必须从最低位对齐。

解法：双指针模拟竖式加法

核心思路

[!blue]

竖式加法从低位算到高位，因为当前位只依赖两个输入位和低一位传来的进位。用 i、j 指向两串尚未处理的最低位，carry 保存传入当前位的进位；某串已经耗尽，就把它的当前位视为 0。

令 sum 为这三部分之和。二进制每满 2 向高位进 1，所以当前位写入 sum % 2，下一轮的进位为 sum / 2。输入位和进位都只可能是 0 或 1，因而 sum 最多为 3，新的进位仍然只有 0 或 1。

每轮确定一个结果位后，这一位就不会再受高位影响。只有两串均已耗尽且进位为 0，才算全部处理完；若还剩进位，循环会再写入一个最高位。缓冲区按低位到高位追加，最后反转一次便得到正常位序，也避免反复在字符串头部插入。

解题步骤

  1. 令 i、j 分别指向两个字符串的末尾，carry = 0。
  2. 当任一字符串还有字符，或仍有进位时继续循环。
  3. 先令 sum = carry，再累加尚未耗尽的输入位；取过数位的指针左移。
  4. 追加 sum % 2，令 carry = sum / 2，进入下一位。
  5. 循环结束后反转缓冲区并返回。两个输入都是 "0" 时，仍会处理一轮并返回 "0"。

代码实现

class Solution {
    public String addBinary(String a, String b) {
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        StringBuilder result = new StringBuilder(Math.max(a.length(), b.length()) + 1);

        // 输入耗尽后仍要处理最后进位，结果先按低位到高位生成。
        while (i >= 0 || j >= 0 || carry != 0) {
            int sum = carry;

            if (i >= 0) {
                sum += a.charAt(i--) - '0';
            }

            if (j >= 0) {
                sum += b.charAt(j--) - '0';
            }

            result.append(sum % 2);
            carry = sum / 2;
        }

        return result.reverse().toString();
    }
}

func addBinary(a string, b string) string {
    i, j, carry := len(a)-1, len(b)-1, 0
    result := make([]byte, 0, max(len(a), len(b))+1)

    // 输入耗尽后仍要处理最后进位，结果先按低位到高位生成。
    for i >= 0 || j >= 0 || carry != 0 {
        sum := carry
        if i >= 0 {
            sum += int(a[i] - '0')
            i--
        }
        if j >= 0 {
            sum += int(b[j] - '0')
            j--
        }
        result = append(result, byte(sum%2)+'0')
        carry = sum / 2
    }
    for left, right := 0, len(result)-1; left < right; left, right = left+1, right-1 {
        result[left], result[right] = result[right], result[left]
    }
    return string(result)
}

复杂度分析

  • 时间复杂度：$O(\max(m,n))$，其中 $m$、$n$ 是两串长度。逐位处理最多 $\max(m,n)+1$ 位，最后线性反转结果。
  • 空间复杂度：$O(\max(m,n))$，用于结果构造缓冲区和返回字符串；除此之外只用常数个变量。

关键点总结

[!green]

  • 字符串表示的大整数不能依赖定长整数类型，逐位运算才不受位数限制。
  • 循环条件必须包含 carry != 0，否则可能丢掉最高位进位。
  • 结果按低位到高位生成，统一反转比不断在字符串头部插入更高效。
  • 二进制中 sum 最大为 3，因此进位始终只有 0 或 1。

易错点总结

[!yellow]

  • 循环条件要用“任一字符串还有位，或还有进位”，只检查两串同时未耗尽会漏掉较长串的剩余位，忽略 carry 则会丢失最高位。
  • 忘记把字符减 '0'，会把字符编码当成数值参与计算。
  • 忘记反转，会得到位序颠倒的字符串。
  • 在循环中用 digit + result 头插字符串，会因反复复制退化为 $O(n^2)$。

相似题目

题目 难度 关联与区别
415. 字符串相加 简单 同样从低位向高位处理进位，原题为十进制字符串，本题进位基数为2。
43. 字符串相乘 中等 复用逐位累加与进位，乘法还要汇总不同位置的部分积。
2. 两数相加 中等 逐位计算并维护进位；本题按二进制位相加，该题链表低位在前可直接遍历相加。
445. 两数相加 II 中等 逐位计算并维护进位；本题按二进制位相加，该题高位在前需反转或栈辅助。
66. 加一 简单 逐位计算并维护进位；本题按二进制位相加，该题加一时只传播单次进位。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/69754249
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！