[LeetCode] 67. Add Binary

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

The input strings are both non-empty and contains only characters 1 or 0.

Example 1:

Input: a = "11", b = "1"
Output: "100"
Example 2:

Input: a = "1010", b = "1011"
Output: "10101"

Constraints:

Each string consists only of '0' or '1' characters.
1 <= a.length, b.length <= 10^4
Each string is either "0" or doesn't contain any leading zero.

二进制求和。影子题415，是十进制的加法。做法甚至代码几乎都是一样的。

题意是给两个用字符串表示的二进制数字，请返回他们的和，也用字符串表示。思路是按位读取数字，从最低位开始两两相加，之后将（加和%2）append到结果集。为什么要将加和%2是因为这是二进制的计算，之后计算carry的时候也是需要除以2而不是除以10。

时间O(n)

空间O(1)

Java实现

class Solution {
    public String addBinary(String a, String b) {
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        int sum = 0;
        StringBuilder sb = new StringBuilder();
        while (i >= 0 || j >= 0 || carry > 0) {
            int x = i >= 0 ? a.charAt(i--) - '0' : 0;
            int y = j >= 0 ? b.charAt(j--) - '0' : 0;
            sum = x + y + carry;
            sb.append(sum % 2);
            carry = sum / 2;
        }
        return sb.reverse().toString();
    }
}

JavaScript实现

 1 /**
 2  * @param {string} a
 3  * @param {string} b
 4  * @return {string}
 5  */
 6 var addBinary = function(a, b) {
 7     let i = a.length - 1;
 8     let j = b.length - 1;
 9     let carry = 0;
10     let res = '';
11     while (i >= 0 || j >= 0 || carry > 0) {
12         if (i >= 0) {
13             carry += parseInt(a[i]);
14         }
15         i--;
16         if (j >= 0) {
17             carry += parseInt(b[j]);
18         }
19         j--;
20         res = (carry % 2) + res;
21         carry = parseInt(carry / 2);
22     }
23     return res;
24 };

LeetCode 题目总结