算法練習 Leetcode 力扣 67. Add Binary 解法

feellikelearning June 19, 2020 0 Comments

和add strings基本一樣。

關鍵點：
從右邊開始加
把長的input作為第一個，給最左邊加0用來進位（如果需要的話），最後看要不要去掉
python裏面要用ord，chr 來做char/ascii轉換

python解法

class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        if a is None or len(a) == 0:
            return b
        if b is None or len(b) == 0:
            return a
        if len(a) < len(b):
            return self.addBinary(b, a)
        n1 = ['0'] + [c for c in a]
        n2 = [c for c in b]
        
        i = len(n1) - 1
        j = len(n2) - 1
        while i >= 0:
            if j >= 0:
                n1[i] = chr(ord(n1[i]) + ord(n2[j]) - ord('0'))
            if n1[i] > '1':
                n1[i] = chr(ord(n1[i]) - 2)
                n1[i - 1] = chr(ord(n1[i - 1]) + 1)
            i -= 1
            j -= 1
        ans = ''.join(n1)
        if ans[0] == '0':
            return ans[1:]
        return ans