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)。