基本信息

  • 题号：67
  • 题厂：亚麻
  • 难度系数：低



已知两个二进制字符串，返回这两个字符串相加后结果

例如 a = "11", b = "1"
返回 "100"


解题思路

  • 因为 a b 字符串长度不等，所以要从末尾往前相加
  • 遇上加减问题，一般需要一个 carry 协助进位计算
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        i, j = len(a) - 1, len(b) - 1
        carry = 0
        res = ""

        while i >= 0 or j >= 0:
            cur = ""
            # 考虑数组越界问题，当 index 小于 0 时，当前字符为 0
            cur_a = a[i] if i >= 0 else "0"
            cur_b = b[j] if j >= 0 else "0"

            # 计算的时候，分 3 种情况考虑
            # 同时为 1 的情况下考虑进位不进位
            # 同时为 0 的情况下考虑进位不进位
            # 一个 1 一个 0 时的进位不进位情况
            if cur_a == "1" and cur_b == "1":
                if carry == 1:
                    cur = "1"
                else:
                    cur = "0"
                carry = 1
            elif cur_a == "0" and cur_b == "0":
                if carry == 1:
                    cur = "1"
                else:
                    cur = "0"
                carry = 0
            else:
                if carry == 1:
                    cur = "0"
                    carry = 1
                else:
                    cur = "1"
                    carry = 0

            res = cur + res
            i -= 1
            j -= 1

        # 跳出循环后，如果 carry 为 1，还需要再额外加一次。。。
        if carry:
            res = "1" + res

        return res


Constraints

  • 1 <= a.length, b.length <= 104
  • a and b consist only of '0' or '1' characters.
  • Each string does not contain leading zeros except for the zero itself.



测试

  • a b 同时为 0 的特殊情况
  • a b 长度不等时
  • a b 有进位的需求情况
  • ……



Big O

  • 时间复杂度：O（n）， n = max（len（a），len（b））
  • 空间复杂度：O（1）


总结

  • 复习了二进制加法。。。。。。有别于常规的二进制加减。。。。。。