67.二进制求和

LeetCode LeetCode 字符串数学位运算模拟

发布时间 : 2000-01-10 00:06

字数:1.2k 阅读 :

评论:

67.二进制求和

67.二进制求和

67.1 题目

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

示例 1：

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

示例 2：

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

提示：

1 <= a.length, b.length <= 10^4
a 和 b 仅由字符 '0' 或 '1' 组成
字符串如果不是 "0"，就不含前导零

67.2 题解

方法一：逐位相加

思路

从两个字符串的末尾开始，逐位相加，模拟二进制加法。维护进位 carry，初始为0。每次计算当前位的和：sum = aVal + bVal + carry，当前位结果为 sum % 2，新的进位为 sum / 2。使用 StringBuilder 在头部插入结果，最后处理最高位的进位。

核心思想：模拟二进制加法，从低位到高位逐位处理。

具体步骤：

初始化索引指向两个字符串末尾，进位 carry = 0。
循环直到两个字符串都处理完：
- 取当前位的值（超出范围取0）
- 计算当前位和：sum = aVal + bVal + carry
- 更新进位：carry = sum / 2
- 插入当前位结果：sum % 2
如果最高位有进位，插入 ‘1’。

举例：对于 a = "11", b = "1"：

i=1, j=0：aVal=1, bVal=1，sum=2，结果 "0"，carry=1
i=0, j=-1：aVal=1, bVal=0，sum=2，结果 "00"，carry=1
i=-1：有进位，插入 ‘1’，结果 "100"

复杂度分析

时间复杂度：O(max(m, n))，遍历较长的字符串。
空间复杂度：O(max(m, n))，存储结果字符串。

代码

// 方法一：逐位相加
// 从字符串末尾开始逐位相加，模拟二进制加法过程，注意进位的处理
static string AddBinary1(string a, string b)
{
    // 初始化两个索引 i 和 j 分别指向字符串 a 和 b 的末尾
    int aIndex = a.Length - 1;
    int bIndex = b.Length - 1;

    // 初始化进位值为 0
    int carry = 0;

    // 创建一个 StringBuilder 用于保存二进制相加的结果
    StringBuilder stringBuilder = new StringBuilder();

    // 循环直到两个字符串全部处理完毕且进位为 0
    while (aIndex >= 0 || bIndex >= 0)
    {
        // 获取当前位置的二进制值，如果索引超出字符串范围则默认为 0
        int aNowValue = (aIndex >= 0) ? a[aIndex--] - '0' : 0;
        int bNowValue = (bIndex >= 0) ? b[bIndex--] - '0' : 0;

        // 计算当前位的和以及进位值
        int sum = aNowValue + bNowValue + carry;
        carry = sum / 2;

        // 在结果的开头插入当前位的二进制值
        stringBuilder.Insert(0, sum % 2);
    }

    // 如果最高位有进位，将 '1' 插入结果的开头
    if (carry > 0)
    {
        stringBuilder.Insert(0, '1');
    }

    // 将 StringBuilder 转换为 string 并返回结果
    return stringBuilder.ToString();
}

67.3 代码

using System;
using System.Text;

class Program
{
    static void Main()
    {
        #region 题目

        // 给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
        // 示例 1：
        // 输入:a = "11", b = "1"
        // 输出："100"
        // 示例 2：
        // 输入：a = "1010", b = "1011"
        // 输出："10101"
        // 提示：
        // 1 <= a.length, b.length <= 104
        // a 和 b 仅由字符 '0' 或 '1' 组成
        // 字符串如果不是 "0" ，就不含前导零

        #endregion

        #region 测试

        // 示例 1
        string a1 = "11", b1 = "1";
        string result1_1 = AddBinary1(a1, b1);
        Console.WriteLine($"示例1 方法1 输出：{result1_1}");


        // 示例 2
        string a2 = "1010", b2 = "1011";
        string result2_1 = AddBinary1(a2, b2);
        Console.WriteLine($"示例2 方法1 输出：{result2_1}");

        #endregion
    }

    #region 答案

    // 方法一：逐位相加
    // 从字符串末尾开始逐位相加，模拟二进制加法过程，注意进位的处理
    static string AddBinary1(string a, string b)
    {
        // 初始化两个索引 i 和 j 分别指向字符串 a 和 b 的末尾
        int aIndex = a.Length - 1;
        int bIndex = b.Length - 1;

        // 初始化进位值为 0
        int carry = 0;

        // 创建一个 StringBuilder 用于保存二进制相加的结果
        StringBuilder stringBuilder = new StringBuilder();

        // 循环直到两个字符串全部处理完毕且进位为 0
        while (aIndex >= 0 || bIndex >= 0)
        {
            // 获取当前位置的二进制值，如果索引超出字符串范围则默认为 0
            int aNowValue = (aIndex >= 0) ? a[aIndex--] - '0' : 0;
            int bNowValue = (bIndex >= 0) ? b[bIndex--] - '0' : 0;

            // 计算当前位的和以及进位值
            int sum = aNowValue + bNowValue + carry;
            carry = sum / 2;

            // 在结果的开头插入当前位的二进制值
            stringBuilder.Insert(0, sum % 2);
        }

        // 如果最高位有进位，将 '1' 插入结果的开头
        if (carry > 0)
        {
            stringBuilder.Insert(0, '1');
        }

        // 将 StringBuilder 转换为 string 并返回结果
        return stringBuilder.ToString();
    }

    #endregion
}

67.4 运行结果

示例1 方法1 输出：100
示例2 方法1 输出：10101

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com