二进制求和

给你两个二进制字符串，返回它们的和（用二进制表示）。

输入为非空字符串且只包含数字 1 和 0。

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

输入：a = "1010", b = "1011"
输出：“10101”

方法：模拟

算法思路：

设置变量carry记录上一个位置的进位，初始值为0
使用StringBuilder拼接字符串，a、b从后往前遍历，最后将StringBuilder反转

代码实现：

class Solution {
    public String addBinary(String a, String b) {
        int carry = 0;
        StringBuilder sb = new StringBuilder();
        int i = a.length() - 1;
        int j = b.length() - 1;
        while(i >= 0 || j >= 0 || carry == 1){
            if(i >= 0 && a.charAt(i--) == '1'){				//此处i--不能置于循环内，不然可能无法执行
                carry++;
            }
            if(j >= 0 && b.charAt(j--) == '1'){
                carry++;
            }
            sb.append(carry % 2);
            carry /= 2;
        }
        return sb.reverse().toString();
    }
}

复杂度分析：

时间复杂度： $O(n)$ ，这里的时间复杂度来源于顺序遍历 $a$ 和 $b$ 。

空间复杂度： $O(1)$ ，除去答案所占用的空间，这里使用了常数个临时变量。

参考

LeetCode题解-二进制求和

LeetCode 题解 - 数学｜CS-Notes

二进制求和

方法： 模拟

参考

方法：模拟