今天是紀錄LeetCode解題的第六十七天

第六十七題題目：Given two binary strings a and b, return their sum as a binary string.

給定兩個二進位字串a和b，回傳它們的二進位總和字串

解題思路

從a和b的尾端相加，首先設定i = len(a) - 1、j = len(b) - 1和curry = 0，前兩個指標為目前a和b的哪兩個位元要相加，curry為紀錄是否有進位，當i >= 0或j >= 0或curry > 0時，我們就要不斷地做相加，每一次相加完，將目前的總和total % 2存入res作為該位元，並記錄是否有進位curry = total // 2

程式碼

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        i, j = len(a) - 1, len(b) - 1
        carry = 0
        res = []

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

            res.append(str(total % 2))   #寫入此位
            carry = total // 2           #更新進位

        return ''.join(res[::-1])

執行過程

初始狀態

• a = "11"
• b = "1"
• i = 1
• j = 0
• carry = 0
• res = []

第一次迴圈

• total = curry → total = 0
• if i >= 0 → total += int(a[i]) → total += int(a[1]) → total = 1
• i -= 1 → i = 0

• if j >= 0 → total += int(b[j]) → total += int(b[0]) → total = 2
• j -= 1 → j = -1

• res.append(str(total % 2)) → res.append(str(2 % 2)) → res = [0]
• carry = total // 2 → carry = 1

第二次迴圈

• total = curry → total = 1
• if i >= 0 → total += int(a[i]) → total += int(a[0]) → total = 2
• i -= 1 → i = -1

• if j >= 0 → False

• res.append(str(total % 2)) → res.append(str(2 % 2)) → res = [0,0]
• carry = total // 2 → carry = 1

第三次迴圈

• total = curry → total = 1
• if i >= 0 → False

• if j >= 0 → False

• res.append(str(total % 2)) → res.append(str(1 % 2)) → res = [0,0,1]
• carry = total // 2 → carry = 0

最後回傳反轉後的res，也就是"100"就是答案了