Question:

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"

Thinking:

  • Method:
    • 参考67
class Solution {
    public String addBinary(String a, String b) {
        if(a == null || b == null) return "";
        int aLen = a.length();
        int bLen = b.length();
        int[] result = new int[Math.max(aLen, bLen) + 1];
        int len = result.length;
        int carry = 0;
        int aVal = 0;
        int bVal = 0;
        while(aLen > 0 || bLen > 0){
            aVal = aLen > 0 ? (int)(a.charAt(--aLen)) - 48 : 0;
            bVal = bLen > 0 ? (int)(b.charAt(--bLen)) - 48 : 0;
            result[--len] = (aVal + bVal + carry) % 2;
            carry = (aVal + bVal + carry) / 2;
        }
        StringBuilder sb = new StringBuilder();
        if(carry == 0){
            for(int i = 1; i < result.length; i++)
                sb.append(result[i]);

        }else{
            result[0] = 1;
            for(int i = 0; i < result.length; i++)
                sb.append(result[i]);
        }
        return sb.toString();
    }
}

二刷

还是像十进制相加一样。

class Solution {
    public String addBinary(String a, String b) {
        char[] aArr = a.toCharArray();
        char[] bArr = b.toCharArray();
        int carry = 0, aIndex = aArr.length - 1, bIndex = bArr.length - 1;
        StringBuilder sb = new StringBuilder();
        while(aIndex >= 0 || bIndex >= 0){
            if(aIndex >= 0 && bIndex >= 0){
                sb.append(((aArr[aIndex] - '0') + (bArr[bIndex] - '0') + carry) % 2);
                carry = ((aArr[aIndex--] - '0') + (bArr[bIndex--] - '0') + carry) / 2;
            }else if(aIndex >= 0 && bIndex < 0){
                sb.append(((aArr[aIndex] - '0') + carry) % 2);
                carry = (aArr[aIndex--] - '0' + carry) / 2;
            }else{
                sb.append(((bArr[bIndex] - '0') + carry) % 2);
                carry = (bArr[bIndex--] - '0' + carry) / 2;
            }
        }
        if(carry == 1) sb.append(1);
        return sb.reverse().toString();
    }
}