Leetcode 67. 二进制求和（易）

看似简单，实际上解法多样，需要多注意，特别是位运算方法。
计算 x 和 y 的无进位相加结果：answer = x^y。
计算 x 和 y 的进位：carry = (x & y) << 1。
完成本次循环，更新 x = answer，y = carry。

题目

给定两个二进制字符串，返回他们的和（用二进制表示）。
输入为非空字符串且只包含数字 1 和 0。

示例

示例 1:

1
2
输入: a = "11", b = "1"
输出: "100"
示例 2:
1
2
输入: a = "1010", b = "1011"
输出: "10101"

考察知识点

数组、位运算

核心思想

方法一、进制转换相加
将 a 和 b 转换为十进制整数，求和，将求和结果转换为二进制整数。

方法二、逐位计算
这种写法巧妙又简洁，用了两个指针分别指向a和b的末尾，然后每次取出一个字符，转为数字，若无法取出字符则按0处理，然后定义进位carry，carry初始化为0，将三者加起来，对2取余即为当前位的数字，对2取商即为当前进位的值，记得最后还要判断下carry，如果为1的话，要在结果最前面加上一个1。

67_sl_3.png

方法三、位运算
XOR 操作得到两个数字无进位相加的结果。

xor4.png

进位和两个数字与操作结果左移一位对应。

carry2.png

现在问题被简化为：1、首先计算两个数字的无进位相加结果和进位，2、然后计算无进位相加结果与进位之和。同理求和问题又可以转换成上一步，直到进位为 0 结束。

算法
- 把 a 和 b 转换成整型数字 x 和 y，x 保存结果，y 保存进位。 - 当进位不为 0：y != 0： - 计算当前 x 和 y 的无进位相加结果：answer = x^y。 - 计算当前 x 和 y 的进位：carry = (x & y) << 1。 - 完成本次循环，更新 x = answer，y = carry。 - 返回 x 的二进制形式。

Python版本

  • 方法一的实现（不推荐，写算法题不能老是调用内部API）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def binaryStr2Decima(self, s):
        count = 0
        res = 0
        for i in range(len(s)-1, -1, -1):
            res += (int(s[i]) * (2 ** count))
            count += 1

        return res

    def addBinary(self, a: str, b: str) -> str:
        # 2进制转10进制
        a = self.binaryStr2Decima(a)
        b = self.binaryStr2Decima(b)
        # 相加
        sum = a + b
        # 10进制转2进制
        sum = str(bin(sum))[2:]
        return sum

# 另一种简洁的写法
class Solution:
    def addBinary(self, a, b) -> str:
        return '{0:b}'.format(int(a, 2) + int(b, 2))

时间复杂度：\(O(m+n)\)，m是a字符串的长度，n是b字符串的长度。
执行用时 :48 ms, 在所有 Python3 提交中击败了27.90%的用户
内存消耗 :13.4 MB, 在所有 Python3 提交中击败了5.01%的用户

  • 方法二的实现（推荐，思路简单明了）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        res = ""
        m = len(a) - 1
        n = len(b) - 1
        carry = 0
        while m >= 0 or n >= 0:
            p = 0 if m < 0 or a[m] == '0' else 1
            q = 0 if n < 0 or b[n] == '0' else 1
            sum = p + q + carry
            res = str(sum % 2) + res  # 放在res前面的位置
            carry = sum // 2  # 注意这里用整除
            m -= 1
            n -= 1

        return "1" + res if carry == 1 else res  # 最后还要判断下carry，如果为1的话，要在结果最前面加上一个1。  


Input = ["11", "1010"]
Input1 = ["1", "1011"]
Answer = ["100", "10101"]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        reslut = solution.addBinary(Input[i], Input1[i])
        if reslut == Answer[i]:
            print(True)
        else:
            print(False)
            print(Input[i])

时间复杂度：\(O(max(N,M))\)，其中 N 和 M 是输入字符串 a 和 b 的长度。
空间复杂度：\(O(max(N,M))\)，存储求和结果。
执行用时 :48 ms, 在所有 Python3 提交中击败了27.90%的用户
内存消耗 :13.5 MB, 在所有 Python3 提交中击败了5.01%的用户

  • 方法三的实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def addBinary(self, a, b) -> str:
        x, y = int(a, 2), int(b, 2)
        while y:
            answer = x ^ y
            carry = (x & y) << 1
            x, y = answer, carry
        return bin(x)[2:]

# 另外一个四行代码的版本
class Solution:
    def addBinary(self, a, b) -> str:
        x, y = int(a, 2), int(b, 2)
        while y:
            x, y = x ^ y, (x & y) << 1
        return bin(x)[2:]

时间复杂度：\(O(N+M)\)，其中 NN 和 MM 是输入字符串 aa 和 bb 的长度。 空间复杂度：\(O(max(N,M))\)，存储计算结果。 执行用时 :36 ms, 在所有 Python3 提交中击败了75.62%的用户 内存消耗 :13.3 MB, 在所有 Python3 提交中击败了5.01%的用户

有效语法糖

1、Python 2进制、8进制、10进制、16进制之间的转换，数值和字符串之间的转换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 字符串2进制转int 10进制
>>> a = "10101"
>>> a = int(a, 2)
>>> a
21
# int 10进制转字符串2进制
>>> a = 21
>>> a = '{0:b}'.format(a)
>>> a
'10101'

# int 2进制、8进制、10进制、16进制之间的转换
>>> dec = 21
>>> print("十进制数为：", dec)
十进制数为： 21
>>> print("转换为二进制为：", bin(dec))
转换为二进制为： 0b10101
>>> print("转换为八进制为：", oct(dec))
转换为八进制为： 0o25
>>> print("转换为十六进制为：", hex(dec))
转换为十六进制为： 0x15

参考连接

LeetCode官方题解