当前位置：首页 > news >正文

峨眉山网站建设沈阳seo优化新势力

news 2025/7/3 21:13:21

峨眉山网站建设,沈阳seo优化新势力,做网站需要学jsp,sdk直播67.二进制求和给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。 1. 内置函数 class Solution(object):def addBinary(self, a, b):""":type a: str:type b: str:rtype: str"""res int(a, 2) int(b, 2)return …

67.二进制求和

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

1. 内置函数

class Solution(object):def addBinary(self, a, b):""":type a: str:type b: str:rtype: str"""res = int(a, 2) + int(b, 2)return bin(res)[2:]

时间复杂度分析：

int(a, 2) 和 int(b, 2)：
- 这两步将二进制字符串转换为整数。将长度为 n 的字符串（假设 a 或 b 的最大长度为 n）转换为整数的时间复杂度是 O(n)，因为需要遍历字符串的每一位
res = int(a, 2) + int(b, 2)：
- 加法操作本身的时间复杂度是 O(1)，但由于涉及到的数字可能很大（例如，如果 a 和 b 都非常长，转换后的整数也会很大），加法的复杂度可能会受到整数位数的影响，因此加法的复杂度实际上是 O(n)，其中 n 是较长字符串的长度
bin(res)：
- bin(res) 将整数转换为二进制字符串。转换一个整数到二进制字符串的时间复杂度为 O(n)，其中 n 是整数的位数。整数的位数大约与输入字符串的长度相等，因此这一步的复杂度是 O(n)
[2:]：
- 这一步是对字符串进行切片，去掉前缀 “0b”。切片操作的时间复杂度是 O(n)
综合时间复杂度：
- 由于上述步骤中最耗时的操作是整数转换和加法操作，它们的时间复杂度都是 O(n)。因此，这段代码的总时间复杂度是 O(n)，其中 n 是输入字符串的长度

空间复杂度分析：

整数转换：int(a, 2) 和 int(b, 2) 会分别创建两个整数，这两个整数占用 O(n) 的空间，因为它们的位数大约和字符串的长度相等
结果存储：bin(res) 会生成一个新的二进制字符串，其长度最多是 n + 1，因此空间复杂度是 O(n)
其他变量：变量 res 和 a, b 是常数大小，空间消耗是 O(1)
综合空间复杂度：
- 空间复杂度主要由整数和二进制字符串的存储占据，因此总空间复杂度是 O(n)

总结：

时间复杂度：O(n)，其中 n 是输入字符串的长度
空间复杂度：O(n)

2. 非内置函数

class Solution(object):def addBinary(self, a, b):""":type a: str:type b: str:rtype: str"""# 初始化carry = 0  # 存储进位的值result = []  # 存储结果# 让a和b长度一致a = a[::-1]  # 反转字符串，方便从最低位开始加b = b[::-1]# 对两者逐位相加for i in range(max(len(a), len(b))):# 获取当前位的值bit_a = int(a[i]) if i < len(a) else 0bit_b = int(b[i]) if i < len(b) else 0# 计算当前位的和以及进位sum_bits = bit_a + bit_b + carryresult.append(str(sum_bits % 2))  # 当前位的值carry = sum_bits // 2  # 更新进位# 如果最后还有进位if carry:result.append('1')# 反转结果并拼接成字符串return ''.join(result[::-1])

过程：
1. 从最低位开始：从字符串的末尾（最低位）开始加起
2. 计算每一位的和：每一位的和可以通过计算当前位的数字相加来得到。需要考虑进位
3. 处理进位：如果当前位的和大于或等于 2，就需要产生进位。否则不进位
4. 继续向前移动：一直处理到两个字符串的最前面，或者其中一个字符串处理完为止。如果有进位，最终的结果需要将进位加到字符串最前端（最左端）
步骤：
1. 假设 a = “1011” 和 b = “1101”，从最后一位开始加
2. 初始化：
  - 设置 carry = 0，表示初始时没有进位
  - 结果存放在一个空字符串中（result）
3. 逐位加法：
  - 从字符串末尾开始，一位一位地加
  - 比如 a 和 b 从末尾开始分别是：
    - a[3] = 1, b[3] = 1，和是 1 + 1 = 2，进位 1，result = 0
    - a[2] = 1, b[2] = 0，和是 1 + 0 + carry(1) = 2，进位1，result = 00
    - a[1] = 0, b[1] = 1，和是 0 + 1 + carry(1) = 2，进位1，result = 000
    - a[0] = 1, b[0] = 1，和是 1 + 1 + carry(1) = 3，进位 1，result = 1000
4. 处理进位：
  - 最后，如果仍有进位 1，需要在最前面加一个 1。上述例子里，由于还有进位，所以最后的结果是11000