Yoru Karu Studio
Yoru Karu Studio

LeetCode 解題思路：67. Add Binary（二進位加法）

掌握進位制運算與字串處理的精髓

luk 收錄於 Leetcode
 約 1400 字 預計閱讀 7 分鐘 

LeetCode 解題思路：Add Binary（二進位加法）

題目描述

給定兩個二進位字串 a 和 b，返回它們的和作為一個二進位字串。

這道題目考驗我們對進位制運算的理解，以及如何優雅地處理字串操作。

範例

範例 1：

輸入：a = "11", b = "1"
輸出："100"
解釋：11 + 1 = 100（二進位）

範例 2：

輸入：a = "1010", b = "1011"
輸出："10101"
解釋：1010 + 1011 = 10101（二進位）

限制條件

  • 1 <= a.length, b.length <= 10⁴
  • a 和 b 僅由字符 '0' 或 '1' 組成
  • 字串如果不是 "0"，就不含前導零

核心概念

1. 理解二進位加法規則

在深入解題之前，讓我們先回顧二進位加法的基本規則：

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10（結果為 0，進位 1）
1 + 1 + 1 = 11（結果為 1，進位 1）

視覺化理解 

範例：11 + 1 = 100

    1 1  ← a
+     1  ← b
-------
  1 0 0  ← 結果

步驟分解：
位置:  2 1 0
      ─────
第0位: 1+1 = 10 → 結果=0, 進位=1
第1位: 1+0+1(進位) = 10 → 結果=0, 進位=1  
第2位: 0+0+1(進位) = 1 → 結果=1, 進位=0

2. 為什麼這題適合從右到左處理？

關鍵洞察：加法運算天然就是從低位到高位進行的！

  • 需要處理進位
  • 兩個字串長度可能不同
  • 最終可能產生額外的最高位

解法一：模擬二進位加法（推薦）

思路

模擬手算二進位加法的過程：

  1. 從最低位（最右邊）開始
  2. 逐位相加，處理進位
  3. 如果一個數字已經處理完，視為 0
  4. 最後別忘了檢查是否還有進位

程式碼實現 

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        result = []
        carry = 0
        i = len(a) - 1  # a 的指標，從最後開始
        j = len(b) - 1  # b 的指標，從最後開始
        
        # 當還有數字要處理或還有進位時繼續
        while i >= 0 or j >= 0 or carry:
            # 取得當前位的值
            digit_a = int(a[i]) if i >= 0 else 0
            digit_b = int(b[j]) if j >= 0 else 0
            
            # 計算當前位的總和
            total = digit_a + digit_b + carry
            
            # 當前位的結果
            result.append(str(total % 2))
            
            # 更新進位
            carry = total // 2
            
            # 移動指標
            i -= 1
            j -= 1
        
        # 反轉結果（因為我們是從低位到高位計算的）
        return ''.join(reversed(result))

執行過程視覺化

讓我們詳細追蹤 a = "1010", b = "1011"：

初始狀態：
a = "1010"
        ↑
        i=3
b = "1011"  
        ↑
        j=3
carry = 0

步驟 1：處理最低位
digit_a = 0, digit_b = 1, carry = 0
total = 0 + 1 + 0 = 1
結果 = ['1'], carry = 0

步驟 2：處理第二位
digit_a = 1, digit_b = 1, carry = 0
total = 1 + 1 + 0 = 2
結果 = ['1', '0'], carry = 1

步驟 3：處理第三位
digit_a = 0, digit_b = 0, carry = 1
total = 0 + 0 + 1 = 1
結果 = ['1', '0', '1'], carry = 0

步驟 4：處理第四位
digit_a = 1, digit_b = 1, carry = 0
total = 1 + 1 + 0 = 2
結果 = ['1', '0', '1', '0'], carry = 1

步驟 5：處理剩餘進位
i = -1, j = -1, carry = 1
total = 0 + 0 + 1 = 1
結果 = ['1', '0', '1', '0', '1']

反轉後：'10101'

為什麼這樣有效？

  1. 處理不等長：較短的字串用 0 補齊
  2. 進位傳遞：每次計算都考慮上一位的進位
  3. 結果構建：從低位到高位構建，最後反轉

解法二：使用內建函數（Python 特有）

思路

利用 Python 強大的內建函數，先轉換為十進位，計算後再轉回二進位。

程式碼實現 

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        # int(x, 2) 將二進位字串轉為十進位整數
        # bin() 將十進位整數轉為二進位字串
        # [2:] 去掉 '0b' 前綴
        return bin(int(a, 2) + int(b, 2))[2:]

這個方法的優缺點

優點：

  • 程式碼極其簡潔
  • 不容易出錯
  • 執行速度快

