1 模拟——67. 二进制求和

本文主要是介绍1 模拟——67. 二进制求和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1 模拟

67. 二进制求和

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

示例 1：
输入:a = "11", b = "1"
输出："100"
示例 2：
输入：a = "1010", b = "1011"
输出："10101"

算法设计

可以从低位到高位（从后向前）计算，用一个变量carry记录进位，如果有字符没处理完或者有进位，则循环处理。两个字符串对应的位A、B相加，并加上进位，和值为sum = A + B + carry，进位carry = sum / 2，余数sum % 2作为结果。
例如，a = “1010”, b = “110”。
（1）初始时，进位carry=0，从低位开始计算，A=0，B=0，和值sum=A+B+carry=0。进位carry= sum / 2 = 0，余数作为结果sum % 2 = 0。

（2）从低位到高位继续处理，进位carry=0，A=1，B=1，和值sum=A+B+carry=2。进位carry= sum / 2 = 1，余数作为结果sum % 2 = 0。

（3）从低位到高位继续处理，进位carry=1，A=0，B=1，和值sum=A+B+carry=2。进位carry= sum / 2 = 1，余数作为结果sum % 2 = 0。

（4）从低位到高位继续处理，进位carry=1，A=0，此时第二个字符串已经处理完毕，按照0计算，B=0，和值sum=A+B+carry=2。进位carry = sum / 2 = 1，余数作为结果sum % 2 = 0。

（5）此时第两个字符串均已处理完毕，但是进位不为0，A=0，B=0，和值sum=A+B+carry=1。进位carry = sum / 2 = 0，余数作为结果sum % 2 = 1。

在算法实现中，可以将每次的计算结果转字符串，加上已计算结果，res = to_string(sum % 2) + res，最后返回字符串res。

算法实现

//LeetCode67 二进制求和 
string addBinary(string a, string b) {string res; // 返回结果 int carry = 0; // 进位 int i = a.size() - 1; // 从低位开始 int j = b.size() - 1;while (i >= 0 || j >= 0 || carry != 0) { // 有未处理完字符或者有进位 int A = i >= 0 ? a[i--] - '0' : 0;int B = j >= 0 ? b[j--] - '0' : 0;int sum = A + B + carry; // 和值 carry = sum / 2; // 商为进位 res = to_string(sum % 2) + res; // 余数转字符串，加上已计算结果 }return res;
}

算法分析

时间复杂度为O(max(n,m))，n、m分别为两个二进制字符串的长度，空间复杂度为 O(1)。

这篇关于1 模拟——67. 二进制求和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---