Description
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"
描述
给定两个二进制字符串，返回它们的总和（也是二进制字符串）。
输入字符串都是非空的，只包含字符1或0。
思路
- 这道题要求两个二进制数相加
- 我们按照二进制相加的规则：满二进一即可。思路很清晰，注意a数组和b数组长度可能不同，对于较长数组的剩余部分需要额外处理.
class Solution: def addBinary(self, a, b): """ :type a: str :type b: str :rtype: str """ # 获取字符串a和字符串b的长度 len_a, len_b = len(a), len(b) # 结果数组 res = [] # 字典，用于记录哪一个字符更长 longest = {} # 如果字符串a更长 if len_a < len_b: num_min = len_a longest.setdefault('a', b) left = len_b-len_a # 如果字符串b更长 else: num_min = len_b longest.setdefault('a', a) left = len_a-len_b temp = 0 # 进行加和运算，注意二进制的进位，遍历a数组和b数组相互重叠的部分 for index in range(1, num_min+1): # 从右往左开始做加法运算 temp = temp+int(a[-index])+int(b[-index]) # 如果大于2则表示需要进位 if temp >= 2: # 进位，当前位置值设置为temp-2 res.insert(0, temp-2) # 重置temp = 1 temp = 1 else: # 在结果数组的首位插入，然后将temp重置为0 res.insert(0, temp) temp = 0 # 对剩下的部分进行加和 for index in range(left-1, -1, -1): temp = temp+int(longest.get('a')[index]) if temp >= 2: res.insert(0, temp-2) temp = 1 else: res.insert(0, temp) temp = 0 if temp: res.insert(0, temp) # 以字符的形式返回 return ''.join(str(x) for x in res)
源代码文件在这里.
