LeetCode 67.二进制求和(简单)

题目描述:

给你两个二进制字符串，返回它们的和（用二进制表示）。输入为 非空 字符串且只包含数字 1 和 0 。

示例 1:

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

示例 2:

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

提示:

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

题目分析:

这道题其实是 LeetCode 415.字符串相加(简单) 的变种题，都是传入两个字符串参数返回其相加的结果字符串。这里还是采用模拟加法计算的方法，从右往左，循环相加两个字符串相同长度的低位数部分，再把进位加上，超过 2 就再进一位，三个数的和对 2 取余即为该位最终的结果，依此类推。如果两个字符串长度不同，则把长度较长的那个字符串剩余部分补上。如果最后两数每位都计算完了进位值还为一，则在最后补上一个进位一。下面的题解同样使用了缓冲区存放结果，当然你也可以把题解中的三个循环整合一下，把它们放在同一个循环里，对相同长度低位数部分和较长字符串的剩余部分一并进行计算。但最后记得把结果反转过来，你也可以使用栈结构，最后依次弹出即可。

题解:

执行用时: 2 ms

内存消耗: 37.5 MB

class Solution {
    public String addBinary(String a, String b) {
        // 双指针索引 以及 进位标志
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        // 字符串缓冲区
        StringBuilder builder = new StringBuilder();
        // 循环相加两个字符串相同长度的低位数部分
        while (i >= 0 && j >= 0) {
            // 计算当前位的和 包含进位
            int sum = carry;
            sum += a.charAt(i) - '0';
            sum += b.charAt(j) - '0';
            // 除法取整得进位值
            carry = sum / 2;
            // 取余得结果当前位的值 放入缓冲区
            builder.append(sum % 2);
            // 继续计算下一位
            --i;
            --j;
        }
        // 如果 a 串比 b 串长，则继续遍历添加 a 的剩余部分
        while (i >= 0) {
            int sum = carry + a.charAt(i--) - '0';
            carry = sum / 2;
            builder.append(sum % 2);
        }
        // 如果 b 串比 a 串长，则继续遍历添加 b 的剩余部分
        while (j >= 0) {
            int sum = carry + b.charAt(j--) - '0';
            carry = sum / 2;
            builder.append(sum % 2);
        }
        // 如果计算完进位为 1 需要补充进位数
        if (carry == 1) {
            builder.append(carry);
        }
        // 对缓冲区字符串反转得结果
        return builder.reverse().toString();
    }
}

题目来源:力扣(LeetCode)