题目描述

[EN | CN]

给你两个二进制字符串,返回它们的和(用二进制表示)。

输入为 非空 字符串且只包含数字 1 和 0

示例 1:

1
2
输入: a = "11", b = "1"
输出: "100"

示例 2:

1
2
输入: a = "1010", b = "1011"
输出: "10101"

提示:

  • 每个字符串仅由字符 '0''1' 组成。
  • 1 <= a.lengthb.length <= 10^4
  • 字符串如果不是 "0" ,就都不含前导零。

解法 1:转成十进制求和

Emmm。比较取巧但确实可行的方法,但是存在几个缺点:

  • 数字可能转不了,例如超过 int 范围;
  • 如果数字比较大,转换效率就比较低。

复杂度分析略。

实现与结果如下:

1
2
3
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        return '{0:b}'.format(int(a, 2) + int(b, 2))
  • 执行用时:40 ms,在所有 Python3 提交中击败了 66.09% 的用户。
  • 内存消耗:13.7 MB,在所有 Python3 提交中击败了 5.31% 的用户。

解法 2:逐位相加

从后往前逐位相加。注意 Python 有个内置函数 zfill 可以直接左补零到指定长度。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        length = max(len(a), len(b))
        a, b = a.zfill(length), b.zfill(length)

        ret = ''

        carry = 0
        for i in range(length - 1, -1, -1):
            sum_ = sum([int(a[i]), int(b[i]), carry])
            ret += f'{sum_ % 2:d}'
            carry = sum_ // 2
        if carry == 1:
            ret += '1'

        return ret[::-1]
  • 执行用时:48 ms,在所有 Python3 提交中击败了 34.57% 的用户。
  • 内存消耗:13.7 MB,在所有 Python3 提交中击败了 5.31% 的用户。