LeetCode题目67:二进制求和

题目描述

给定两个二进制字符串，返回它们的和（也是一个二进制字符串）。

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

输入格式

• a, b：两个字符串，表示二进制数字。

输出格式

• 返回一个表示和的字符串。

示例

示例 1

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

示例 2

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

---

方法一：模拟二进制加法

解题步骤

1. 反向迭代字符串：从两个字符串的最低位（即字符串的最后一个字符）开始，向前迭代。
2. 处理进位：维护一个进位变量，根据当前位的加法结果和进位情况更新进位。
3. 计算当前位结果：根据位加法和进位计算当前位的结果，并将结果拼接到最终字符串。
4. 处理最终进位：迭代结束后，如果还有进位，将其添加到结果字符串的最前面。

完整的规范代码

def addBinary(a, b):
    """
    使用模拟二进制加法的方法计算二进制字符串的和
    :param a: str, 第一个二进制字符串
    :param b: str, 第二个二进制字符串
    :return: str, 二进制求和结果
    """
    i, j, carry, result = len(a) - 1, len(b) - 1, 0, []
    while i >= 0 or j >= 0 or carry:
        total = carry
        if i >= 0:
            total += int(a[i])
            i -= 1
        if j >= 0:
            total += int(b[j])
            j -= 1
        carry = total // 2
        result.append(str(total % 2))
    return ''.join(result[::-1])

# 示例调用
print(addBinary("11", "1"))  # 输出: "100"
print(addBinary("1010", "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

算法分析

• 时间复杂度：(O(max(n, m)))，其中 n 和 m 分别是两个字符串的长度，因为我们需要迭代每个字符串一次。
• 空间复杂度：(O(max(n, m)))，用于存储结果字符串。

方法二：内置函数转换

解题步骤

1. 字符串转换为数字：使用 Python 的 int 函数将二进制字符串转换为十进制整数。
2. 求和操作：对两个十进制数进行加法操作。
3. 数字转回字符串：将结果数转换回二进制字符串。

完整的规范代码

def addBinary(a, b):
    """
    使用内置函数转换方法计算二进制字符串的和
    :param a: str, 第一个二进制字符串
    :param b: str, 第二个二进制字符串
    :return: str, 二进制求和结果
    """
    return bin(int(a, 2) + int(b, 2))[2:]

# 示例调用
print(addBinary("11", "1"))  # 输出: "100"
print(addBinary("1010", "1011"))  # 输出: "10101"
1
2
3
4
5
6
7
8
9
10
11
12

算法分析

• 时间复杂度：(O(n + m))，其中 n 和 m 是两个字符串的长度。转换过程和加法操作的时间复杂度为线性。
• 空间复杂度：(O(1))，除了输入和输出之外，使用的额外空间为常数。

方法三：位操作模拟

解题步骤

1. 初始化：设置两个指针分别指向两个字符串的尾部，初始化进位为 0。
2. 逐位处理：通过位运算模拟二进制加法，计算每一位的结果和新的进位。
3. 生成结果字符串：将每一位的结果存储在数组中，最后将数组反转并转换为字符串。

完整的规范代码

def addBinary(a, b):
    """
    使用位操作模拟二进制加法
    :param a: str, 第一个二进制字符串
    :param b: str, 第二个二进制字符串
    :return: str, 二进制求和结果
    """
    result, carry = [], 0
    i, j = len(a) - 1, len(b) - 1
    while i >= 0 or j >= 0 or carry:
        if i >= 0:
            carry += int(a[i])
            i -= 1
        if j >= 0:
            carry += int(b[j])
            j -= 1
        result.append(str(carry % 2))
        carry //= 2
    return ''.join(result[::-1])

# 示例调用
print(addBinary("11", "1"))  # 输出: "100"
print(addBinary("1010", "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

算法分析

• 时间复杂度：(O(max(n, m)))，需要遍历每个字符串的每个字符一次。
• 空间复杂度：(O(max(n, m)))，存储结果需要的空间。

方法四：递归方法

解题步骤

1. 递归基：如果一个字符串为空，返回另一个字符串和进位的和。
2. 递归计算：从字符串末尾开始，逐位相加，考虑进位，并递归调用自身计算前一位的结果。
3. 组合结果：将当前位的结果与前一位的递归结果结合。

完整的规范代码

def addBinary(a, b):
    """
    使用递归方法计算二进制字符串的和
    :param a: str, 第一个二进制字符串
    :param b: str, 第二个二进制字符串
    :return: str, 二进制求和结果
    """
    if not a:
        return b
    if not b:
        return a
    
    if a[-1] == '1' and b[-1] == '1':
        return addBinary(addBinary(a[:-1], b[:-1]), '1') + '0'
    if a[-1] == '0' and b[-1] == '0':
        return addBinary(a[:-1], b[:-1]) + '0'
    else:
        return addBinary(a[:-1], b[:-1]) + '1'

# 示例调用
print(addBinary("11", "1"))  # 输出: "100"
print(addBinary("1010", "1011"))  # 输出: "10101"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

算法分析

• 时间复杂度：(O(n + m))，在最坏的情况下，递归深度等于较长字符串的长度。
• 空间复杂度：(O(n + m))，递归栈的深度。

方法五：反转字符串后迭代

解题步骤

1. 反转字符串：首先将两个字符串反转，以便从最低位开始处理。
2. 迭代加法：迭代反转后的字符串，逐位计算结果和进位。
3. 处理剩余位和进位：如果一个字符串遍历完毕，处理另一个字符串的剩余位和进位。
4. 结果反转：完成迭代后，将结果字符串反转回正确的顺序。

完整的规范代码

def addBinary(a, b):
    """
    反转字符串后进行迭代计算二进制字符串的和
    :param a: str, 第一个二进制字符串
    :param b: str, 第二个二进制字符串
    :return: str, 二进制求和结果
    """
    a, b = a[::-1], b[::-1]
    result = []
    carry = 0
    i = 0
    while i < len(a) or i < len(b) or carry:
        total = carry
        if i < len(a):
            total += int(a[i])
        if i < len(b):
            total += int(b[i])
        result.append(str(total % 2))
        carry = total // 2
        i += 1
    return ''.join(result[::-1])

# 示例调用
print(addBinary("11", "1"))  # 输出: "100"
print(addBinary("1010", "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

算法分析

• 时间复杂度：(O(max(n, m)))，需要遍历两个字符串中较长的那一个。
• 空间复杂度：(O(max(n, m)))，存储结果字符串。

不同算法的优劣势对比

应用示例

通信系统：
在数字通信系统中，二进制数据的处理是基本需求。这些算法可以用于实现错误检测与纠正算法中的简单二进制计算，如奇偶校验位的计算。选择合适的算法可以优化通信协议的实现，提高数据传输的可靠性和效率。