67.Add Binary
Given two binary strings a and b, return their sum as a binary string.
Example 1:
1
2
| Input: a = "11", b = "1"
Output: "100"
|
Example 2:
1
2
| Input: a = "1010", b = "1011"
Output: "10101"
|
个人解答：
时间复杂度：O(n)
空间复杂度：O(n)
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
36
37
38
| string addBinary(string a, string b) {
string ans_str = "";
int a_size = a.size();
int b_size = b.size();
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
if (a_size < b_size) {
int temp = b_size - a_size;
while (temp--)a += "0";
}
else {
int temp = a_size - b_size;
while (temp--)b += "0";
}
char carry = '0';
for (int i = 0; i < a_size || i<b_size; ++i) {
if (a[i] + b[i] + carry == 144) {
ans_str += "0";
carry = '0';
}
else if (a[i] + b[i] + carry == 145) {
ans_str += "1";
carry = '0';
}
else if (a[i] + b[i] + carry == 146) {
ans_str += "0";
carry = '1';
}
else if (a[i] + b[i] + carry == 147) {
ans_str += "1";
carry = '1';
}
else cout << "mistake" << endl;
}
if (carry == '1')ans_str += "1";
reverse(ans_str.begin(), ans_str.end());
return ans_str;
}
|
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
| string addBinary(string a, string b) {
if (a.empty()) return b;
if (b.empty()) return a;
int index_a = a.size() - 1;
int index_b = b.size() - 1;
int carry = 0;
int bit_a = 0, bit_b = 0;
string result;
const int radix = 2;
while (index_a >= 0 || index_b >= 0) {
bit_a = 0, bit_b = 0;
if (index_a >= 0) {
bit_a = a[index_a] - '0';
}
if (index_b >= 0) {
bit_b = b[index_b] - '0';
}
auto sum = bit_a + bit_b + carry;
auto bit = sum % radix;
carry = sum / radix;
result += bit + '0';
--index_a;
--index_b;
}
if (carry) {
result += carry + '0';
}
reverse(begin(result), end(result));
return result;
}
|