Keshawn_lu's Blog

Leetcode 67. 二进制求和

字数统计: 387阅读时长: 1 min
2020/06/23 Share

题目简介:

给你两个二进制字符串,返回它们的和(用二进制表示)。

输入为 非空 字符串且只包含数字 10

示例 1:

1
2
输入: a = "11", b = "1"
输出: "100"

示例 2:

1
2
输入: a = "1010", b = "1011"
输出: "10101"

提示:

  • 每个字符串仅由字符 '0''1' 组成。
  • 1 <= a.length, b.length <= 10^4
  • 字符串如果不是 "0" ,就都不含前导零。

思路:

首先的想法是将二进制先转换为十进制进行相加,再转化成二进制字符串,但是位数多了就会超时,所以开始想别的方法。

然后想到了可以使用模拟竖式的方法,先用补0的方法将两个字符串变成相同的长度;再从后向前逐位相加,若相加 >= 2,则向前一位进1。

tips:

  • 学会a[i] - '0'的方法将字符串变成数字(ASCII码)。
  • 注意补零的方法

代码如下:

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
32
33
34
35
class Solution {
public:
string addBinary(string a, string b) {

while(a.size() < b.size()){

a = "0" + a; //补0,使等长
}
while(b.size() < a.size()){

b = "0" + b;
}

//从后往前,对齐按位相加
for(int i = a.size() - 1; i >= 1; i--){

a[i] = a[i] - '0' + b[i];
if(a[i] >= '2'){

a[i] = (a[i] - '0') % 2 + '0';
a[i - 1]++; //进位
}
}

a[0] = a[0] - '0' + b[0]; //处理第0位
if(a[0] >= '2'){

a[0] = (a[0] - '0') % 2 + '0';
a = '1' + a;
}

return a;

}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: