【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++
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
|
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;
}
};
|
C++ - 写法2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public:
string addBinary(string a, string b) {
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
string ans;
int cnt = 0;
for (int i = 0, to = max(a.size(), b.size()); i < to; i++) {
cnt += i < a.size() ? a[i] - '0' : 0;
cnt += i < b.size() ? b[i] - '0' : 0;
ans.push_back('0' + (cnt % 2));
cnt >>= 1;
}
if (cnt) {
ans.push_back('1');
}
reverse(ans.begin(), ans.end());
return ans;
}
};
|
Python - 内部库 string->int->string
1
2
3
4
5
6
| '''
LastEditTime: 2026-02-15 12:45:41
'''
class Solution:
def addBinary(self, a: str, b: str) -> str:
return format((int(a, 2) + int(b, 2)), 'b')
|
同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
千篇源码题解已开源