Add Binary

67. 二进制求和

分析

字符串逆序遍历
- 为了方便从最低位到最高位逐位相加，首先将 a 和 b 字符串进行反转
逐位相加
- 维护进位变量 t，依次对 a 和 b 的每一位进行相加：
  - 若当前索引在 a 范围内，则加上 a[i] - '0'
  - 若当前索引在 b 范围内，则加上 b[i] - '0'
  - 将当前位结果 t % 2 转为字符加入结果字符串 c
  - 更新进位 t /= 2
处理多余进位
- 当遍历完两个字符串后，若仍有进位，则继续加入结果字符串
结果反转
- 将结果字符串 c 反转回正序，即为最终答案

时间复杂度

时间复杂度 O(max(m, n))，其中 m 和 n 分别为字符串 a 和 b 的长度

空间复杂度

空间复杂度为 O(max(m, n))

C++代码

 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


class Solution
{
public:
    string addBinary(string a, string b)
    {
        // 反转字符串以方便从低位开始计算
        std::reverse(a.begin(), a.end());
        std::reverse(b.begin(), b.end());

        std::string c;
        for (int i = 0, t = 0; i < a.size() || i < b.size() || t; ++i)
        {
            // 加上 a 和 b 当前位的数值
            if (i < a.size()) t += a[i] - '0';
            if (i < b.size()) t += b[i] - '0';

            // 当前位结果加入结果字符串
            c += t % 2 + '0';

            // 更新进位
            t /= 2;
        }

        // 反转回正序
        std::reverse(c.begin(), c.end());
        return c;
    }
};