Add Binary – LeetCode 67
Problem
Description
Given two binary strings, return their sum (also a binary string).
Example
For example,
a = “11”
b = “1”
Return “100”.
Answer
Original
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
string addBinary(string a, string b) {
string &result = (a.size() > b.size())? a: b;
string &other = (a.size() <= b.size())? a: b;
int diff = result.size() - other.size();
int push = 0;
for(int i = other.size() - 1; i >= 0; --i){
if(result[i+diff] == '1' && other[i] == '1'){result[i+diff] = (char)(push+'0'); push = 1;}
else if(result[i+diff] == '0' && other[i] == '0'){result[i+diff] = (char)(push+'0'); push = 0;}
else {if(push) {result[i+diff] = '0'; push = 1;} else {result[i+diff] = '1';}}
}
for(int i = diff - 1; i >= 0; --i){
if(result[i] == '1') {if(push){result[i] = '0'; push = 1;} else {result[i] = '1'; push = 0;}} else {result[i] = (char)(push+'0'); push = 0;}
}
if(push) {result.insert(result.begin(), '1');}
return result;
}
};
|
思路
简单使用两个循环分别处理两个字符串的共有段和私有段，从尾向头传播。时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$3$ ms，排名$77.79\%$
Better
思路
使用恰当的取值和下标控制来统一计算过程，且简化加和和进位在同一个变量，这是目前看到的同样复杂度下最漂亮的解法。时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$3$ ms，排名$88.57\%$
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution
{
public:
string addBinary(string a, string b)
{
string s = "";
int c = 0, i = a.size() - 1, j = b.size() - 1;
while(i >= 0 || j >= 0 || c == 1)
{
c += i >= 0 ? a[i --] - '0' : 0;
c += j >= 0 ? b[j --] - '0' : 0;
s = char(c % 2 + '0') + s;
c /= 2;
}
return s;
}
};
|