Question
1 2 3 4 5 6 Given two binary strings, return their sum (also a binary string). For example, a = "11" b = "1" Return "100".
题解
用字符串模拟二进制的加法,加法操作一般使用自后往前遍历的方法,不同位大小需要补零。
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 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; StringBuilder sb = new StringBuilder (); int aLen = a.length(), bLen = b.length(); int carry = 0 ; for (int ia = aLen - 1 , ib = bLen - 1 ; ia >= 0 || ib >= 0 ; ia--, ib--) { int aNum = (ia < 0 ) ? 0 : a.charAt(ia) - '0' ; int bNum = (ib < 0 ) ? 0 : b.charAt(ib) - '0' ; int num = (aNum + bNum + carry) % 2 ; carry = (aNum + bNum + carry) / 2 ; sb.append(num); } if (carry == 1 ) sb.append(1 ); sb.reverse(); String result = sb.toString(); return result; } }
源码分析
用到的技巧主要有两点,一是两个数位数大小不一时用0补上,二是最后需要判断最高位的进位是否为1。最后需要反转字符串,因为我们是从低位往高位迭代的。虽然可以使用 insert 避免最后的 reverse 操作,但如此一来时间复杂度就从 \[O(n)\] 变为 \[O(n^2)\] 了。
复杂度分析
遍历两个字符串,时间复杂度 \[O(n)\] . reverse 操作时间复杂度 \[O(n)\] , 故总的时间复杂度 \[O(n)\] . 使用了 StringBuilder 作为临时存储对象,空间复杂度 \[O(n)\] .