缺點：

  • 面試時可能不被接受（太簡單了）
  • 沒有展現演算法思維
  • 其他語言可能沒有這樣方便的函數

解法三：更直觀的實現

思路

先補齊兩個字串的長度，然後從右到左逐位處理。

程式碼實現 

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        # 補齊長度
        max_len = max(len(a), len(b))
        a = a.zfill(max_len)
        b = b.zfill(max_len)
        
        result = []
        carry = 0
        
        # 從右到左處理
        for i in range(max_len - 1, -1, -1):
            bit_sum = int(a[i]) + int(b[i]) + carry
            result.append(str(bit_sum % 2))
            carry = bit_sum // 2
        
        # 處理最後的進位
        if carry:
            result.append('1')
        
        return ''.join(reversed(result))

常見錯誤與陷阱

錯誤 1：忘記處理不同長度 

# ❌ 錯誤！沒有處理長度不同的情況
def addBinary(self, a: str, b: str) -> str:
    result = []
    carry = 0
    for i in range(len(a)-1, -1, -1):
        total = int(a[i]) + int(b[i]) + carry  # b[i] 可能越界！
        # ...

錯誤 2：忘記最後的進位 

# ❌ 錯誤！遺漏最後的進位
def addBinary(self, a: str, b: str) -> str:
    result = []
    carry = 0
    # ... 處理邏輯 ...
    
    # 忘記檢查最後是否還有進位
    return ''.join(reversed(result))

錯誤 3：結果沒有反轉 

# ❌ 錯誤！忘記反轉結果
def addBinary(self, a: str, b: str) -> str:
    result = []
    # ... 從右到左處理 ...
    
    return ''.join(result)  # 應該要反轉！

錯誤 4：型別轉換問題 

# ❌ 錯誤！忘記轉換型別
def addBinary(self, a: str, b: str) -> str:
    result = []
    carry = 0
    # ...
    result.append(total % 2)  # 應該是 str(total % 2)

進階思考

1. 如果是其他進位制怎麼辦？

我們可以寫一個通用的進位制加法函數：

def addBase(a: str, b: str, base: int) -> str:
    result = []
    carry = 0
    i, j = len(a) - 1, len(b) - 1
    
    while i >= 0 or j >= 0 or carry:
        digit_a = int(a[i]) if i >= 0 else 0
        digit_b = int(b[j]) if j >= 0 else 0
        
        total = digit_a + digit_b + carry
        result.append(str(total % base))
        carry = total // base
        
        i -= 1
        j -= 1
    
    return ''.join(reversed(result))

# 使用範例
addBase("11", "1", 2)    # 二進位
addBase("99", "1", 10)   # 十進位
addBase("77", "1", 8)    # 八進位

2. 處理十六進位 

def addHex(a: str, b: str) -> str:
    hex_to_dec = {
        '0':0, '1':1, '2':2, '3':3, '4':4, '5':5, '6':6, '7':7,
        '8':8, '9':9, 'A':10, 'B':11, 'C':12, 'D':13, 'E':14, 'F':15
    }
    dec_to_hex = {v: k for k, v in hex_to_dec.items()}
    
    result = []
    carry = 0
    i, j = len(a) - 1, len(b) - 1
    
    while i >= 0 or j >= 0 or carry:
        digit_a = hex_to_dec[a[i].upper()] if i >= 0 else 0
        digit_b = hex_to_dec[b[j].upper()] if j >= 0 else 0
        
        total = digit_a + digit_b + carry
        result.append(dec_to_hex[total % 16])
        carry = total // 16
        
        i -= 1
        j -= 1
    
    return ''.join(reversed(result))

3. 遞迴解法 

