题目描述

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

样例1

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

样例2

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

算法

(模拟) $O(n)$

模拟人工进行二进制加法的过程。

假设输入的两个字符串是a和b。
为了简化代码，我们进行如下操作：

1. 如果a的长度小于b的长度，我们交换a和b；
2. 翻转a和b，使得每个二进制数的最低位存储在字符串第0个位置；

然后从低位到高位依次计算每一位，过程中需要记录前一位的进位。
如果最高位的进位是1，则需要在最高位的位置补上1。

时间复杂度分析：两个字符串遍历的次数是常数，所以总时间复杂度是 $O(n)$。

C++ 代码

class Solution {
public:
    string addBinary(string a, string b) {
        if (a.size() < b.size()) swap(a, b);
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        int t = 0;
        string res;
        int k = 0;
        while (k < b.size())
        {
            t += a[k] - '0' + b[k] - '0';
            res += to_string(t&1);
            t /= 2;
            k ++ ;
        }
        while (k < a.size()) //处理a超出b的部分
        {
            t += a[k] - '0';
            res += to_string(t&1);
            t /= 2;
            k ++ ;
        }
        if (t) res += '1';
        reverse(res.begin(), res.end());
        return res;
    }
};