代码训练LeetCode(12)二进制求和-Toy模板网

这篇具有很好参考价值的文章主要介绍了代码训练LeetCode(12)二进制求和。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

代码训练(12)LeetCode之二进制求和

Author: Once Day Date: 2024年3月14日

一位热衷于Linux学习和开发的菜鸟，试图谱写一场冒险之旅，也许终点只是一场白日梦…

漫漫长路，有人对你微笑过嘛…

全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客

参考文章:

67. 二进制求和 - 力扣（LeetCode）

力扣 (LeetCode) 全球极客挚爱的技术成长平台

1. 原题

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

例如，输入a=111，b=1，输出结果为1000。

2. 分析

二进制加法本质上和十进制加法相似，只不过它只包含两个数字：0和1。在二进制加法中，我们需要考虑以下几种情况：

0 + 0 = 0
1 + 0 = 1 或者 0 + 1 = 1
1 + 1 = 10 （这里1需要进位）

我们可以使用一个指针从两个字符串的末尾开始向前遍历，模拟手工加法的过程。同时，我们需要一个变量carry来记录进位。对于每一对位，我们需要计算它们的和再加上carry，然后更新carry。如果carry在处理完所有位之后仍然为1，我们需要在结果前面再加上一个’1’。

分析步骤：

对齐字符串：确保两个字符串等长，可以在较短的字符串前面补0。
初始化进位carry为0。
从字符串的最后一个字符开始，向前遍历。
对每一位进行加法运算，并更新进位carry。
如果遍历完后carry仍为1，则在结果前面添加一个’1’。
返回结果字符串。

例如，假设我们有两个二进制字符串a = "1010"和b = "1011"。

结果初始化为空字符串result = ""，进位carry = 0。
从最右边开始，0 + 1 = 1，result = "1"，carry = 0。
接着，1 + 1 = 10，result = "01"，carry = 1。
再次，0 + 0 + carry(1) = 1，result = "101"，carry = 0。
最后，1 + 1 + carry(0) = 10，result = "0101"，carry = 1。
因为carry为1，所以在result前面加上一个’1’，得到result = "10101"。

性能优化关键点：

内存管理：由于我们需要动态地创建一个新字符串来保存加法结果，使用malloc进行内存分配，因此在使用完毕后，应当使用free释放内存，以避免内存泄露。
字符串操作：在进行字符串操作时，我们计算了字符串长度，并且从后向前进行遍历，避免了不必要的字符串复制或移动，这有助于提高代码的执行效率。

3. 代码实现

char *addBinary(char *a, char *b) {
    int len_a = strlen(a);
    int len_b = strlen(b);
    int max_len = len_a > len_b ? len_a : len_b;

    // 结果字符串长度可能会比输入长1，所以需要加2（一个额外的字符和一个结束符'\0'）
    char *result = (char *)malloc(max_len + 2);

    int carry = 0; // 进位
    int i = len_a - 1, j = len_b - 1, k = max_len;

    result[k + 1] = '\0'; // 设置字符串结束符

    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) sum += a[i--] - '0'; // 将字符转换为数字并加到sum
        if (j >= 0) sum += b[j--] - '0';
        result[k--] = (sum % 2) + '0'; // 计算当前位的结果，并将数字转换为字符
        carry = sum / 2; // 计算新的进位
    }

    if (carry) {
        result[k--] = '1';
    }

    return result + k + 1; // 返回正确的结果字符串起始位置
}

这段代码实现了一个函数 addBinary，用于将两个二进制字符串 a 和 b 相加，并返回相加的结果。函数的主要逻辑如下：

计算输入字符串 a 和 b 的长度，分别存储在变量 len_a 和 len_b 中。
确定结果字符串的最大长度 max_len，取 len_a 和 len_b 的较大值。
动态分配结果字符串 result 的内存空间，长度为 max_len + 2。额外的两个字符是为了存储可能的进位和字符串结束符 '\0'。
初始化变量 carry 为 0，表示进位；i、j、k 分别表示字符串 a、b 和 result 的当前位置，初始值分别为 len_a - 1、len_b - 1 和 max_len。
设置结果字符串的结束符 '\0'。
使用 while 循环从右到左遍历字符串 a 和 b，同时考虑进位的情况：
- 计算当前位的和 sum，初始值为进位 carry。
- 如果 i 和 j 还没有越界，将对应位置的字符转换为数字并加到 sum 中。
- 计算当前位的结果，即 sum % 2，并将数字转换为字符存储在 result[k] 中。
- 计算新的进位 carry，即 sum / 2。
- 更新指针 i、j、k 的位置。
循环结束后，如果还有进位，将进位添加到结果字符串的最高位。
返回结果字符串的正确起始位置，即 result + k + 1。