【LeetCode每天一题】Add Binary(二进制加法)-蒲公英云

【LeetCode每天一题】Add Binary(二进制加法)

你的名字 2021-12-15 14:21 302阅读 0赞

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"
思路

这道题和字符串加法思路是一样的，两个字符串都从尾向前遍历，使用溢出标志量进行记录是否存在溢出。直到遍历完毕。时间复杂度为O(n+m), n,m为a，b字符串的长度，空间复杂度为O(N), N为n，m中最大值加1。
解题思路

1 class Solution(object):
 2     def addBinary(self, a, b):
 3         """
 4         :type a: str
 5         :type b: str
 6         :rtype: str
 7         """
 8         res, flow= '', 0     #  设置结果变量和溢出变量
 9         i, j = len(a) - 1, len(b) - 1     # 两个字符串长度
10         while i >= 0 or j >= 0 or flow:      # 循环变量
11             curval = (i >= 0 and a[i] == '1') + (j >= 0 and b[j] == '1')   # 每一位相加的结果
12             flow, rem = divmod(curval + flow, 2)   # 存储结果
13             res = `rem` + res
14             i -= 1
15             j -= 1
16         return res