题目描述
给你两个二进制字符串，返回它们的和（用二进制表示）。
输入为 非空 字符串且只包含数字 1 和 0。
示例
示例 1:
输入: a = "11", b = "1" 输出: "100"
示例 2:
输入: a = "1010", b = "1011" 输出: "10101"
提示：
每个字符串仅由字符 '0' 或 '1' 组成。
1 <= a.length, b.length <= 10^4
字符串如果不是 "0" ，就都不含前导零。
题目分析
首先普及一下二进制的概念：和十进制的逢十进一相比，二进制是逢二进一，这就是我们唯一需要知道的基本概念。
我们可以借鉴「列竖式」的方法，末尾对齐，逐位相加。在十进制的计算中「逢十进一」，二进制中我们需要「逢二进一」。
思路讲解
其实这道题是比较烧脑的，写写画画了很久还是没有完全通过。
最终看了力扣的题解，理清了思路如下：
具体的，我们可以取n=max{∣a∣,∣b∣}，循环 n 次，从最低位开始遍历。
注意，为了让各个位置对齐，我们可以先反转这个代表二进制数字的字符串，然后低下标对应低位，高下标对应高位。
当然我们也可以直接把a和b中短的那一个补0，直到和长的那个一样长，然后从高位向低位遍历，对应位置的答案按照顺序存入答案字符串内，最终将答案串反转。
AC代码
func addBinary(a string, b string) string { ans := "" carry := 0 lenA, lenB := len(a), len(b) n := max(lenA, lenB) for i := 0; i < n; i++ { if i < lenA { carry += int(a[lenA-i-1] - '0') } if i < lenB { carry += int(b[lenB-i-1] - '0') } ans = strconv.Itoa(carry%2) + ans carry /= 2 } if carry > 0 { ans = "1" + ans } return ans } func max(x, y int) int { if x > y { return x } return y }
运行结果
总结
复杂度分析
时间复杂度：O(n)
空间复杂度：O(1)
