Update Add Binary.java

awangdev · web-flow · commit ff4c9b6117be · 2018-08-06T17:59:15.000-07:00
diff --git a/Java/Add Binary.java b/Java/Add Binary.java
@@ -1,11 +1,16 @@
 E
-1519709164
-tags: Math, String
+1533603550
+tags: Math, String, Two Pointers
 
-&#26041;&#27861;&#19968;:&#22303;&#21150;&#27861;&#27809;&#25216;&#26415;&#65292;&#25226;binary&#25442;&#25104;&#25968;&#23383;&#65292;&#21152;&#36215;&#26469;&#65292;&#20877;&#25442;&#25104;binary&#12290;&#22914;&#26524;input&#24456;&#22823;&#65292;&#37027;&#20040;&#24456;&#21487;&#33021;int,long&#37117;hold&#19981;&#20303;&#12290;&#19981;&#20445;&#38505;&#12290;
+#### Two pointers
+- Use two pointers i, j to track the 2 strings
+- Add when i and j are applicable. While (i >= 0 || j >= 0)
+- StringBuffer.insert(0, x);
+- handle carry
 
-&#26041;&#27861;&#20108;:&#19968;&#33324;&#26041;&#27861;&#65292;string&#21270;&#20026;charArray,&#28982;&#21518;&#36880;&#20301;&#21152;&#36215;&#65292;&#26368;&#21518;&#35760;&#24471;&#22788;&#29702;&#22810;&#20313;&#30340;&#19968;&#20010;carry on
-&#27880;&#24847;: &#38656;&#35201;&#20174;&#26411;&#23614;&#21152;&#36215;&#26469;, &#25152;&#20197;&#35201;&#29992;&#19968;&#20010;diff&#26469;&#24110;&#21161;  shortArray[i-diff] &#25351;&#21521; shortArray&#30340;&#30456;&#23545;&#24212;index.
+#### wrong: convert to int
+- &#22303;&#21150;&#27861;&#27809;&#25216;&#26415;&#65292;&#25226;binary&#25442;&#25104;&#25968;&#23383;&#65292;&#21152;&#36215;&#26469;&#65292;&#20877;&#25442;&#25104;binary
+- &#22914;&#26524;input&#24456;&#22823;&#65292;&#37027;&#20040;&#24456;&#21487;&#33021;int,long&#37117;hold&#19981;&#20303;&#12290;&#19981;&#20445;&#38505;&#12290;
 
 ```
 /*
@@ -23,6 +28,21 @@ Given two binary strings, return their sum (also a binary string).
 Tags Expand 
 String Binary Facebook
 */
+public class Solution {
+    public String addBinary(String a, String b) {
+        StringBuilder sb = new StringBuilder();
+        int i = a.length() - 1, j = b.length() -1, carry = 0;
+        while (i >= 0 || j >= 0) {
+            int sum = carry;
+            if (i >= 0) sum += a.charAt(i--) - '0';
+            if (j >= 0) sum += b.charAt(j--) - '0';
+            sb.insert(0, sum % 2);
+            carry = sum / 2;
+        }
+        if (carry != 0) sb.insert(0, carry);
+        return sb.toString();
+    }
+}
 
 /*
 Thoughts:
@@ -121,4 +141,4 @@ public String addBinary(String a, String b) {
 
 
 
-```
+```
