67. Add Binary

Given two binary strings, return their sum (also a binary string).

The input strings are both **non-empty** and contains only characters `1` or `0`.

**Example 1:**

1
2
Input: a = "11", b = "1"
Output: "100"
**Example 2:**
1
2
Input: a = "1010", b = "1011"
Output: "10101"
思路(copy):下面这种写法又巧妙又简洁,用了两个指针分别指向a和b的末尾,然后每次取出一个字符,转为数字,若无法取出字符则按0处理,然后定义进位carry,初始化为0,将三者加起来,对2取余即为当前位的数字,对2取商即为当前进位的值,记得最后还要判断下carry,如果为1的话,要在结果最前面加上一个1,参见代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
string addBinary(string a, string b) {
string res = "";
int m = a.size() - 1, n = b.size() - 1, carry = 0;
while (m >= 0 || n >= 0) {
int p = m >= 0 ? a[m--] - '0' : 0;
int q = n >= 0 ? b[n--] - '0' : 0;
int sum = p + q + carry;
res = to_string(sum % 2) + res;
carry = sum / 2;
}
return carry == 1 ? "1" + res : res;
}
};
Res. 4ms, Ranking 97.16%.改进的写法,更快了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
string addBinary(string a, string b) {
string c;
int carry = 0, i = a.size()-1, j = b.size()-1;
while(i>=0 || j>=0 || carry!=0){
carry += (i>=0? a[i--]-'0':0);
carry += (j>=0? b[j--]-'0':0);
c = c + (char)(carry%2+'0');
carry /= 2;
}
reverse( c.begin(), c.end());
return c;
}
};
Res. 0ms, Ranking 100.100%