最开始的思路是直接把字符串转换成数字，然后加和，再转换回去，这样只需要一行代码即可实现。
1
2
3
4
5
| class Solution {
public String addBinary(String a, String b) {
return Long.toBinaryString(Long.parseLong(a,2)+Long.parseLong(b,2));
}
}
|
但是在运行时发现，测试集里的字符串太长，转换失败，只能换其他思路。
新的思路也很简单，甚至和上一道题Plus One的思路类似，就是先从右边开始将较短数字加和到较长数字中并记录进位，当用尽比较短的串中的数字时，开始单纯考虑较长数字的进位，最后考虑较长数字最大位的进位。
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
| class Solution {
public String addBinary(String a, String b) {
char[] ac=a.toCharArray();
char[] bc=b.toCharArray();
char[] longer=ac.length>bc.length?ac:bc;
char[] shorter=ac.length>bc.length?bc:ac;
int subLen=longer.length-shorter.length;
boolean isCarry=false;
for(int i=longer.length-1;i>=longer.length-shorter.length;i--){
if(longer[i]=='1' && shorter[i-subLen]=='1'){
longer[i]=isCarry?'1':'0';
isCarry=true;
}else if(longer[i]=='0' && shorter[i-subLen]=='0'){
longer[i]=isCarry?'1':'0';
isCarry=false;
}else{
longer[i]=isCarry?'0':'1';
}
}
for(int i=longer.length-shorter.length-1;i>=0;i--){
if(isCarry){
if(longer[i]=='1'){
longer[i]='0';
}else{
longer[i]='1';
isCarry=false;
}
}
}
if(isCarry==true){
char[] newLonger=new char[longer.length+1];
newLonger[0]='1';
System.arraycopy(longer,0,newLonger,1,longer.length);
longer=newLonger;
}
return new String(longer);
}
}
|
代码行数虽然长了一些，但是效率还不错，击败了 96.75%的人。
看了 Discuss 中的代码，真的自愧不如，他用了 StringBuilder 和 reverse，巧妙地避免了 arraycopy 的麻烦，并且在运算中将 char 转换为 int 并使用了取商和取余操作，简化了各种 case，真的是妙。
仿照他的思路写出如下代码，击败了 52.8%的人。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public String addBinary(String a, String b) {
StringBuilder sb=new StringBuilder();
char[] ac=a.toCharArray();
char[] bc=b.toCharArray();
int i=ac.length-1;
int j=bc.length-1;
int carry=0;
while(i>=0 || j>=0){
int sum=carry;
if(j>=0)
sum+=bc[j--]-'0';
if(i>=0)
sum+=ac[i--]-'0';
sb.append(sum%2);
carry=sum/2;
}
if(carry>0)
sb.append(carry);
return sb.reverse().toString();
}
}
|