题目内容

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

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

示例

示例 1:

输入: a = “11”, b = “1”
输出: “100”

示例 2:

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

提示

1、每个字符串仅由字符 ‘0’ 或 ‘1’ 组成。
2、1 <= a.length, b.length <= 10^4
3、字符串如果不是 “0” ，就都不含前导零。

题解

本题和十进制求和的方法类似，将个位放在前面，所以刚开始需要反转一下数组。然后，有如下求解步骤：

1、求每一位的和S = 进位 + A[i] + B[i]，且当A或者B越界时，去掉对应的部分即可。

2、再求每一位应该填的数 = S % 2

3、最后求每一位的进位 = S / 2

注意：我们要将字符串转化为对应的int值，所以需要减掉字符串的’0’。

具体，看代码即可。

代码

class Solution {
public:
    string addBinary(string a, string b) {
        //二进制和十进制类似
        //第i位的值 = (进位 + a[i] + b[i]) % 2，
        //i + 1的进位 = (进位 + a[i] + b[i]) / 2
        reverse(a.begin(),a.end());
        reverse(b.begin(),b.end());

        string c;
        //当i小于a或b的大小或者有进位的时候进行循环
        for(int i = 0, t = 0; i < a.size() || i < b.size() || t; i++){
            if(i < a.size()) t += a[i] - '0';
            if(i < b.size()) t += b[i] - '0';
            c += to_string(t % 2);
            t /= 2;
        }

        reverse(c.begin(),c.end());
        return c;
    }
};