题目

给定两个二进制字符串，返回他们的和（用二进制表示）。
输入为非空字符串且只包含数字 1 和 0。

示例 1:

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

示例 2:

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

解答

方案一

利用语言特性，先将字符串转化为数值，再利用语言的数值运算。

def addBinary(a: str, b: str) -> str:
    '''方案一:
    先转化为int, 然后在执行数值操作, 最后转化回 string
    '''
    sum = int(f'0b{a}', 2) + int(f'0b{b}', 2)
    return bin(sum)[2:]

方案二

  1. 将输入的两个字符串转化为字符数组（语言支持直接遍历的话可以不转）；
  2. 倒序遍历最长的字符数组（注意先判断短的是否越界）；
  3. 利用加法的规则，进行相加；
  4. 返回最终结果。
def addBinary(a: str, b: str) -> str:
    max_len = len(a) if len(a) > len(b) else len(b)
    carry = 0  # 进位的数值
    ret = []
    for i in range(max_len):
        a_index = len(a) - i - 1
        b_index = len(b) - i - 1
        if a_index >= 0 and b_index >= 0:  # 都没有越界
            num = int(a[a_index]) + int(b[b_index]) + carry
        if a_index < 0:  # a 越界
            num = int(b[b_index]) + carry
        if b_index < 0:  # b 越界
            num = int(a[a_index]) + carry

        # 加法法则
        if num < 2:
            ret.append(str(num))
            carry = 0
        else:
            ret.append(str(num - 2))
            carry = 1

    if carry == 1:  # 最后是否进位了
        ret.append('1')
    ret.reverse()
    return ''.join(ret)