Leetcode 剑指 Offer II 002. 二进制加法

题目难度: 简单

原题链接

今天继续更新 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” ，就都不含前导零。

题目思考

1. 字符串长度可能很长, 如何处理?
2. 两个字符串长度可能不同, 如何处理?

解决方案

思路

• 分析题目, 字符串长度最大可达 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家关注~😊