def addBinary(self, a: str, b: str) -> str:
    def helper(a, b, carry):
        if not a and not b:
            return '1' if carry else ''
        
        # 取最後一位，如果沒有則為 0
        bit_a = int(a[-1]) if a else 0
        bit_b = int(b[-1]) if b else 0
        
        # 計算當前位
        total = bit_a + bit_b + carry
        current = str(total % 2)
        
        # 遞迴處理剩餘部分
        remaining = helper(a[:-1] if a else '', 
                         b[:-1] if b else '', 
                         total // 2)
        
        return remaining + current
    
    return helper(a, b, 0) or '0'

4. 位元運算解法（進階） 

def addBinary(self, a: str, b: str) -> str:
    # 轉為整數
    x, y = int(a, 2), int(b, 2)
    
    # 位元運算加法
    while y:
        answer = x ^ y  # 不考慮進位的加法
        carry = (x & y) << 1  # 進位
        x, y = answer, carry
    
    # 轉回二進位字串
    return bin(x)[2:]

複雜度分析

時間複雜度：O(max(m, n))

  • m 和 n 分別是兩個字串的長度
  • 需要遍歷較長字串的每一位

空間複雜度：O(max(m, n))

  • 需要存儲結果字串
  • 結果最多比最長的輸入多一位

相關題目推薦

這些題目都涉及類似的進位處理或字串操作：

  1. LeetCode 2: Add Two Numbers - 鏈表版本的加法
  2. LeetCode 66: Plus One - 陣列加一
  3. LeetCode 415: Add Strings - 字串加法（十進位）
  4. LeetCode 445: Add Two Numbers II - 鏈表加法（不反轉）
  5. LeetCode 43: Multiply Strings - 字串乘法
  6. LeetCode 989: Add to Array-Form of Integer - 陣列形式的整數加法

實戰技巧總結

1. 處理不等長字串的模板 

def processStrings(s1, s2):
    i = len(s1) - 1
    j = len(s2) - 1
    
    while i >= 0 or j >= 0:
        val1 = s1[i] if i >= 0 else default_value
        val2 = s2[j] if j >= 0 else default_value
        
        # 處理邏輯
        
        i -= 1
        j -= 1

2. 調試技巧 

def addBinary(self, a: str, b: str) -> str:
    print(f"輸入: a='{a}', b='{b}'")
    result = []
    carry = 0
    i, j = len(a) - 1, len(b) - 1
    
    step = 0
    while i >= 0 or j >= 0 or carry:
        digit_a = int(a[i]) if i >= 0 else 0
        digit_b = int(b[j]) if j >= 0 else 0
        total = digit_a + digit_b + carry
        
        print(f"步驟 {step}: {digit_a} + {digit_b} + {carry} = {total}")
        print(f"  結果位: {total % 2}, 進位: {total // 2}")
        
        result.append(str(total % 2))
        carry = total // 2
        i -= 1
        j -= 1
        step += 1
    
    final_result = ''.join(reversed(result))
    print(f"最終結果: '{final_result}'")
    return final_result

3. 完整測試案例 

def test_addBinary():
    test_cases = [
        # (a, b, 期望結果)
        ("11", "1", "100"),
        ("1010", "1011", "10101"),
        ("0", "0", "0"),
        ("0", "1", "1"),
        ("1", "0", "1"),
        ("1", "1", "10"),
        ("111", "111", "1110"),
        ("1", "111", "1000"),
        ("10101010", "11110000", "110011010"),
        ("1111", "1111", "11110"),
        ("10000000000", "1", "10000000001")
    ]
    
    solution = Solution()
    for a, b, expected in test_cases:
        result = solution.addBinary(a, b)
        status = "✅" if result == expected else "❌"
        print(f"{status} {a} + {b} = {result} (期望: {expected})")

4. 效能優化技巧 

# 使用列表推導式
def addBinary(self, a: str, b: str) -> str:
    # 反轉字串，方便從低位開始處理
    a, b = a[::-1], b[::-1]
    max_len = max(len(a), len(b))
    
    result = []
    carry = 0
    
    for i in range(max_len + 1):
        digit_a = int(a[i]) if i < len(a) else 0
        digit_b = int(b[i]) if i < len(b) else 0
        
        total = digit_a + digit_b + carry
        if i < max_len or total > 0:
            result.append(str(total % 2))
        carry = total // 2
    
    return ''.join(result[::-1])

總結

這道二進位加法題目完美展示了：

  1. 進位制運算的本質：無論是二進位還是十進位，加法的原理相同
  2. 字串處理技巧：從右到左處理、處理不等長、結果反轉
  3. 邊界條件的重要性：空字串、全零、最後的進位
  4. 簡潔與清晰的平衡：內建函數雖簡潔，但展現思維過程更重要
  5. 通用性思考：從二進位擴展到任意進位制

記住核心思想：模擬手算過程，細心處理每個細節！

練習建議

  1. 理解基礎：先在紙上手算幾個例子，理解二進位加法
  2. 視覺化過程：畫出指標移動的過程，理解演算法執行
  3. 邊界測試：特別注意各種邊界條件
  4. 多種實現：嘗試不同的實現方式，比較優缺點
  5. 擴展練習：
    • 實現二進位減法
    • 實現其他進位制的運算
    • 嘗試位元運算的解法
  6. 相關練習：完成推薦的相關題目，鞏固知識點

通過這道題目，你不僅學會了二進位加法，更重要的是掌握了處理字串運算的通用模式！

更新於 2024-12-28 
CC BY-NC-SA 4.0
閱讀原始文檔
LeetcodeAlgorithmStringMath
返回 | 主頁
0%