Add Binary

Question

  1. Given two binary strings, return their sum (also a binary string).
  3. For example,
  4. a = "11"
  5. b = "1"
  6. Return "100".

題解

用字串模擬二進制的加法，加法操作一般使用自後往前遍歷的方法，不同位大小需要補零。

Java

  1. public class Solution {
  2.     /**
  3.      * @param a a number
  4.      * @param b a number
  5.      * @return the result
  6.      */
  7.     public String addBinary(String a, String b) {
  8.         if (a == null || a.length() == 0) return b;
  9.         if (b == null || b.length() == 0) return a;
  11.         StringBuilder sb = new StringBuilder();
  12.         int aLen = a.length(), bLen = b.length();
  14.         int carry = 0;
  15.         for (int ia = aLen - 1, ib = bLen - 1; ia >= 0 || ib >= 0; ia--, ib--) {
  16.             // replace with 0 if processed
  17.             int aNum = (ia < 0) ? 0 : a.charAt(ia) - '0';
  18.             int bNum = (ib < 0) ? 0 : b.charAt(ib) - '0';
  20.             int num = (aNum + bNum + carry) % 2;
  21.             carry = (aNum + bNum + carry) / 2;
  22.             sb.append(num);
  23.         }
  24.         if (carry == 1) sb.append(1);
  26.         // important!
  27.         sb.reverse();
  28.         String result = sb.toString();
  29.         return result;
  30.     }
  31. }

源碼分析

用到的技巧主要有兩點，一是兩個數位數大小不一時用0補上，二是最後需要判斷最高位的進位是否為1。最後需要反轉字符串，因為我們是從低位往高位迭代的。雖然可以使用 insert 避免最後的 reverse 操作，但如此一來時間複雜度就從 O(n) 變為 O(n^2) 了。

C++

  1. class Solution {
  2. public:
  3.     // helper functions
  4.     char XOR(char x, char y) {
  5.         return x == y ? '0' : '1';
  6.     }
  7.     char CARRY(char x, char y){
  8.         return (x == '1' and y == '1') ? '1' : '0';
  9.     }
  10.     string addBinary(string a, string b) {
  11.         if(a.size() < b.size())
  12.             swap(a,b);
  14.         int i = a.size()-1;
  15.         int j = b.size()-1;
  16.         char carry ='0';
  18.         while(0 <= i) {
  19.             char tmp = a[i];
  20.             a[i] = XOR(tmp, carry);
  21.             carry = CARRY(tmp, carry);
  22.             if(0 <= j) {
  23.                 tmp = a[i];
  24.                 a[i] = XOR(tmp, b[j]);
  25.                 carry = XOR(carry, CARRY(tmp, b[j]));
  26.             }
  27.             i--; j--;
  28.         }
  30.         if(carry == '1')
  31.             a = "1" + a;
  32.         return a;
  33.     }
  34. };

源碼分析

C++的解法採用了直接操作char的作法，模擬硬體半加器(half adder)的行為，先確保a的長度不小於b的長度後，下標從尾到頭逐位相加，小心處理進位即可。

複雜度分析

Java解法遍歷兩個字串，時間複雜度 O(n). reverse 操作時間複雜度 O(n), 故總的時間複雜度 O(n). 使用了 StringBuilder 作為臨時存儲對象，空間複雜度 O(n).

C++解法時間複雜度也是O(n)，計算過程中使用的臨時變數，額外空間複雜度是O(1)，實際整體空間複雜度則取決於最後我們要將答案擴張一位時，函數的實現方法，最差可能達到O(n)。