leecode-67 二进制求和

给你两个二进制字符串，返回它们的和（用二进制表示）。

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

1
2
3
4
5
6
7
8
示例 1:

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

输入: a = "1010", b = "1011"
输出: "10101"
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# author：sarizzm time:2021/1/6 0006

class Solution:
    def addBinary(self, a, b):
        if len(a)<len(b):
            a,b = b, a

        a = [int(i) for i in a]
        b = [int(j) for j in b]

        length_a = -len(a)

        # while(length_b):
        #     if a
        j = -1
        for i in b[::-1]:
            a[j] = a[j] + i
            if a[j] == 2:
                a[j] = 0
                if j > length_a:
                    a[j-1] = a[j-1] +1
                else:
                    a.insert(0, 1)
            if a[j] == 3:
                a[j] = 1
                if j > length_a:
                    a[j-1] = a[j-1] +1
                else:
                    a.insert(0, 1)
            j -= 1
        while(j > length_a):
            if a[j] == 2:
                a[j] = 0
                a[j - 1] = a[j - 1] + 1
                if j-1 == length_a and a[j-1] ==2:
                    a[j-1] = 0
                    a.insert(0,1)
            j -= 1
        if a[0] == 2:
            a[0] = 0
            a.insert(0, 1)


        result = ''
        for i in a:
            result += str(i)

        return result


print(Solution().addBinary('1010','1011')) #10101

print(Solution().addBinary('1010','10')) ## 1100
print(Solution().addBinary('1011','10'))   ## 1100
print(Solution().addBinary('11','1')) # 100
print(Solution().addBinary('11','11'))
print(Solution().addBinary('0','0'))

print(Solution().addBinary('1','111'))

执行用时：44 ms, 在所有 Python3 提交中击败了51.95%的用户

内存消耗：15.1 MB, 在所有 Python3 提交中击败了5.01%的用户

思路和算法

整体思路是将两个字符串较短的用 00 补齐，使得两个字符串长度一致，然后从末尾进行遍历计算，得到最终结果。

本题解中大致思路与上述一致，但由于字符串操作原因，不确定最后的结果是否会多出一位进位，所以会有 2 种处理方式：

第一种，在进行计算时直接拼接字符串，会得到一个反向字符，需要最后再进行翻转
第二种，按照位置给结果字符赋值，最后如果有进位，则在前方进行字符串拼接添加进位

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
class Solution {
    public String addBinary(String a, String b) {
        StringBuffer ans = new StringBuffer();
		
        // 
        
        int n = Math.max(a.length(), b.length()), carry = 0;
        for (int i = 0; i < n; ++i) {
            // i < a.length() , 超过长度以后不再取值，为0
            // a.charAt(a.length() - 1 - i 倒着取值，累加到 carry中
            carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;
            carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;
            ans.append((char) (carry % 2 + '0')); // carry % 2 取余，表示当前位的值
            carry /= 2; //表示进位的值不是0，就是1
        }
		// carry > 0 :表示还可以进位
        if (carry > 0) {
            ans.append('1');
        }
        ans.reverse();

        return ans.toString();
    }
}

//作者：LeetCode-Solution
//链接：https://leetcode-cn.com/problems/add-binary/solution/er-jin-zhi-qiu-he-by-leetcode-solution/

1
2
3
4
5
6
7
8
9
10
11
12
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:] #bin(7) ：0b111

#作者：LeetCode-Solution
#链接：https://leetcode-cn.com/problems/add-binary/solution/er-jin-zhi-qiu-he-by-leetcode-solution/

大佬的图解