【leetcode】67.二进制求和

前言：剑指offer刷题系列

问题：

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

示例：

输入：a = "1010", b = "1011"
输出："10101"

思路1：

我们为了避免去判断谁大谁小的边界问题，直接把最短的字符串前面先补0。设置一个保存进位的数，从低到高遍历，逢二进一。

先通过两个 while 循环将输入的二进制字符串 a 和 b 的长度补齐，使它们的长度相等。如果其中一个字符串较短，就在它的前面添加0，以保证两个二进制数的位数相同。

然后，定义了一个变量 tmp 用来存储进位信息，初始化为0。同时，将字符串 a 和 b 一起转换为列表，以便进行逐位相加操作。

接下来，通过一个 for 循环从字符串的最后一位开始逐位相加，从低位到高位。具体的相加规则如下：

• 如果当前位的数字是0，1，2，3中的0，那么将进位 tmp 和当前位相加，并根据相加结果更新当前位。
• 如果相加结果是3，表示当前位和进位都是1，那么当前位变为0，进位为1。
• 如果相加结果是2，表示当前位和进位中有一个是1，那么当前位变为0，进位为1。
• 如果相加结果是1，表示当前位和进位中只有一个是1，那么当前位变为1，进位为0。

最后，在循环结束后，检查是否还有进位 tmp。如果有进位，就在结果字符串的最前面添加一个 “1”。最终，返回结果字符串。

时间复杂度：O(n)

空间复杂度：O(n)

基于上述思考，代码如下：

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        while len(a) > len(b):
            b = "0" + b

        while len(a) < len(b):
            a = "0" + a

        tmp = 0
        a, b = list(a), list(b)
        for i in range(len(a) - 1, -1, -1):
            cur = int(a[i]) + int(b[i]) + tmp
            if cur == 3:
                b[i] = "1"
                tmp = 1
            elif cur == 2:
                b[i] = "0"
                tmp = 1
            elif cur == 1:
                b[i] = "1"
                tmp = 0
            else:
                b[i] = "0"
                tmp = 0
        if tmp == 1:
            b = ["1"] + b
        return "".join(b)

执行结果如下图：

思路2：

首先，将输入的二进制字符串 a 和 b 使用 int(a, 2) 和 int(b, 2) 转换为整数，基数为2，表示将二进制字符串转换为整数。然后，这两个整数相加，得到它们的和。

接下来，将上一步得到的和转换为二进制字符串形式，并通过切片操作去掉字符串的前缀"0b"，以获取纯二进制数表示。

最终，该方法返回两个二进制数相加后的结果作为二进制字符串。

基于上述思考，代码如下：

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

执行结果如下图：