67 Add Binary
Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".
Lesson learned:
- sum.append(digit % 2);
// should remember, if this case come up, // if (digit%2==1) append(1); elseif (digit%2==0) append(0); // use append(digit%2) directly!!!!!!!!!!!!!!!!!!!! - carry = digit / 2;
// this is another special case of "if". // digit>2, carry = 1; digit < 2, carry = 0; means you can use carry = digit/2;
StringBuilder 的好处：
本题用遍历（倒着）的方法edge case太多，更好的是用补零。虽然刚开始想到了补零但是没想到怎么用String简单的操作，参考了网上的程序，用StringBuilder补零。StringBuilder还有一个好处是里面有reverse（）函数。
Code
public class Solution {
public String addBinary(String a, String b) {
String sum = "";
// traverse order!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
int carry = 0; // record carry
String s, l;
if (b.length() < a.length()) {
s = b;
l = a;
} else {
s = a;
l = b;
}
int i = s.length() - 1; // traverse s
int j = l.length() - 1;
// start sum
while (i >= 0) {
int digit = s.charAt(i) - '0' + l.charAt(j) - '0' + carry;
sum = sum + Integer.toString(digit % 2);
if (digit > 1) {
carry = 1;
} else {
carry = 0;
}
i--;
j--;
}
while (j >= 0) {
int digit = l.charAt(j) - '0' + carry;// traverse a
sum = sum + Integer.toString(digit % 2);
if (digit > 1) {
carry = 1;
} else {
carry = 0;
}
j--;
}
if (carry != 0) {
sum = sum + "1";
}
String addNum = "";
for (int k = 0; k < sum.length(); k++) {
addNum += sum.charAt(sum.length() - 1 - k);
}
return addNum;
}
}
Stringbuilder的例子： updated：
public class Solution {
public String addBinary(String a, String b) {
StringBuilder s = a.length() < b.length() ? new StringBuilder(a) : new StringBuilder(b);
StringBuilder l = a.length() >= b.length() ? new StringBuilder(a) : new StringBuilder(b);
s = s.reverse();
l = l.reverse();
while (l.length() != s.length()) {
s.append(0);
}
StringBuilder sum = new StringBuilder();
int carry = 0;
for (int i = 0; i < s.length(); i++) {
int digit = carry + s.charAt(i) - '0' + l.charAt(i) - '0';
if (digit % 2 == 1) {
sum.append(1);
if (digit > 1) {
carry = 1;
} else {
carry = 0;
}
} else {
sum.append(0);
if (digit > 1) {
carry = 1;
} else {
carry = 0;
}
}
}
if (carry == 1) {
sum.append(1);
}
return sum.reverse().toString();
}
}
updated 2:
public class Solution {
public String addBinary(String a, String b) {
StringBuilder s = a.length() < b.length() ? new StringBuilder(a) : new StringBuilder(b);
StringBuilder l = a.length() >= b.length() ? new StringBuilder(a) : new StringBuilder(b);
s = s.reverse();
l = l.reverse();
while (l.length() != s.length()) {
s.append(0);
}
StringBuilder sum = new StringBuilder();
int carry = 0;
for (int i = 0; i < s.length(); i++) {
int digit = carry + s.charAt(i) - '0' + l.charAt(i) - '0';
sum.append(digit % 2); // should remember, if this case come up,
// if (digit%2==1) append(1); elseif (digit%2==0) append(0);
// use append(digit%2) directly!!!!!!!!!!!!!!!!!!!!
carry = digit / 2; // this is another special case of "if".
// digit>2, carry = 1; digit < 2, carry = 0; means you can use carry = digit/2;
}
if (carry == 1) {
sum.append(1);
}
return sum.reverse().toString();
}
}
updated 3:
public class Solution {
public String addBinary(String a, String b) {
// 不补零做法
int digit = 0, carry = 0;
int al = a.length(), bl = b.length();
StringBuilder str = new StringBuilder();
for (int i = 0; i < Math.max(al, bl); i++) {
int x = (i < al) ? (a.charAt(al - i - 1) - '0') : 0; // 用这种方式补零
int y = (i < bl) ? (b.charAt(bl - i - 1) - '0') : 0;
digit = x + y + carry;
str.append(digit % 2);
carry = digit / 2;
}
if (carry > 0) {
str.append(1);
}
return str.reverse().toString();
}
}
Nine Chapter
carry = sum/2 //这里特别好。奇数偶数分别用%解决，大于一小于一问题用/2解决！
九章给出的解法和我第一次解法的想法一样，但是他们写的特别简洁。 http://www.jiuzhang.com/solutions/add-binary/
/**
- 本代码由九章算法编辑提供。没有版权欢迎转发。
- 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
- 现有的面试培训课程包括：九章算法班，系统设计班，BAT国内班
更多详情请见官方网站：http://www.jiuzhang.com/ */
public class Solution { public String addBinary(String a, String b) {
if(a.length() < b.length()){ String tmp = a; a = b; b = tmp; } int pa = a.length()-1; //这里倒着遍历，也特别好 int pb = b.length()-1; int carries = 0; String rst = ""; while(pb >= 0){ int sum = (int)(a.charAt(pa) - '0') + (int)(b.charAt(pb) - '0') + carries; rst = String.valueOf(sum % 2) + rst; carries = sum / 2; pa --; pb --; } while(pa >= 0){ int sum = (int)(a.charAt(pa) - '0') + carries; rst = String.valueOf(sum % 2) + rst; carries = sum / 2; pa --; } if (carries == 1) rst = "1" + rst; return rst;} }
William's Coding Book
// Math.max(); find the max value
// ?: can be used to reduce the size of if...else...
//Working for any place-value systems below 10
public String addBinary(String a, String b) {
int place = 2; // 10: decimal, 2 - binary
int na = a.length(), nb = b.length();
int digit = 0, carry = 0;
StringBuilder str = new StringBuilder();
for (int i = 0; i < Math.max(na, nb); i++) {
int da = (i < na) ? Character.getNumericValue(a.charAt(na - 1 - i)) : 0;
int db = (i < nb) ? Character.getNumericValue(b.charAt(nb - 1 - i)) : 0;
int sum = da + db + carry;
digit = sum % place;
carry = sum / place;
str.append(digit);
}
if (carry > 0) str.append(carry);
return str.reverse().toString();
}
Updated(12.18.15):
public class Solution {
public String addBinary(String a, String b) {
if (a == null || b == null) {
return null;
}
if (a.length() == 0 || b.length() == 0) {
return a + b;
}
int carry = 0;
int count = Math.max(a.length(), b.length());
int i = 0;
StringBuilder plus = new StringBuilder();
// should be plused from 低位
// 不要背答案，仔细思考操作位和循环条件。
while (i < count) {
int digitA = i < a.length() ? a.charAt(a.length() - 1 - i) - '0' : 0;
int digitB = i < b.length() ? b.charAt(b.length() - 1 - i) - '0' : 0;
int digit = digitA + digitB + carry;
plus.append(digit % 2);
carry = digit / 2;
i++;
}
if (carry == 1) {
plus.append(carry);
}
// forgot to convert to String
return plus.reverse().toString();
}
}