题目描述
我们解析一下题目
- 我们可以理解到两个主要信息
- 给的是二进制的字符串
- 返回他们的和
我们知道，十进制的加减法需要进位，例如：9+7=16是因为9+1之后进了一位，二进制也是如此，只不过十进制是逢10进1，二进制是逢2进1.
但是我们这里还需要注意两点
- 题目给的是字符串
- 返回的和也是字符串
算法原理[[leetCode]]
先说结论
- 核心打法：
- 字符串转数字
结果数字再转字符
- 字符串转数字
因为按照我们的习惯，加法喜欢从后面往前开始依次加
所以我们这里定义一个循环
{
- 把每个字符串的最后一个字符转成数字
- 用sum变量记录他们的和
- push他们的和%2+'0’到一个新的字符串里面
- 用carry记录他们的进位
}
这里的carry的值可能会出现三种情况
- 和有3中情况
- 0：%2还是0，直接写入
- 1：%2还是1，小于2，直接写入
- 2:%2是0，但是要进位，写入0之后，用carry值记录他们的进位1 - 然后在循环中carry的值给到sum，一直带着进位，直到遇到能写入的位置
- 因为我们是从后往前依次加，但是结果是要从前往后读取的，所以我们要把结果反转一下
代码
class Solution {public:string addBinary(string a, string b) {int i=a.size()-1;int j=b.size()-1;int carry=0;string result;while(i>=0||j>=0||carry>0){int sum=carry;if(i>=0){sum+=a[i]-'0';i--;}if(j>=0){sum+=b[j]-'0';j--;}result.push_back((sum%2)+'0');carry=sum/2;}reverse(result.begin(),result.end());return result;}};
时间复杂度：
