力扣第 67 题 “二进制求和”

题目描述

给你两个二进制字符串 a 和 b，以二进制字符串的形式返回它们的和。

示例 1:

输入: a = "11", b = "1"
输出: "100"

示例 2:

输入: a = "1010", b = "1011"
输出: "10101"

提示:

1. 每个字符串仅由字符 '0' 或 '1' 组成。
2. 每个字符串都不会包含前导零，除了 “0” 本身。
3. $1\le a.length,b.length\le 10^4$。

---

解决方案

可以通过模拟二进制加法的规则，从两个字符串的尾部开始逐位相加，记录进位，并生成结果字符串。

核心思路

1. 使用双指针分别从字符串 a 和 b 的末尾向前遍历。
2. 每次取出当前指针指向的字符（或 0 如果指针超出范围），将其转换为整数并求和，同时加上进位。
3. 将求和的结果取模 (2) 得到当前位，将其加入结果字符串；将求和结果整除 (2) 得到进位。
4. 如果遍历结束后进位为 (1)，需要在结果字符串前追加一个 1。
5. 返回结果字符串的反转。

---

C 语言实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>char* addBinary(char* a, char* b) {int lenA = strlen(a); // 字符串 a 的长度int lenB = strlen(b); // 字符串 b 的长度int maxLength = (lenA > lenB ? lenA : lenB) + 1; // 可能的最大长度（考虑进位）char* result = (char*)malloc((maxLength + 1) * sizeof(char)); // 分配结果字符串result[maxLength] = '\0'; // 设置字符串结尾符int carry = 0; // 进位标志int index = maxLength - 1; // 结果字符串的末尾索引// 从末尾向前逐位相加lenA--;lenB--;while (lenA >= 0 || lenB >= 0 || carry > 0) {int bitA = (lenA >= 0) ? a[lenA--] - '0' : 0; // 从 a 取当前位，或 0int bitB = (lenB >= 0) ? b[lenB--] - '0' : 0; // 从 b 取当前位，或 0int sum = bitA + bitB + carry; // 当前位求和result[index--] = (sum % 2) + '0'; // 当前位结果carry = sum / 2; // 更新进位}// 如果有多余的 0，在前面移动结果字符串指针return result + index + 1;
}int main() {char a[] = "1010";char b[] = "1011";char* result = addBinary(a, b);printf("结果: %s\n", result);// 因为结果可能有偏移，需要用原始地址释放free(result - strlen(result));return 0;
}

---

代码说明

1. 双指针遍历

   • 使用 lenA 和 lenB 作为指针从 a 和 b 的末尾向前移动。
   • 对于超出长度范围的位，默认取 (0)。

2. 进位处理

   • 用 carry 记录进位。
   • 在当前位的求和结果中，模 (2) 的余数是当前位的值，整除 (2) 的商是进位。

3. 动态分配结果字符串

   • 最大可能长度为 $\max (lenA,lenB)+1$。
   • 结果字符串存储的数字从低位开始，需要最终返回反转后的字符串。

4. 字符串偏移

   • 由于可能有多余的 0，返回结果时调整指针位置。
     好，让我们举一个例子，其中 index 在计算完成后 不等于 -1。这是因为在某些情况下（例如没有进位且结果比输入字符串短），index 的值会大于 -1。

---

计算过程

如果输入为：

a = "10", b = "01"

1. 初始化:

   • lenA = 2, lenB = 2。
   • maxLength = 3，分配 result 为 [_, _, _]。
   • index = 2。

2. 逐步相加:

   • 第一位：bitA = 0, bitB = 1，sum = 0 + 1 + 0 = 1，result[2] = 1，index = 1。
   • 第二位：bitA = 1, bitB = 0，sum = 1 + 0 + 0 = 1，result[1] = 1，index = 0。
   • 没有进位，结束。

3. 最终结果:

   • result = [_, 1, 1]，index = 0。
   • 返回 result + index + 1，即 result + 1，输出 "11"。

---

复杂度分析

• 时间复杂度: $O(\max (lenA,lenB))$，需要逐位遍历较长的字符串。
• 空间复杂度: $O(\max (lenA,lenB))$，存储结果字符串的空间。

---

测试示例

输入: a = "11", b = "1"
输出: "100"输入: a = "1010", b = "1011"
输出: "10101"输入: a = "0", b = "0"
输出: "0"