让我们一起啃算法----二进制求和
62 / 2 / 创建于 3年前 /
三斤和他的喵 的个人博客
二进制求和（Add-Binary）
题干：
给你两个二进制字符串，返回它们的和（用二进制表示）。
输入为 非空 字符串且只包含数字 1 和 0。
示例 1:
输入: a = “11”, b = “1”
输出: “100”
示例 2:
输入: a = “1010”, b = “1011”
输出: “10101”
提示：
每个字符串仅由字符 ‘0’ 或 ‘1’ 组成。
1 <= a.length, b.length <= 10^4
字符串如果不是 “0” ，就都不含前导零。
来源：力扣
解题思路与 让我们一起啃算法—-两数相加 相似，只不过这里将链表换成了字符串，并且 进位条件由大于等于 10 产生进位变成了 大于等于 2 产生进位。
解题思路
首先要明确，一个 数字字符 与 字符0 相减，得到的值就是这个数字字符的数值，即 ‘9’ - ‘0’ 等于 9。
初始化 i 指向字符串 a 的最后一个字符，j 指向字符串 b 的最后一个字符，res 为空字符串，接着计算得到 数值 a[i] 与 数值 b[j] 的和，记为 sum。
如果 sum 等于 2，则产生进位 carry，且进位值为 1，如果 sum 小于 2，则不产生进位，carry 设置为 0。并将 sum % 2 的值转成字符串记为 v，与 res 进行拼接，由于我们是从右往左遍历的，每次计算得到的 v 应该与 res 左拼接，即 res = v + res。
接着 i 向左移动一位，b 向左移动一位，继续计算数值 a[i] 与 数值 b[j] 的和，记得求和时带上上次的进位值，重复上面的操作。
大致思路如上，详细流程，可以查看下面的流程图：
代码实现
GO语言实现
func addBinary(a string, b string) string {
var res string
var carry uint8
i := len(a) - 1
j := len(b) - 1
// i 或者 j 有一个越界了就跳出循环，即表示 字符串a 与字符串b 长度不一致
for i >= 0 && j >= 0 {
// 计算 sum ，strconv.Itoa 将数值转成对应的字符串
res = strconv.Itoa(int((a[i] - '0' + (b[j] - '0') + carry) % 2)) + res
// 计算进位
carry = ((a[i] - '0') + (b[j] - '0') + carry) / 2
i --
j --
}
// j越界
for i >= 0 {
// 字符串a 剩余的字符与进位求和
res = strconv.Itoa(int((a[i] - '0' + carry) % 2)) + res
carry = ((a[i] - '0') + carry) / 2
i --
}
// i 越界
for j >= 0 {
// 字符串b 剩余的字符与进位求和
res = strconv.Itoa(int((b[j] - '0' + carry) % 2)) + res
carry = ((b[j] - '0') + carry) / 2
j --
}
// i 和 j 都越界了，判断 carry进位是否大于0，如果大于0，这需要将这个最高位补上
if carry > 0 {
res = "1" + res
}
return res
}总结
每天进步一点点，加油！
算法教程项目，每天更新一题，点个 star 支持一下呀：
https://github.com/wx-satellite/learning-a…
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号
推荐文章：