[LeetCode] Add Binary 解题报告

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

For example,
a = "11"
b = "1"
Return "100".

» Solve this problem

[解题思路]
典型的实现题。没什么可说的。


[Code]
很少用c++，不查api库，不知道还有reverse这个方法。

1:    string addBinary(string a, string b) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      string result;  
5:      int maxL = a.size() > b.size()? a.size():b.size();  
6:      std::reverse(a.begin(), a.end());  
7:      std::reverse(b.begin(), b.end());  
8:      int carry=0;  
9:      for(int i =0; i<maxL;i++)  
10:      {  
11:        int ai = i<a.size()? a[i]-'0':0;  
12:        int bi = i<b.size()?b[i]-'0':0;  
13:        int val = (ai+bi+carry)%2;  
14:        carry = (ai+bi+carry)/2;  
15:        result.insert(result.begin(), val+'0');  
16:      }  
17:      if(carry ==1)  
18:      {  
19:        result.insert(result.begin(), '1');  
20:      }  
21:      return result;  
22:    }  

[Note]
在facebook见过一个扩展题就是，如果不是二进制而是16进制，如何扩展。在上面的code中很容易更改，将Line13及Line14 中的2改成16就可以了。

Update 3/1/2014
上一个version写的太复杂，string的reverse根本没必要。直接用两个index一起往前跑就好了。更新之。

1:    string addBinary(string a, string b) {  
2:      int carry =0;  
3:      string result;  
4:      for(int i = a.size()-1, j = b.size()-1; i >=0 || j>=0; --i,--j)  
5:      {  
6:        int ai = i>=0? a[i]-'0':0;  
7:        int bj = j>=0? b[j]-'0':0;  
8:        int val = (ai+bj+carry)%2;  
9:        carry = (ai+bj+carry) /2;  
10:        result.insert(result.begin(), val+'0');  
11:      }  
12:      if(carry ==1)  
13:      {  
14:        result.insert(result.begin(), '1');  
15:      }  
16:      return result;  
17:    }