leetcode 67. Add Binary

Seawolf

1. Given two binary strings, return their sum (also a binary string).
   
2. 
   
3. The input strings are both non-empty and contains only characters 1 or 0.
   
4. 
   
5. Example 1:
   
6. 
   
7. Input: a = "11", b = "1"
   
8. Output: "100"
   
9. Example 2:
   
10. 
    
11. Input: a = "1010", b = "1011"
    
12. Output: "10101"

复制代码

借助BigInteger，虽然过了，效率贼差

1. import java.math.BigInteger;
   
2. class Solution {
   
3.     public String addBinary(String a, String b) {
   
4.         
   
5.         BigInteger bi1, bi2, bi3;
   
6.         bi1 = new BigInteger(a,2);
   
7.         bi2 = new BigInteger(b,2);
   
8.         bi3 = bi1.add(bi2);
   
9.         
   
10.         return bi3.toString(2);
    
11.     }
    
12.    
    
13. }

复制代码

然后选择分步来解决！

1. class Solution {
   
2.     public String addBinary(String a, String b) {
   
3.         
   
4.         StringBuilder A = new StringBuilder(a);
   
5.         
   
6.         StringBuilder B = new StringBuilder(b);
   
7.         
   
8.         A.reverse();
   
9.         B.reverse();
   
10.         
    
11.         while(A.length() > B.length()) B.append("0");
    
12.         
    
13.         while(A.length() < B.length()) A.append("0");
    
14.         
    
15.         int carry = 0, sum =0;
    
16.         
    
17.         StringBuilder re = new StringBuilder("");
    
18.         
    
19.         for(int i = 0; i< A.length(); i ++){
    
20.             
    
21.             sum = carry + (A.charAt(i) - '0') + (B.charAt(i) - '0');
    
22.             
    
23.             re.append(sum % 2);
    
24.             
    
25.             carry = sum /2;
    
26.             
    
27.         }
    
28.         
    
29.         while(carry > 0){
    
30.             
    
31.             re.append(carry % 2);
    
32.             
    
33.             carry = carry /2;
    
34.         }
    
35.         
    
36.         re.reverse();
    
37.         return re.toString();
    
38. 
    
39.     }
    
40.    
    
41. }

复制代码