刷题-力扣-67. 二进制求和

67. 二进制求和

题目链接

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-binary/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目描述

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

示例 1:

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

示例 2:

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

提示：

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

题目分析

1. 根据题目描述计算两个二进制字符串的和
2. 运用逢二进一的原则，倒叙遍历两个字符串
3. 使用flag记录进位的数字

代码

class Solution {
public:
    string addBinary(string a, string b) {
        if (a == "") return b;
        if (b == "") return a;
        int pa = a.length() - 1;
        int pb = b.length() -1;
        int flag = 0;
        string sum = "";
        while (pa >= 0 || pb >= 0) {
            if (pa >= a.length()) {
                if (b[pb] == '0') {
                    sum.push_back(flag ? '1' : '0');
                    flag = 0;
                }
                else sum.push_back(flag ? '0' : '1');
                --pb;
            } else if (pb >= b.length()) {
                if (a[pa] == '0') {
                    sum.push_back(flag ? '1' : '0');
                    flag = 0;
                }
                else sum.push_back(flag ? '0' : '1');
                --pa;
            } else {
                if (flag) {
                    if (a[pa] == '1' && b[pb] == '1') sum.push_back('1');
                    else if (a[pa] == '0' && b[pb] == '0') {
                        sum.push_back('1');
                        flag = 0;
                    } else sum.push_back('0');
                } else {
                    if (a[pa] == '1' && b[pb] == '1') {
                        sum.push_back('0');
                        flag = 1;
                    } else sum.push_back(a[pa] == '1' ? a[pa] : b[pb]);
                }
                --pa;
                --pb;
            }
        }
        if (flag) sum.push_back('1');
        reverse(sum.begin(), sum.end());
        return sum;
    }
};