LeetCode 67 Add Binary

題目：

Given two binary strings, return their sum (also a binary string).

For example,

a = "11"

思路如下：

我們需要i，j兩個指針和carry, sum兩個int型變數。 i從String a 的最後一個元素開始往前走，j從String b的最後一個元素往前走。carry代表進位數，sum代表每個位置處ab與carry的和。

因為我們把數字加進StringBuilder的順序跟最後應該輸出的結果的順序是反著的，所以最後要記得翻轉一下。

代碼如下：

public String addBinary(String a, String b) {n StringBuilder sb = new StringBuilder();n int i = a.length() -1, j = b.length() -1, carry = 0;n while (i>= 0 || j>= 0) {n int sum = carry;n if(j >=0) sum += b.charAt(j--) -0;n if(i >=0) sum += a.charAt(i--) -0;n sb.append(sum%2);n carry = sum/2;n }n if (carry!= 0) sb.append(carry);nreturn sb.reverse().toString();n}n

時間複雜度： O(n)

推薦閱讀：