1 题目
Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".
接口
String addBinary(String a, String b)
2 思路
处理二进制求和和进位。从低位开始，一直相加并且维护进位。和Add Two Numbers的区别是这个题目低位在后面，所以要从string的尾部往前加。
代码采用Add Two Number的思路，先把Input String逆序，让低位在前面，最后把result在逆序一次。
复杂度
Time: O(n)
Space: O(n)
3 代码
1 public String addBinary(String a, String b) { 2 char[] ac = new StringBuilder(a).reverse().toString().toCharArray(); 3 char[] bc = new StringBuilder(b).reverse().toString().toCharArray(); 4 int alen = ac.length; 5 int blen = bc.length; 6 StringBuilder res = new StringBuilder(); 7 int max = alen > blen ? alen : blen; 8 int carry = 0; 9 for (int i = 0; i < max; i++) { 10 int ai = i < alen ? ac[i] - '0' : 0; 11 int bi = i < blen ? bc[i] - '0' : 0; 12 int sum = ai + bi + carry; 13 carry = sum / 2; 14 res.append((char) (sum % 2 + '0')); 15 } 16 if (carry == 1) 17 res.append('1'); 18 return res.reverse().toString(); 19 }
4 总结
- 关键是处理相加和进位
- 采用StringBuilder reverse()
- 和Add Two Number类似
5 扩展
String、StringBuilder、StringBuffer的区别？