67.二进制求和

【LetMeFly】67.二进制求和

力扣题目链接：https://leetcode.cn/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" ，就都不含前导零。

方法一：reverse

这里我对字符串进行了一个处理，先把字符串前后颠倒了一下顺序（123变成321)，计算后再颠倒回来。

这样做的目的是字符串往后添加比较容易（直接s += '0'即可），并且数位比较容易对齐（最低位的下标都变成了0）。当然你也可以选择不这么做，直接insert到前面也一样。

我们只需要用一个变量记录“进位”，初始值是0。

然后令a为长度长的数字，从0到a.size()枚举a的每一位，如果b也有对应的这一位，就加之。

• 时间复杂度$O(n)$，其中$n$是两个数字的最大长度
• 空间复杂度$O(1)$（没考虑reverse所消耗的空间）

AC代码

C++

class Solution {
public:
    string addBinary(string& a, string& b) {
        bool JinWei = false;
        if (a.size() < b.size())
            swap(a, b);
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        for (int i = 0; i < a.size(); i++) {
            int cnt = JinWei;
            cnt += a[i] - '0';
            if (i < b.size())
                cnt += b[i] - '0';
            a[i] = (cnt % 2) + '0';
            JinWei = cnt / 2;
        }
        if (JinWei)
            a += '1';
        reverse(a.begin(), a.end());
        return a;
    }
};

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/125793685