二进制加法 注意考虑本位和进位
Given two binary strings, return their sum (also a binary string).
The input strings are both non-empty and contains only characters 1 or 0.
Example 1:
Input: a = "11", b = "1" Output: "100"
Example 2:
Input: a = "1010", b = "1011" Output: "10101"
自己的方法：
就是将加法分成进位和本位，然后递归的调用加法，然后当进位部分为 0 时，则为结果。
但是很麻烦
class Solution {
public String addBinary(String a, String b) {
if(a == null || a.length() == 0 || b == null || b.length() == 0) return "";
String str = help(a, b);
int index = str.indexOf("1");
if(index == -1) return "0";
return str.substring(index);
}
public static String help(String a, String b){
if(b.indexOf("1") == -1) return a;
StringBuilder sum = new StringBuilder();
StringBuilder carry = new StringBuilder();
if(a.length() != b.length()){
String max = a.length() > b.length() ? a : b;
String min = a.length() < b.length() ? a : b;
a = max;
char[] ch = new char[max.length() - min.length()];
Arrays.fill( ch, '0' );
b = String.valueOf(ch) + min;
}
for(int i = 0; i < a.length() && i < b.length(); i++){
if(a.charAt(i) == '1' && b.charAt(i) == '1'){
carry.append("1");
sum.append("0");
} else if(a.charAt(i) == '0' && b.charAt(i) == '0'){
carry.append("0");
sum.append("0");
} else{
carry.append("0");
sum.append("1");
}
}
return help(sum.toString(), carry.append("0").toString());
}
}
在discuss区看到的一个简单的方法：
public class Solution {
public String addBinary(String a, String b) {
StringBuilder sb = new StringBuilder();
int i = a.length() - 1, j = b.length() -1, carry = 0;
while (i >= 0 || j >= 0) {
int sum = carry;
if (j >= 0) sum += b.charAt(j--) - '0';
if (i >= 0) sum += a.charAt(i--) - '0';
sb.append(sum % 2);
carry = sum / 2;
}
if (carry != 0) sb.append(carry);
return sb.reverse().toString();
}
}