题目

给你两个二进制字符串，返回它们的和(用二进制表示)。
输入非空字符串且只包含数组1和0。

示例1：

输入: a = "11", b = "1"
输出: "100"
1
2

示例2：

输入: a = "1010", b = "1011"
输出: "10101"
1
2

提示

每个字符串仅由字符 ‘0’ 或 ‘1’ 组成。
1 <= a.length, b.length <= 10^4
字符串如果不是 “0” ，就都不含前导零。

思路1

这个方法中规中矩，直接看吧，但是有一个问题，我没弄明白，我写在最后。

class Solution {
public:
    string addBinary(string a, string b) {
        int carry = 0; //补位数
        int cur = 0; //求和后的数  = a[i] + b[i] + carry
        int size_a = a.size();
        int size_b = b.size();
        string result;
        if(size_a < size_b){ //保证字符串b是短的
            swap(a, b);
            swap(size_a, size_b);
            // cout << a << " " << b << endl;
            // cout << size_a << " " << size_b << endl;
        }
        //保证b是短的原因是为了，将短的进行补位
        int add = size_a - size_b;
        b.insert(0, add, '0');
        // cout << b;
        //现在两个就对齐了，开始相加。
        for(int i = size_a - 1; i >= 0; i--){
            // cout << a[i] << " " ;
            int ia = a[i] - '0';
            int ib = b[i] - '0';
            // cout << b[i];
            // cout << ib << " ";
            //现在开始我们是从字符串的最后一个开始计算
            // cur = a[i] ^ b[i] ^ carry;  //三数相与和相加的效果一样
            // if(a[i] + b[i] + carry >= 2){
            cur = ia ^ ib ^ carry;  //三数相与和相加的效果一样
            if(ia + ib + carry >= 2){
                carry = 1;
            }else{
                carry = 0;
            }
            result.insert(0, 1, cur + '0');
        }
        //最高位
        if(carry){
            result.insert(0, 1, carry + '0');
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

扩展

介绍string的insert用法

#include
using namespace std;
int main()
{
    string str="hello";
    string s="Hahah";
    str.insert(1,s);//在原串下标为1的字符e前插入字符串s
    cout<<str<<endl;

    string str1="hello";
    char c='w';
    str1.insert(4,5,c);//在原串下标为4的字符o前插入5个字符c
    cout<<str1<<endl;

    string str2="hello";
    string s2="weakhaha";
    str2.insert(0,s2,1,3);//将字符串s2从下标为1的e开始数3个字符，分别是eak，插入原串的下标为0的字符h前
    cout<<str2<<endl;

    return 0;
//hHahahello
//hellwwwwwo
//eakhello
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

问题1-----已解决

思路1里面，为什么要转换为ia，而不是a[i]直接运算。解决了。
首先题目里面说了给出的是二进制的字符串，也就是说虽然我们看到的比如111，实际上是0000 0111。
‘0’表示二进制存储的字符0，内存中为0011 0000，转十进制为48。而整型的0在内存中是0000 0000，所以字符型的a[i]减去字符型的‘0’，得到的是整型结果int。

            int ia = a[i] - '0';
            int ib = b[i] - '0';
            // cout << b[i];
            // cout << ib << " ";
1
2
3
4

思路2

不用补0，用reverse（）函数反转来实现的。

class Solution {
public:
    string addBinary(string a, string b) {
        int a_size = a.size();
        int b_size = b.size();
        if(a_size < b_size){
            swap(a, b);
            swap(a_size, b_size);
        }
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        string result = "";
        int carry = 0;
        int sum;
        //处理字符长度相同的部分
        for(int i = 0; i < b_size; i++){
            sum = a[i] - '0' + b[i] - '0' + carry;
            result = result + char(sum%2 + '0');  //整型转字符型
            carry = sum/2;
        }
        //处理字符长度不相同的部分
        for(int j = b_size; j < a_size; j++){
            sum = a[j] - '0' + carry;
            result = result + char(sum%2 + '0');  // + 后面整型转字符型
            carry = sum/2;
        }
        if(carry ==1){
            result = result + '1'; //这个+ ‘1’为什么直接就加在了最后？
        }
        reverse(result.begin(), result.end());
        return result;
    }
};
//"11"
//"1"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

问题2

我理解for循环结束时候，result是0 0，但是这个‘1’为什么能够直接加成了001？还是说前面的我对‘0’的认知是错误的？

        if(carry ==1){
            result = result + '1'; //这个+ ‘1’为什么直接就加在了最后？
        }
1
2
3