算法题--两个二进制数相加

image.png

0. 链接

题目链接

1. 题目

Given two binary strings, return their sum (also a binary string).

The input strings are both non-empty and contains only characters 1 or 0.

Example 1:

Input: a = "11", b = "1"
Output: "100"

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"

2. 思路1：从右往左逐个相加，考虑位数不等，考虑进位

3. 代码

# coding:utf8


class Solution:
    def addBinary(self, a: str, b: str) -> str:
        results = list()
        extra = 0
        i = len(a) - 1
        j = len(b) - 1
        while i >= 0 or j >= 0:
            int_a = int(a[i]) if i >= 0 else 0
            int_b = int(b[j]) if j >= 0 else 0

            i -= 1
            j -= 1

            result = int_a + int_b + extra
            if result >= 2:
                result -= 2
                extra = 1
            else:
                extra = 0

            results.insert(0, str(result))

        if extra > 0:
            results.insert(0, str(extra))

        return ''.join(results)


solution = Solution()
print(solution.addBinary('11', '1'))
print(solution.addBinary('1010', '1011'))

输出结果

100
10101

4. 结果

image.png