题目描述
给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和。
提示:
num1 和num2 的长度都小于 5100
num1 和num2 都只包含数字 0-9
num1 和num2 都不包含任何前导零
你不能使用任何內建 BigInteger 库, 也不能直接将输入的字符串转换为整数形式
。
算法1
题目思想和链表数相加类似
两个数翻转后计算 注意进位 最后答案再翻转即可
时间复杂度
参考文献
C++ 代码
class Solution {
public:
string addStrings(string num1, string num2) {
string ans;
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
int p1 = 0; int p2 = 0;
int extraAdd = 0;
while (p1 < num1.size() && p2 < num2.size()) {
int sum = (num1[p1]-'0') + (num2[p2] -'0') + extraAdd;
extraAdd = sum / 10;
sum = sum % 10;
ans += to_string(sum);
p1++; p2++;
}
while (p1 < num1.size()) {
int sum = (num1[p1] - '0') + extraAdd;
extraAdd = sum / 10;
sum = sum % 10;
ans += to_string(sum);
p1++;
}
while (p2 < num2.size()) {
int sum = (num2[p2] - '0') + extraAdd;
extraAdd = sum / 10;
sum = sum % 10;
ans += to_string(sum);
p2++;
}
if (extraAdd != 0) {
ans += to_string(extraAdd);
}
reverse(ans.begin(),ans.end());
return ans;
}
};