专业做淘宝网站推广,门户网站建设投入,外贸网站建设智能建站,百度青岛代理公司前言#xff1a;剑指offer刷题系列
问题#xff1a;
给你两个二进制字符串 a 和 b #xff0c;以二进制字符串的形式返回它们的和。
示例#xff1a;
输入#xff1a;a 1010, b 1011
输出#xff1a;10101思路1#xff1a;
…前言剑指offer刷题系列
问题
给你两个二进制字符串 a 和 b 以二进制字符串的形式返回它们的和。
示例
输入a 1010, b 1011
输出10101思路1
我们为了避免去判断谁大谁小的边界问题直接把最短的字符串前面先补0。设置一个保存进位的数从低到高遍历逢二进一。
先通过两个 while 循环将输入的二进制字符串 a 和 b 的长度补齐使它们的长度相等。如果其中一个字符串较短就在它的前面添加0以保证两个二进制数的位数相同。
然后定义了一个变量 tmp 用来存储进位信息初始化为0。同时将字符串 a 和 b 一起转换为列表以便进行逐位相加操作。
接下来通过一个 for 循环从字符串的最后一位开始逐位相加从低位到高位。具体的相加规则如下
如果当前位的数字是0123中的0那么将进位 tmp 和当前位相加并根据相加结果更新当前位。如果相加结果是3表示当前位和进位都是1那么当前位变为0进位为1。如果相加结果是2表示当前位和进位中有一个是1那么当前位变为0进位为1。如果相加结果是1表示当前位和进位中只有一个是1那么当前位变为1进位为0。
最后在循环结束后检查是否还有进位 tmp。如果有进位就在结果字符串的最前面添加一个 “1”。最终返回结果字符串。
时间复杂度O(n)
空间复杂度O(n)
基于上述思考代码如下
class Solution:def addBinary(self, a: str, b: str) - str:while len(a) len(b):b 0 bwhile len(a) len(b):a 0 atmp 0a, b list(a), list(b)for i in range(len(a) - 1, -1, -1):cur int(a[i]) int(b[i]) tmpif cur 3:b[i] 1tmp 1elif cur 2:b[i] 0tmp 1elif cur 1:b[i] 1tmp 0else:b[i] 0tmp 0if tmp 1:b [1] breturn .join(b)执行结果如下图 思路2
首先将输入的二进制字符串 a 和 b 使用 int(a, 2) 和 int(b, 2) 转换为整数基数为2表示将二进制字符串转换为整数。然后这两个整数相加得到它们的和。
接下来将上一步得到的和转换为二进制字符串形式并通过切片操作去掉字符串的前缀0b以获取纯二进制数表示。
最终该方法返回两个二进制数相加后的结果作为二进制字符串。
基于上述思考代码如下
class Solution(object):def addBinary(self, a, b):return bin(int(a,2)int(b,2))[2:]执行结果如下图
