欢迎访问LeetCode题解合集
题目描述
给你两个二进制字符串,返回它们的和(用二进制表示)。
输入为 非空 字符串且只包含数字 1
和 0
。
示例 1:
输入: a = "11", b = "1"
输出: "100"
示例 2:
输入: a = "1010", b = "1011"
输出: "10101"
提示:
-
每个字符串仅由字符
0
或1
组成。 -
$1 \le a.length, b.length \le 10^4$
-
字符串如果不是
"0"
,就都不含前导零。
题解:
模拟竖式加法。
将 a
和 b
逆序,低位在前,高位在后,这样做加法比较容易。
然后从低位到高位依次计算每一位,过程中需要记录前一位的进位。
如果最高位的进位是1,则需要在最高位的位置补上1(这也是逆序的目的,为了处理这种情况)
最后,将相加结果逆序返回。
时间复杂度:$O(max(n, m))$
额外空间复杂度:$O(max(n, m))$
class Solution {
public:
string addBinary(string a, string b) {
reverse( a.begin(), a.end() );
reverse( b.begin(), b.end() );
string ret = "";
int la = a.length(), lb = b.length();
int max_len = max( la, lb );
int d = 0;
for ( int i = 0; i < max_len; ++i ) {
if ( i < la ) d += a[i] & 15;
if ( i < lb ) d += b[i] & 15;
ret.push_back( d % 2 + '0' );
d >>= 1;
}
if ( d ) ret.push_back( d + '0' );
reverse(ret.begin(), ret.end());
return ret;
}
};
/*
时间:0ms,击败:100.00%
内存:6.2MB,击败:91.38%
*/
官方题解还有 位运算 版本,c++
没有高精度哭了。。。