67. Add Binary

1. 我的AC

方法一

• 把较短字符串的低位补上"0"
• 把两个字符串逐位相加，并在首位补上整数 0
• 从右边高位开始，逐位进位处理，去除首位的"0"
• 拼接列表

class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        lena = len(a)
        lenb = len(b)
        length = max(lena, lenb)
        if lena < lenb:
            a = '0' * (lenb - lena) + a
        elif lenb < lena:
            b = '0' * (lena - lenb) + b

        num = []
        for i in range(length):
            num.append(int(a[i]) + int(b[i]))
        num = [0] + num
        print num
        
        for i in range(length, 0, -1):
            if num[i] == 3:
                num[i] = 1
                num[i-1] += 1
            elif num[i] == 2:
                num[i] = 0
                num[i-1] += 1                
        if num[0] == 0:
            del num[0]
        return "".join(str(digit) for digit in num)       

方法二

• python 的二进制运算

class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        return bin(int(a, 2) + int(b, 2))[2:]  

方法三

• 递归，当两个加数都是1时要进位

class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        if len(a) == 0: return b
        if len(b) == 0: return a
        if a[-1] == '1' and b[-1] == '1':
            return self.addBinary(self.addBinary(a[:-1], b[:-1]), '1') + '0'
        elif a[-1] == '0' and b[-1] == '0':
            return self.addBinary(a[:-1], b[:-1]) + '0'
        else:
            return self.addBinary(a[:-1], b[:-1]) + '1'

---

2. 小结

1. 十进制数字符串转换为相应的二进制串

• int(a, 2) 表示a是二进制数，将它转换成十进制数

>>> bin(int('256', 10))
'0b100000000'

2. 二进制串转换为相应的十进制整数字符串

>>> str(int('0b100000000', 2))
'256'

---

3.做题步骤

• 想5分钟，感觉自己会做的，先自己做一遍，半小时一小时都没关系，争取 AC。
• 之后再看最高点赞的1-2个答案。
• 5分钟不会直接看高票答案