LeetCode 67 Add Binary
題目:
Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
"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 |