[Leetcode][python]Add Binary/二进制求和

桃扇骨 2022-06-07 07:44 174阅读 0赞

## 题目大意 ##

对两个二进制的字符串求和。

## 解题思路 ##

该题较为简单，面试遇到硬写，不必非要按照如下代码写。

二进制数相加，并且保存在string中，要注意的是如何将string和int之间互相转换，并且每位相加时，会有进位的可能，会影响之后相加的结果。而且两个输入string的长度也可能会不同。这时我们需要新建一个string，它的长度是两条输入string中的较大的那个，并且把较短的那个输入string通过在开头加字符‘0’来补的较大的那个长度。这时候我们逐个从两个string的末尾开始取出字符，然后转为数字，想加，如果大于等于2，则标记进位标志carry，并且给新string加入一个字符‘0’。

## 代码 ##

从后往前依次相加，计算该位的值和进位值。最高位如要进位就添加一个位，最后把结果翻转。

class Solution(object):
        def addBinary(self, a, b):
            """
            :type a: str
            :type b: str
            :rtype: str
            """
            result = []
            val = 0
            carry = 0
            lenA = len(a)
            lenB = len(b)
            if lenA < lenB: # 注意坑：确保A比B长, 所以值长度也要交换
                a, b = b, a
                lenA, lenB = lenB, lenA 
            for i in range(lenA):  
                print carry
                val = carry
                val += int(a[-(i+1)])  # 从最后一位开始取
                if i < lenB:
                    val += int(b[-(i+1)])
                print val, carry
                carry = val // 2
                val = val % 2  # 注意坑：注意这里val变化了，必须放下面
                print val, carry
                result.append(str(val))
    
            if carry:
                result.append(str(carry))
            return ''.join(result[::-1])

## 总结 ##

py2和py3的除法区别：  
在python2中// = / 都为整数（如1）,而在3中，3 / 2 = 1.5, 3 // 2 = 1