算法

(模拟) $O(n)$

模拟两个数的加法，维护一个进位

C++ 代码

class Solution {
public:
    string addBinary(string a, string b) {
        int m = a.size(), n = b.size();
        if (m < n) return addBinary(b, a);

        int carry = 0, i = m - 1, j = n - 1;
        string res;
        while(j >= 0 || i >= 0 || carry){
            int num1 = i >= 0 ? a[i--] - '0' : 0;
            int num2 = j >= 0 ? b[j--] - '0' : 0;
            int num = num1 + num2 + carry;
            carry = num / 2;
            res.push_back(num % 2 + '0');
        }

        return string(res.rbegin(), res.rend());
    }
};

Java 代码

class Solution {
    public String addBinary(String a, String b) {
        int ai = a.length() - 1;
        int bi = b.length() - 1;
        StringBuilder res = new StringBuilder();
        int carry = 0;
        while (ai >= 0 || bi >= 0) {
            int cur = carry;
            if (ai >= 0) {
                cur += a.charAt(ai--) - '0';
            }
            if (bi >= 0) {
                cur += b.charAt(bi--) - '0';
            }
            res.append("" + cur % 2);
            carry = cur / 2;
        }
        while (carry > 0) {
            res.append("" + carry % 2);
            carry /= 2;
        }
        return res.reverse().toString();
    }
}

Python 代码

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        def add(x, y, carry):
            s = x + y + carry
            return (s // 2, s % 2)

        ml = max(len(a), len(b))
        res = ""
        carry = 0
        a = a.rjust(ml, '0')
        b = b.rjust(ml, '0')
        for i in range(ml - 1, -1, -1):
            carry, s = add(int(a[i]), int(b[i]), carry)
            res = str(s) + res
        return '1' + res if carry else res