「力扣」第 67 题:二进制求和(简单)

liweiwei1419 ... 2022-1-6 位运算
  • 位运算
About 4 min

# 题目描述

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

输入为 非空 字符串且只包含数字 10

示例 1:

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

示例 2:

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

提示:

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

# 思路分析

思路很简单,就是模拟一个「二进制」的竖式加法。

image.png{:width=400} {:align=center}

我个人觉得这道题单纯是为了考察了我们对于所使用语言的字符串 API 的熟悉程度。写法不唯一,下面以 Java 为例编写参考代码。

在 Java 语言中,如果需要频繁地针对字符串进行操作,应该使用可变的字符序列对象 StringBuilder(这里有一个常见的面试问题:StringBuilderStringBuffer 的区别),并且 StringBuilder 对象也为我们提供了一些好用的操作字符序列的方法(反转,删除、在某一个位置插入一个字符)。

编码中要注意的一点是:如果两个字符的长度不等,需要在短的那个字符串的左边补“0”。

参考代码 1

public class Solution {

    public String addBinary(String a, String b) {
        int aLen = a.length();
        int bLen = b.length();
        int maxLen = Math.max(aLen, bLen);

        // 从个位开始加,个位在字符串的右边
        // 代码访问从左到右,因此先反转一下
        StringBuilder sbA = new StringBuilder(a).reverse();
        StringBuilder sbB = new StringBuilder(b).reverse();

        // 让两个字符补齐成一样的长度
        while (sbA.length() < maxLen) {
            sbA.append("0");
        }
        while (sbB.length() < maxLen) {
            sbB.append("0");
        }

        StringBuilder res = new StringBuilder();
        // 进位,初始时进位为 0
        int carry = 0;
        // 当前字符的 ASCII 值减去 '0' 的 ASCII 值,相当于将这个字符转换成数值
        int num1;
        int num2;
        for (int i = 0; i < maxLen; i++) {
            num1 = sbA.charAt(i) - '0';
            num2 = sbB.charAt(i) - '0';
            if (carry + num1 + num2 > 1) {
                // 因为是二进制,所以多余 2 的部分要减去
                res.append(carry + num1 + num2 - 2);
                // 表示要进位
                carry = 1;
            } else {
                res.append(carry + num1 + num2);
                carry = 0;
            }
        }
        // 对于最高位还要进位的情况,需要单独判断
        if (carry == 1) {
            res.append("1");
        }
        // 最后不要忘记再反转一次
        return res.reverse().toString();
    }

    public static void main(String[] args) {
        String a = "1010";
        String b = "1011";
        Solution solution = new Solution();
        String addBinary = solution.addBinary(a, b);
        System.out.println(addBinary);
    }
}
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

复杂度分析

  • 时间复杂度:O(max(M,N))O(\max(M,N)),这里 MM 是字符串 a 的长度,NN 是字符串 b 的长度。
  • 空间复杂度:O(max(M,N))O(\max(M,N)),保存结果需要 max(M,N)\max(M,N) 长度的可变字符序列对象,如果最高位需要进位,还需要加 11,不过在复杂度计算中忽略这个 11

上面的代码“翻转”了两次,显得有点啰嗦,我们可以使用两个指针,分别从字符串的末尾开始向前遍历,同时在借用 StringBuilder 对象的 insert 方法,从右向左依次得出计算结果,就真的非常接近我们手写“竖式加法”的过程了。下面是参考代码。

参考代码 2

public class Solution {

    public String addBinary(String a, String b) {
        int i = a.length() - 1;
        int j = b.length() - 1;

        // 保存结果的可变的字符序列对象
        StringBuilder res = new StringBuilder();
        // 当前和
        int curSum;
        int carry = 0;
        while (i >= 0 || j >= 0) {
            // 当前和至少是那个进位
            curSum = carry;
            if (i >= 0) {
                curSum += a.charAt(i) - '0';
                i--;
            }
            if (j >= 0) {
                curSum += b.charAt(j) - '0';
                j--;
            }

            // 判断是否需要进位,即确定 carry 的值
            if (curSum > 1) {
                curSum -= 2;
                carry = 1;
            } else {
                carry = 0;
            }

            // 只写结果的值,进位作为下一轮的初始值
            res.insert(0, curSum);
        }

        // 这里不要忘记如果全部加完以后还要进位,要把最高位加上 1
        if (carry == 1) {
            res.insert(0, 1);
        }
        return res.toString();
    }

    public static void main(String[] args) {
        String a = "1010";
        String b = "1011";
        Solution2 solution2 = new Solution2();
        String addBinary = solution2.addBinary(a, b);
        System.out.println(addBinary);
    }
}
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

复杂度分析

  • 时间复杂度:O(max(M,N))O(\max(M,N)),这里 MM 是字符串 a 的长度,NN 是字符串 b 的长度。
  • 空间复杂度:O(max(M,N))O(\max(M,N)),保存结果需要 max(M,N)\max(M,N) 长度的可变字符序列对象,如果最高位需要进位,还需要加 11,不过在复杂度计算中忽略这个 11
Last update: January 14, 2022 00:24
Contributors: liweiwei1419