122.二进制求和
题目
给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
示例 1：
输入:a = "11", b = "1"
输出："100"
示例 2：
输入：a = "1010", b = "1011"
输出："10101"
思路
步骤： - 从两个字符串的末尾开始往前遍历。 - 每次取当前位（如果某个字符串已经遍历完，则当前位视为 0），加上进位 carry。 - 当前位的和 sum = bit_a + bit_b + carry。 - 结果的当前位 = sum % 2（因为二进制只有 0 和 1）。 - 新的进位 carry = sum / 2（因为逢二进一）。 - 重复直到两个字符串都遍历完，并且进位为 0。 - 最后将结果反转（因为我们是从低位往高位计算的）。
边界情况：
- 如果两个字符串长度不同，短的在高位补 0。
- 最后如果还有进位，要在结果前面加一个 '1'。
class Solution {
fun addBinary(a: String, b: String): String {
val sb = StringBuilder()
var i = a.length - 1
var j = b.length - 1
var carry = 0
while (i >= 0 || j >= 0 || carry > 0) {
val bitA = if (i >= 0) a[i] - '0' else 0
val bitB = if (j >= 0) b[j] - '0' else 0
val sum = bitA + bitB + carry
sb.append(sum % 2)
carry = sum / 2
i--
j--
}
return sb.reverse().toString()
}
}
二进制求和就是：从右往左逐位相加，逢二进一，最后把结果反转过来。
复杂度
- 时间复杂度: O(max(m, n))，其中 m 和 n 分别是两个字符串的长度。只需遍历较长的那一个。
- 空间复杂度: O(max(m, n))，用于存储结果字符串（StringBuilder 内部数组）。
- 邮箱 ：charon.chui@gmail.com
- Good Luck!