Add Binary

Posted on | Edited on | In | | Views:

67. Add Binary

这道题是一道简单题, 真的很简单.
首先来看题目

Given two binary strings, return their sum (also a binary string).
The input strings are both non-empty and contains only characters 1 or 0.

意思就是, 给两个二进制的数, 返回他们相加的和.

例子: 

Input a = "11", b = "1"
Output: "100"

思路

既然做加法, 我们就从最右边的一位开始加. 二进制的加法很简单, 每一位只有两种可能, 要么是0, 要么是1. 同样的, 进位也只有这两种可能. 有了这个共识, 思路就出来了.
从最右开始, 两个数相加, 取跟2取模运算的结果作为答案, 如果两数相加的和大于1, 那么进位取1. 然后同时往左挪一位.

Code

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
33
34
35
36
37
38
39
40
def addBianry(a, b):
    res = list()
    a = a[::-1]
    b = b[::-1]
    
    i = j = 0
    carry = 0
    while i < len(a) and j < len(b):
        val = int(a[i]) + int(b[j]) + carry
        carry = 0
        if val > 1:
            carry = 1
            res.apend(str(val%2))
        else:
            res.append(str(val))
        i += 1
        j += 1
    while i < len(a):
        val = int(a[i]) + carry
        carry = 0
        if val > 1:
            carry = 1
            res.append(str(val % 2))
        else:
            res.append(str(val))
        i += 1

    while j < len(b):
        val = int(b[j]) + carry
        carry = 0
        if val > 1:
            carry = 1
            res.append(str(val % 2))
        else:
            res.append(str(val))
        j += 1
    if carry != 0:
        res.append("1")
    
    return "".join(res)[::-1]

需要注意的地方是, 在返回结果之前, 需要看一下进位是否等于0. 如果不等于0, 需要最前面加一个1.
这道题的时间复杂度是 $O(n)$

EOF