?【LeetCode】415. 字符串相加
?读题
将两个字符串 用int形式相加，结果用string打印。
此题不能用int/long因为测试用例很长，longlong也存不下，所以要按位计算！
?代码
定义两个标记 ned1/end2从两个数组尾部开始向前走，并且用carry记录进位，ret计算两数之和，两数相加>10 则ret -= 10 ，carry置1，否则carry置0；
创建s字符串将计算结果尾插，最后再翻转过来(这么做是为了防止，头插会一直挪动数据，造成O(N^2^))
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;
}
};?解读代码
定义两个标记，从两个数组尾部向前访问。
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;
}