力扣第 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 取当前位，或 0
        int bitB = (lenB >= 0) ? b[lenB--] - '0' : 0; // 从 b 取当前位，或 0
        int 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"