leetcode_位运算67.二进制求和

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 0 bit_b = int(b[i]) if i < len(b) else 0 # 计算当前位的和以及进位 sum_bits = bit_a + bit_b + carry result.append(str(sum_bits % 2)) # 当前位的值 carry = sum_bits // 2 # 更新进位 # 如果最后还有进位 if carry: result.append('1') # 反转结果并拼接成字符串 return ''.join(result[::-1]) 过程： 从最低位开始：从字符串的末尾（最低位）开始加起计算每一位的和：每一位的和可以通过计算当前位的数字相加来得到。需要考虑进位处理进位：如果当前位的和大于或等于 2，就需要产生进位。否则不进位继续向前移动：一直处理到两个字符串的最前面，或者其中一个字符串处理完为止。如果有进位，最终的结果需要将进位加到字符串最前端（最左端） 步骤：

假设 a = “1011” 和 b = “1101”，从最后一位开始加

初始化：

设置 carry = 0，表示初始时没有进位结果存放在一个空字符串中（result）

逐位加法：

从字符串末尾开始，一位一位地加

比如 a 和 b 从末尾开始分别是：

a[3] = 1, b[3] = 1，和是 1 + 1 = 2，进位 1，result = 0a[2] = 1, b[2] = 0，和是 1 + 0 + carry(1) = 2，进位1，result = 00a[1] = 0, b[1] = 1，和是 0 + 1 + carry(1) = 2，进位1，result = 000a[0] = 1, b[0] = 1，和是 1 + 1 + carry(1) = 3，进位 1，result = 1000

处理进位：

最后，如果仍有进位 1，需要在最前面加一个 1。上述例子里，由于还有进位，所以最后的结果是11000 时间复杂度：O(max(m, n))，其中 m 和 n 分别是字符串 a 和 b 的长度 反转字符串：O(n)逐位加法：O(max(m, n))拼接字符串：O(n) 空间复杂度：O(max(m, n)) 存储结果：O(max(m, n))其他：O(1)