题目

Given two binary strings a and b, return their sum as a binary string.

思考

题外话：根据LeetCode premium的说法，这题是no.4最常被Facebook面试问到的题目

这题是二进制相加的问题

什么是二进制

二进制是一种计数系统，基于数字 0 和 1。与十进制每10进1不同，二进制每2进1
二进制：0 -> 1 -> 10 就对应着十进制：0 -> 1 -> 2

难点

在解决这道问题时，个人觉得难点在于如何进位，其中包括了前进一位时，当前位归零，记录进位到下一位的运算，在代码实现时都让我有点卡顿

解决

首先，对于两个二进制相加，肯定要从最末尾的一位开始，而两个数字长度未必相同
所以我们先初始化两个指针分别指向两个数字String a和 String b的末尾
int countA = a.length() - 1;
int countB = b.length() - 1;

然后我们用sum和carry分别记录当前位、下一位的情况
有这么些情况：

sum = 0，那么向结果String res加入0，carry也为0;
sum = 1, 那么 res.append(1), carry = 0;
sum = 2, res.append(0), carry = 1;
sum = 3, res.append(1), carry = 1;
以上就是进位逻辑

最后不要忘记将进位也加入结果，如果carry不是0，那就加入结果
然后逆向输出

代码

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder res = new StringBuilder();
        int countA = a.length() - 1;
        int countB = b.length() - 1;
        int carry = 0;
        while(countA >= 0 || countB >= 0) {
            int sum = carry;
            if (countA >= 0) sum += a.charAt(countA--) - '0';
            if (countB >= 0) sum += b.charAt(countB--) - '0';
            carry = sum > 1 ? 1 : 0;
            res.append(sum%2);
        }
        if (carry != 0) {res.append(carry);}
        return res.reverse().toString();
    }
}