題目

  • 題目連結
  • 目標函式 : addBinary(sa, b)
    • Input : a: str、b: str
    • Output : str

解題概念

  • 題意 : 給定兩個 Binary string a 與 b，需要回傳兩者相加後的 Binary string

我的寫法

  • 想法 :
    • 將 a 與 b 切成 list，result 紀錄目前累積之字元，carry 記錄每回合進位量
    • 每回合需要判斷 :
      1. 將 a.pop() 加到 carry
      2. 將 b.pop() 加到 carry
      3. 將 carry % 2 加到 result 後方
      4. 將 carry // = 2
    • 最後將 result 反轉並回傳
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    def addBinary(self, a, b):
        
        carry = 0
        result = ''

        a = list(a) # 將 a 切成 list
        b = list(b) # 將 b 切成 list

        while len(a) != 0 or len(b) != 0  or carry != 0:
            if len(a) != 0: # 若 a 非空
                carry += int(a.pop())
            if len(b) != 0: # 若 b 非空 
                carry += int(b.pop())

            result += str(carry % 2) # 將 carry % 2 加到 result 後方

            carry //= 2

        return result[::-1] # 將 result 反轉並回傳
  • 成效 :
    • Time Complexity : $O(n)$
    • Runtime: 19 ms (faster than 70.67%)
    • Memory Usage: 13.4 MB (more than 41.21%)

解答 or 其他優秀寫法

  • 想法 : 採用 雙重指標 的方式，以節省儲存空間，其他相同
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    def addBinary(self, a, b):
        
        i = len(a) - 1 
        j = len(b) - 1
        carry = 0
        result = ""

        while i >= 0 or j >= 0 or carry != 0:

            if i >= 0 :
                carry += int(a[i])
                i -= 1
            if j >= 0 : 
                carry += int(b[j])
                j -= 1

            result += str(carry % 2)

            carry //= 2

        return res[::-1]
  • 成效 :
    • Time Complexity : $O(n)$
    • Runtime: 18 ms (faster than 74.87%)
    • Memory Usage: 13.4 MB (more than 41.21%)