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

蛮三刀酱

发布于 2019-03-26 16:20:27

7080

发布于 2019-03-26 16:20:27

文章被收录于专栏：蛮三刀的后端开发专栏

题目大意

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

解题思路

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

二进制数相加，并且保存在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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017年10月15日，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度