題目描述:給定兩個二進位字串 a 和 b,回傳它們相加的結果(同樣以二進位字串表示)。字串不含前導零(除非本身就是 "0")。
解題思路:模擬手動二進位加法的過程,從最低位(字串末尾)開始向左逐位相加,並處理進位(carry)。
i、j 分別指向 a 和 b 的末尾。carry = 0。i >= 0、j >= 0 或 carry != 0 時持續迴圈:
carry。sum % 2,更新 carry = sum / 2。使用 result 字串在尾端 append 再反轉,比每次前插(O(n) 操作)更有效率。
時間複雜度:O(max(m, n)) — m 和 n 分別為字串 a 和 b 的長度。迴圈執行次數等於較長字串的長度加上可能的最後進位,為線性時間。reverse 同樣為 O(max(m, n))。
空間複雜度:O(max(m, n)) — 結果字串的長度最多為 max(m, n) + 1(最高位可能產生進位)。
1. Set i = a.size() - 1, j = b.size() - 1, carry = 0, result = "". 2. While i >= 0 OR j >= 0 OR carry != 0: a. sum = carry. b. If i >= 0: sum += a[i] - '0'; decrement i. c. If j >= 0: sum += b[j] - '0'; decrement j. d. Append (sum % 2) as a character to result. e. carry = sum / 2. 3. Reverse result. 4. Return result.
內建大整數轉換 O(m+n):在支援大整數的語言(如 Python)中,可直接用 int(a, 2) + int(b, 2) 轉換為整數相加,再用 bin() 轉回二進位字串。C++ 中因整數有位元上限,此法不適用於超長字串。
逐位 XOR + 進位模擬(位元操作風格)O(m+n):本質與上述方法相同,但可以用 XOR 計算當前位(無進位加法),用 AND 後左移計算進位。在硬體描述語言(HDL)設計中這種加法器風格更常見,但在軟體層面並無效能優勢。