67.二进制求和

题目描述

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

示例 1:
输入: a = “11”, b = “1”
输出: “100”

思路

先将 a 和 b 转化成十进制数，求和后再转化为二进制数

列竖式
末尾对齐，逐位相加，逢二进一
具体的，我们可以取 n=max{∣a∣,∣b∣}，循环 n 次，从最低位开始遍历。我们使用一个变量 carry 表示上一个位置的进位，初始值为 0。记当前位置对其的两个位为 ai 和 bi，则每一位的答案为 (carry+ai+bi) mod 2，下一位的进位为 ⌊(carry+ai+bi)/2⌋。重复上述步骤，直到数字 a 和 b 的每一位计算完毕。最后如果 carry 的最高位不为 0，则将最高位添加到计算结果的末尾。
注意，为了让各个位置对齐，你可以先反转这个代表二进制数字的字符串，然后低下标对应低位，高下标对应高位。当然你也可以直接把 a 和 b 中短的那一个补 0 直到和长的那个一样长，然后从高位向低位遍历，对应位置的答案按照顺序存入答案字符串内，最终将答案串反转。

代码

class Solution:

 def addBinary(self, a: str, b: str) -> str:
     """
     先将 aaa 和 bbb 转化成十进制数，求和后再转化为二进制数
     :param a:
     :param b:
     :return:
     """
     # a = int(a, 2)  # 将二进制数转为十进制
     # b = int(b, 2)
     # print(a)
     # print(b)
     # return bin(a+b)[2:]

     return '{0:b}'.format(int(a, 2) + int(b, 2))

 def addBinary1(self, a: str, b: str) -> str:
     ans = list()
     n = max(len(a), len(b))
     carry = 0

     list_a = []
     list_b = []
     for e in a:
         list_a.append(int(e))

     for e in b:
         list_b.append(int(e))

     print(list_a)
     print(list_b)

     for i in range(n):
         carry += list_a[len(a) - i - 1] if i < len(a) else 0
         carry += list_b[len(b) - i - 1] if i < len(b) else 0
         ans.append(str(int(carry % 2)))
         carry /= 2

     if carry > 0:
         ans.append('1')

     return ''.join(ans[::-1])

if name == ‘main‘:

 s = Solution()
 a = "11"
 b = "1"
 res = s.addBinary1(a, b)
 print(res)

victory的博客

leetcode | 67.二进制求和

67.二进制求和

题目描述

思路

代码