二進位操作: 兩個二進位字串相加 Add Binary_Leetcode #67

Sasun Bughdaryan on Unsplash

題目敘述 Add Binary

題目給定兩個二進位字串a, b

請計算a+b二進位加法的答案，最後以字串的形式輸出。

測試範例

Example 1:

Input: a = "11", b = "1"
Output: "100"

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"

約束條件

Constraints:

• 1 <= a.length, b.length <= 10^4

字串a 和 字串b的長度都介於 1個 ~ 一萬個字元。

• a and b consist only of '0' or '1' characters.

字串a 和 字串b只會包含'0'或'1'

• Each string does not contain leading zeros except for the zero itself.

前面沒有無意義的leading zero補零

演算法 模擬二進位加法

模擬二進位加法，逢二就進位，從最低位元逐項累加到最高位元。

0 + 0 = 0

0 + 1 = 1

1 + 0 = 0

1 + 1 = 0 ，同時傳遞進位1給左側的高位元

最後，以字串的形式輸出答案。

程式碼 模擬二進位加法

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        
        result = ''

        a = list(map(int, a))
        b = list(map(int, b))

        carry = 0
        while a or b or carry:
            digit_sum = 0
            
            if a:  digit_sum += a.pop()
            if b:  digit_sum += b.pop()
            digit_sum += carry

            carry, digit_sum = digit_sum // 2, digit_sum % 2

            result = str(digit_sum) + result

        return result

複雜度分析

時間複雜度:O(m+n)

總計算時間依賴於長度較長的那個字串，依然是線性時間演算法。

空間複雜度: O(m+n)

輸出總長度也依賴長度較長的那個字串，依然是線性空間演算法。

Reference

[1] Add Binary - LeetCode