LeetCode 67. 二进制求和

题目描述

原题链接

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

数据范围

• 1 < = a . l e n g t h , b . l e n g t h < = 1 0 4 1 <= a.length, b.length <= 10^4 1<=a.length,b.length<=104
• 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;}};