思路:
相加时要转换成对应的数字,所以让字符数字-'0' 如‘9’-‘0’=(ASCII)57-48=9
9+1=10,会进1,把进位保存起来,只取0头插到新串里。
头插时要转换对应字符数字,所以让对应的数字+‘0’ 如0+'0'=48 =='0'
之后下标往前走依次取值相加(每次都要+进位)。
实现
class Solution
{
public:
string addStrings(string num1, string num2)
{
int end1=num1.size()-1,end2=num2.size()-1;
int next=0;
string str;
while(end1>=0||end2>=0)
{
int val1 = 0;
int val2 = 0;
if(end1>=0)
{
val1=num1[end1--]-'0';
}
if(end2>=0)
{
val2=num2[end2--]-'0';
}
int ret=val1+val2+next;
next=ret/10;
ret%=10;
str.insert(0,1,ret+'0');
}
return str;
}
};
发现还有用例没通过,可以看出是结束时循环走出来了没有+进位,所以在循环结束后加个判断条件:
if(next==1)
{
str.insert(0,1,'1');
}
最后看到用时很长,因为头插的时间复杂度是()。
优化:
把头插换成尾插
class Solution
{
public:
string addStrings(string num1, string num2)
{
int end1=num1.size()-1,end2=num2.size()-1;
int next=0;
string str;
while(end1>=0||end2>=0)
{
int val1 = 0;
int val2 = 0;
if(end1>=0)
{
val1=num1[end1--]-'0';
}
if(end2>=0)
{
val2=num2[end2--]-'0';
}
int ret=val1+val2+next;
next=ret/10;
ret%=10;
str.push_back(ret+'0');
}
if(next==1)
{
str.push_back('1');
}
reverse(str.begin(),str.end());
return str;
}
};
时间复杂度(n)