LeetCode-Add Binary

Add Binary

##题目

####Add Binary

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

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

##解题思路
该题是对两个二进制进行求和，这里维护一个进位，分别对a和b从后往前，每一位进行求和，然后/2得到进位，%2得到该位的值。如果a和b长度不一样，则最终还要遍历完长度长的那个字符串。如果最终位也存在进位的情况，则需要将进位放入结果中。

##算法代码
代码采用JAVA实现：

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
39
40
41
42
43
44
public class Solution {
    public String addBinary(String a, String b) {
        if(a==null ||a.length()==0)
        	return b;
        if(b==null ||b.length()==0)
        	return a;
        char[] a_char=a.toCharArray();
        char[] b_char=b.toCharArray();
        int jinwei=0;
        int i=a_char.length-1;
        int j=b_char.length-1;
        StringBuilder res=new StringBuilder();  //结果先存在其中，最后通过转置得到结果
        while(i>=0 && j>=0) 
        {
        	int numa=a_char[i]-'0';
        	int numb=b_char[j]-'0';
        	int num=(numa+numb+jinwei)%2;
        	jinwei=(numa+numb+jinwei)/2;
        	res.append(num);
        	i--;
        	j--;
        }
        while(i>=0)  //b字符串已经结束
        {
        	int numa=a_char[i]-'0';
        	int num=(numa+jinwei)%2;
        	jinwei=(numa+jinwei)/2;
        	res.append(num);
        	i--;
        }
        while(j>=0)  //a字符串已经结束
        {
        	int numb=b_char[j]-'0';
        	int num=(numb+jinwei)%2;
        	jinwei=(numb+jinwei)/2;
        	res.append(num);
        	j--;
        }
        if(jinwei!=0)   //最高位存在进位
        	res.append(jinwei);
        res.reverse();
        return res.toString();
    }
}

Comments

▲