Thursday, November 20, 2014

[LeetCode] Add Binary

Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".

思路:

和Add Two Numbers那题一样的思路。区别仅在于:

1. 本题中的数字是顺序而非逆序排列的。可以先将a, b逆序。

2. 二进制而非十进制加法。

3. 字符和数字之间的转换。



 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) {
        reverse(a.begin(),a.end());
        reverse(b.begin(),b.end());
        string sum;
        int carry = 0;
        int n = max(a.size(),b.size());
        for(int i=0; i<n; i++) {
            if(i<a.size()) carry+=(a[i]-'0');
            if(i<b.size()) carry+=(b[i]-'0');
            sum.push_back(carry%2+'0');
            carry/=2; 
        }
        if(carry) sum.push_back('1');
        reverse(sum.begin(),sum.end());
        return sum;
    }
};

No comments:

Post a Comment