67. Add Binary

Leetcode Math String

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"

分析

这道题目其实想让我们模拟二进制加法。

public String addBinary(String a, String b) {
    int a_len = a.length(), b_len = b.length();
    int n = Math.max(a_len, b_len);
    int add = 0, d;
    StringBuilder res = new StringBuilder();
    for (int i = 0; i < n; i++) {
        if ( i < a_len && i < b_len) {
            d = add + a.charAt(a_len - 1  - i) - '0' + b.charAt(b_len -1 - i) - '0';
        } else if (i < a_len) {
            d = add + a.charAt(a_len - 1 - i) - '0';
        } else {
            d = add + b.charAt(b_len - 1 - i) - '0';
        }


        if (d == 0) {
            res.append("0");
            add = 0;
        } else if (d == 1) {
            res.append("1");
            add = 0;
        } else if (d == 2){
            res.append("0");
            add = 1;
        } else if (d == 3) {
            res.append("1");
            add = 1;
        }

    }

    if (add == 1) res.append("1");

    return res.reverse().toString();
}

在论坛上看到的比较优雅的代码

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 (j >= 0) sum += b.charAt(j--) - '0';
        if (i >= 0) sum += a.charAt(i--) - '0';
        sb.append(sum % 2);
        carry = sum / 2;
    }
    if (carry != 0) sb.append(carry);
    return sb.reverse().toString();
}

我写的代码更快，后面的更好看一些。