標籤:

LeetCode 67 Add Binary

題目:

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

For example,

a = "11"

b = "1"

Return "100".

思路如下:

我們需要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)

推薦閱讀:

leetcode-1
Leetcode刷完了第一次,用了一個半月,完全人肉debug,接受率不到20%,第二次該如何刷?
LeetCode 680. Valid Palindrome II

TAG:LeetCode |