力扣67.二进制求和(模拟法，java || c++语言实现)

题目描述：

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

解题思路:

（1）.我们分析可以得到：按照人的解决思路，我们应该从两个二进制数的低位依次向高位计算，也就是每次将两个二进制数对应的位的数相加，每次逢二进一。
（2）.在(1)的初步逻辑分析基础上，我们应该在物理上解决两个问题：a.如何控制对应位依次相加；b:如何解决存在逢二进一问题。由此我们可以想出如下的操作解决这些问题:

1.我们定义两个指针(假设分别为i,j)分别指向两个字符串的尾部，利用循环（倒序）每次取出最低位的值相加（用于存储当前位的数之和的变量假设为sum；循环退出条件是i >= 0 && j >= 0）
2.我们先定义一个整形变量（假设为carry）用于储存进一位的值，利用逢二进一的特性，将1中求得当前位得数得和除以2，再在下一轮循环开始后将此时的carry赋值给sum
3.若循环后有一个字符串还有剩余，则继续将其剩余的数进行类比于2中的操作
4.我们应注意若最后的carry == 1则表示我们最后要求出的二进制数还需要再进一位

代码：

java代码：

class Solution {//Time Complexity: O(N)//Space Complexity: O(N)public String addBinary(String a, String b) {// a = "1010", b = "1011"// 输出: "10101"int i = a.length() - 1;int j = b.length() - 1;int carry = 0;StringBuilder builder = new StringBuilder();while (i >= 0 && j >= 0) {int sum = carry;sum += a.charAt(i--) - '0';sum += b.charAt(j--) - '0';//取定是否进一位carry = sum / 2;builder.append(sum % 2);}//字符串a还有剩余while (i >= 0) {int sum = carry + a.charAt(i--) - '0';carry = sum / 2;builder.append(sum % 2);}//字符串b还有剩余while (j >= 0) {int sum = carry + b.charAt(j--) - '0';carry = sum / 2;builder.append(sum % 2);}//最高位还要需要进一if (carry == 1) {builder.append('1');}//反转builderreturn builder.reverse().toString();}
}

c++代码：

class Solution {//Time Complexity: O(N)//Space Complexity: O(N)public:string addBinary(string a, string b) {int carry = 0;int i = a.length() - 1;int j = b.length() - 1;string builder;while (i >= 0 && j >= 0) {int sum = carry;sum += a.at(i--) - '0';sum += b.at(j--) - '0';carry = sum / 2;builder += to_string(sum % 2);}//如果a有剩余while (i >= 0) {int sum = carry + a.at(i--) - '0';carry = sum / 2;builder += to_string(sum % 2);}//如果b有剩余while (j >= 0) {int sum = carry + b.at(j--) - '0';carry = sum / 2;builder += to_string(sum % 2);}if (carry == 1) {builder += to_string(1);}reverse(builder.begin(),builder.end());return builder;}
};