作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
题目描述
给定两个二进制字符串，返回它们的和（也是一个二进制字符串）。
输入为非空字符串且只包含数字 1 和 0。
输入格式
- a, b：两个字符串，表示二进制数字。
输出格式
- 返回一个表示和的字符串。
示例
示例 1
输入: a = "11", b = "1" 输出: "100"
示例 2
输入: a = "1010", b = "1011" 输出: "10101"
方法一：模拟二进制加法
解题步骤
- 反向迭代字符串：从两个字符串的最低位（即字符串的最后一个字符）开始，向前迭代。
- 处理进位：维护一个进位变量，根据当前位的加法结果和进位情况更新进位。
- 计算当前位结果：根据位加法和进位计算当前位的结果，并将结果拼接到最终字符串。
- 处理最终进位：迭代结束后，如果还有进位，将其添加到结果字符串的最前面。
完整的规范代码
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"
算法分析
- 时间复杂度：(O(max(n, m)))，其中
n和m分别是两个字符串的长度，因为我们需要迭代每个字符串一次。 - 空间复杂度：(O(max(n, m)))，用于存储结果字符串。
方法二：内置函数转换
解题步骤
- 字符串转换为数字：使用 Python 的
int函数将二进制字符串转换为十进制整数。 - 求和操作：对两个十进制数进行加法操作。
- 数字转回字符串：将结果数转换回二进制字符串。
完整的规范代码
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"
算法分析
- 时间复杂度：(O(n + m))，其中
n和m是两个字符串的长度。转换过程和加法操作的时间复杂度为线性。 - 空间复杂度：(O(1))，除了输入和输出之外，使用的额外空间为常数。
方法三：位操作模拟
解题步骤
- 初始化：设置两个指针分别指向两个字符串的尾部，初始化进位为 0。
- 逐位处理：通过位运算模拟二进制加法，计算每一位的结果和新的进位。
- 生成结果字符串：将每一位的结果存储在数组中，最后将数组反转并转换为字符串。
完整的规范代码
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"
算法分析
- 时间复杂度：(O(max(n, m)))，需要遍历每个字符串的每个字符一次。
- 空间复杂度：(O(max(n, m)))，存储结果需要的空间。
方法四：递归方法
解题步骤
- 递归基：如果一个字符串为空，返回另一个字符串和进位的和。
- 递归计算：从字符串末尾开始，逐位相加，考虑进位，并递归调用自身计算前一位的结果。
- 组合结果：将当前位的结果与前一位的递归结果结合。
完整的规范代码
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"
算法分析
- 时间复杂度：(O(n + m))，在最坏的情况下，递归深度等于较长字符串的长度。
- 空间复杂度：(O(n + m))，递归栈的深度。
方法五：反转字符串后迭代
解题步骤
- 反转字符串：首先将两个字符串反转，以便从最低位开始处理。
- 迭代加法：迭代反转后的字符串，逐位计算结果和进位。
- 处理剩余位和进位：如果一个字符串遍历完毕，处理另一个字符串的剩余位和进位。
- 结果反转：完成迭代后，将结果字符串反转回正确的顺序。
完整的规范代码
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"
算法分析
- 时间复杂度：(O(max(n, m)))，需要遍历两个字符串中较长的那一个。
- 空间复杂度：(O(max(n, m)))，存储结果字符串。
不同算法的优劣势对比
| 特征 | 方法一: 模拟加法 | 方法二: 转换加法 | 方法三: 位操作 | 方法四: 递归 | 方法五: 反转迭代 |
| 时间复杂度 | (O(max(n, m))) | (O(n + m)) | (O(max(n, m))) | (O(n + m)) | (O(max(n, m))) |
| 空间复杂度 | (O(max(n, m))) | (O(1)) | (O(max(n, m))) | (O(n + m)) | (O(max(n, m))) |
| 优势 | 直接明了，处理逻辑清晰 | 计算快速，适合长度较短的字符串 | 位操作符合二进制加法的本质 | 递归逻辑清晰，易于理解 | 反转后迭代符合直觉，易于实现 |
| 劣势 | 较多的迭代和条件判断 | 需要处理较大的整数转换 | 代码复杂度较高，需处理多种边界情况 | 对于大字符串，递归可能导致栈溢出 | 额外的字符串反转操作增加了计算步骤 |
应用示例
通信系统：
在数字通信系统中，二进制数据的处理是基本需求。这些算法可以用于实现错误检测与纠正算法中的简单二进制计算，如奇偶校验位的计算。选择合适的算法可以优化通信协议的实现，提高数据传输的可靠性和效率。
欢迎关注微信公众号 数据分析螺丝钉
