二进制求和

题目链接: https://leetcode.cn/problems/add-binary

解题思路：

1. 如果a的长度小于b的长度，则交换a和b

2. 从右往左遍历两个字符串，相同位置的字符相加，如果有进位则下一位加1

3. 如果两个字符串长度不一致，则较短的字符串前面补0

4. 如果最后一位有进位，则在最前面补1

func addBinary(a, b string) string {
	// 如果a的长度小于b的长度，则交换a和b
	if len(a) < len(b) {
		a, b = b, a
	}

	// 将a转换为byte类型的切片，用于存储结果
	ans, c, i, j := []byte(a), 0, len(a)-1, len(b)-1

	// 从右往左遍历a和b，相同位置的字符相加，如果有进位则下一位加1
	for i >= 0 {
		if j >= 0 {
			c += int(a[i]-'0') + int(b[j]-'0')
		} else {
			c += int(a[i] - '0')
		}

		// 将相加的结果存储到ans中
		ans[i] = byte(c%2) + '0'
		c /= 2
		i--
		j--
	}

	// 如果最后一位有进位，则在最前面补1
	if c > 0 {
		ans = append([]byte{'1'}, ans...)
	}

	// 将byte类型的切片转换为字符串类型并返回
	return string(ans)
}

复杂度分析

• 时间复杂度： 间复杂度是 $O(n)$，其中 $n$ 是字符串 a 的长度

• 空间复杂度： 空间复杂度是 $O(n)$，因为函数使用了一个 byte 类型的切片 ans 来存储相加的结果。切片的长度等于字符串 a 的长度，因此空间复杂度是 $O(n)$