LeetCode 67. Add Binary：二進制字符串相加模擬

題目描述

給定兩個二進制字符串 a、b，返回它們的和（二進制字符串）。例如 "11" + "1" = "100"。

解題思路：雙指針從右向左模擬加法

1. 初始化進位 carry = 0，結果字符串 res = ""。
2. 雙指針 i = a.size()-1, j = b.size()-1 從右向左遍歷。
3. 每輪計算 sum = (a[i]-'0') + (b[j]-'0') + carry。
4. 當前位結果 sum % 2 加到 res 前端，carry = sum / 2。
5. 處理剩餘較長字符串，最後若 carry 仍為 1 加到最前端。

C++ 代碼實現

class Solution {
public:
    string addBinary(string a, string b) {
        int i = a.length() - 1, j = b.length() - 1, carry = 0;
        string res;
        while (i >= 0 || j >= 0 || carry) {
            int sum = carry;
            if (i >= 0) sum += a[i--] - '0';
            if (j >= 0) sum += b[j--] - '0';
            res.push_back('0' + (sum & 1));
            carry = sum >> 1;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

優化點

• 使用 push_back + 最後 reverse 避免字符串前端插入的 O(n²) 開銷。
• 位運算 sum & 1、sum >> 1 替代取模除法。
• 統一循環條件 i>=0 || j>=0 || carry 簡化代碼。

複雜度

• 時間：O(max(|a|, |b|))。
• 空間：O(max(|a|, |b|)) 存儲結果。