题目难度: 简单
今天继续更新 Leetcode 的剑指 Offer（专项突击版）系列, 大家在公众号 算法精选 里回复
剑指offer2就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。
输入为 非空 字符串且只包含数字 1 和 0。
示例 1:
- 输入: a = "11", b = "10"
- 输出: "101"
示例 2:
- 输入: a = "1010", b = "1011"
- 输出: "10101"
提示：
- 每个字符串仅由字符 '0' 或 '1' 组成。
- 1 <= a.length, b.length <= 10^4
- 字符串如果不是 "0" ，就都不含前导零。
题目思考
- 字符串长度可能很长, 如何处理?
- 两个字符串长度可能不同, 如何处理?
解决方案
思路
- 分析题目, 字符串长度最大可达 10^4, 转成二进制数字直接相加不现实
- 直接对字符串进行计算的话, 就需要用到小学加法的知识了 😂
- 简单来说, 就是将两个字符串从个位开始逐位相加, 同时维护进位信息
- 如果两者的当前位加进位的和大于 1, 则将其对 2 取模作为和的当前位, 同时进位设为 1
- 否则将它自身设为和的当前位, 同时进位设为 0
- 具体实现时, 需要逆序遍历两字符串, 模拟从个位开始的情况
- 同时由于两个字符串长度可能不等, 如果某个字符串提前遍历完了, 则更高位用 0 代替
- 另外特别注意, 如果最后两个字符串都遍历完了但仍有进位, 则需要将该进位也加到最终结果里
- 下面代码中对上面提到的每个步骤都有详细注释, 方便大家理解
复杂度
- 时间复杂度 O(A+B): A 和 B 分别是字符串 a 和 b 的长度, 只需要循环 A+B(+1) 次 (有额外进位时+1)
- 空间复杂度 O(1): 只使用了几个常数空间的变量
代码
class Solution:
def addBinary(self, a: str, b: str) -> str:
# 初始化双指针指向两个字符串的最后一位
i, j = len(a) - 1, len(b) - 1
# 初始化进位为0
carry = 0
res = ""
while i >= 0 or j >= 0 or carry > 0:
# 只要任意操作数存在当前位或进位仍有值, 就继续求和
# 如果某个操作数不存在当前位了, 则用0代替
x = int(a[i]) if i >= 0 else 0
y = int(b[j]) if j >= 0 else 0
# 将两个位的值和进位相加
sm = x + y + carry
# 新的进位只有当sm>=2时才是1, 且最多是1, 所以是sm/2
carry = sm // 2
# 和的当前位则是sm对2取模后的结果
bit = sm % 2
# 注意这里的结果是加在当前字符串开头, 因为是逆序遍历
res = str(bit) + res
# 继续求前一位的和
i -= 1
j -= 1
return res
大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号