LeetCode 67. 二进制求和

题目描述

原题链接

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

数据范围

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

样例1：

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

样例2：

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

---

算法

(模拟)

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

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

• 如果a的长度小于b的长度，我们交换a和b；
• 翻转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;
        int k = 0;
        string res;
        while (k < b.size())
        {
            t += a[k] - '0' + b[k] - '0';
            res += to_string(t & 1);
            t /= 2;
            k ++ ;
        }

        while (k < a.size())
        {
            t += a[k] - '0';
            res += to_string(t & 1);
            t /= 2;
            k ++ ;
        }

        if (t) res += '1';
        reverse(res.begin(), res.end());
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31