💒【LeetCode】415. 字符串相加

🧸读题

将两个字符串 用int形式相加，结果用string打印。
此题不能用int/long因为测试用例很长，longlong也存不下，所以要按位计算！

🧸代码

定义两个标记 ned1/end2从两个数组尾部开始向前走，并且用carry记录进位，
ret计算两数之和，两数相加>10 则ret -= 10 ，carry置1，否则carry置0；
创建s字符串将计算结果尾插，最后再翻转过来(这么做是为了防止，头插会一直挪动数据，造成O(N²))

class Solution {
public:
    string addStrings(string num1, string num2) {
        int end1 = num1.size()-1,end2 = num2.size()-1;
        int carry = 0;
        string s;
        while(end1 >=0 ||end2>=0)
        {
            int x1 = 0;
            if(end1>= 0 )
            {
                x1 = num1[end1] - '0';
                --end1;
            }
            int x2 = 0;
            if(end2>= 0 )
            {
                x2 = num2[end2] - '0';
                --end2;
            }
            int ret = x1+x2 + carry;
            if(ret > 9)
            {
                ret-=10;
                carry = 1;
            }
            else
            {
                carry = 0;
            }
            s += ret + '0';
        }
        if(carry == 1)
        {
            s += '1';
        }
        reverse(s.begin(),s.end());
        return s;
    }
};
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

🧸解读代码

		定义两个标记，从两个数组尾部向前访问。
        int end1 = num1.size()-1,end2 = num2.size()-1;
        定义carry保存进位
        int carry = 0;
        定义s保存结果
        string s;
        循环只要有一方没走完，就继续访问，因为carry可能有值，有可能会一直进位
        例如：9999+11 ，11走完后，carry = 1，所以9999还要继续访问知道carry被置0
        while(end1 >=0 ||end2>=0)
        {
        	x1x2是用来进行单位计算的 也就是x1 = num1[end]
        	因为每一次计数都要重置x1，x2
        	所以
            int x1 = 0; 
            判断end1有没有走完，没走完就继续算，走完了x1 = 0
            if(end1>= 0 )
            {
                x1 = num1[end1] - '0';
                --end1;
            }
            跟x1同理
            int x2 = 0;
            if(end2>= 0 )
            {
                x2 = num2[end2] - '0';
                --end2;
            }
            ret是存储 x1+x2的结果
            int ret = x1+x2 + carry;
            计算进位，如果两数相加>9 则ret-=10，进位 = 1
            if(ret > 9)
            {
                ret-=10;
                carry = 1;
            }
            else
            {
            	必须判断else ，否则进位可能一直是1
                carry = 0;
            }
            尾插两数相加的结果
            s += ret + '0';
        }
        里面判断完，如果进位里还有一个数，还要尾插进去
        if(carry == 1)
        {
            s += '1';
        }
        最后翻转则得到正确答案
        reverse(s.begin(),s.end());
        return s;
    }
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
44
45
46
47
48
49
50
51
52

🌈加油 祝你拿到心仪的offer！