67.二进制求和

题目:67.二进制求和

给你两个二进制字符串 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" ，就不含前导零

思路

可以通过逐位相加两个二进制字符串的方法来解决这个问题。这里的关键在于处理二进制加法中的进位问题。我们可以从两个字符串的最后一位开始向前进行加法运算，同时考虑进位，最后将结果逆序输出。

1. 初始化变量：

   • i 指向字符串 a 的末尾，j 指向字符串 b 的末尾。
   • carry 代表进位，初始化为 0。
   • result 是存储计算结果的字符串。

2. 逐位相加：

   • 对应位置的数字相加，并加上上次相加的 carry。
   • 将相加的结果对 2 取余得到当前的值，并将 carry 更新为相加结果除以 2 的值（即进位），直到两个字符串都遍历完。

3. 处理剩余进位：

   • 在循环结束后，如果 carry 仍然不为 0，则将 carry 添加到结果。

4. 返回结果：

   • 由于加法是从最低位开始的，因此需要将结果字符串反转后返回。

• 时间复杂度:O(max(m,n))
• 空间复杂度:O(max(m,n))

代码

public String addBinary(String a, String b) {
    StringBuilder result = new StringBuilder();
    int i = a.length() - 1;
    int j = b.length() - 1;
    int carray = 0;
    int sum;
    while (i >= 0 || j >= 0) {
        int x = 0;
        int y = 0;
        if (i >= 0) {
            // 将 a 的当前位置的二进制数转换为整数
            x = a.charAt(i) - '0';
            i--;
        }
        if (j >= 0) {
            // 将 b 的当前位置的二进制数转换为整数
            y = b.charAt(j) - '0';
            j--;
        }
        // 对应位置的数字相加，并加上上次相加的 carry。
        sum = x + y + carray;
        // 将相加的结果对 2 取余得到当前的值
        result.append(sum % 2);
        carray = sum / 2;
    }
    // 如果最后还有进位，追加到结果中
    if (carray > 0) {
        result.append(carray);
    }
    // 翻转结果字符串并返回
    return result.reverse().toString();
}