原题
给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和。
注意:
- num1 和num2 的长度都小于 5100.
- num1 和num2 都只包含数字 0-9.
- num1 和num2 都不包含任何前导零。
- 你不能使用任何內建 BigInteger 库, 也不能直接将输入的字符串转换为整数形式。
思路
这是一道大整数相加的经典题目,值得注意的是,为了方便计算我们通常习惯性地会将数字的低位存放到字符数组(或字符串)的低位。无论是加减乘除。
class Solution {
public:
string addStrings(string num1, string num2) {
string ans;
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
int i = 0, t = 0;
while (i < num1.size() || i < num2.size()) {
int n1 = 0, n2 = 0;
if (i < num1.size()) n1 = num1[i] - '0';
if (i < num2.size()) n2 = num2[i] - '0';
ans.push_back('0' + (n1 + n2 + t) % 10);
t = (n1 + n2 + t) / 10;
++i;
}
if (t > 0) ans.push_back('0' + t);
while (ans.size() > 1 && ans.back() == 0) ans.pop_back();
reverse(ans.begin(), ans.end());
return ans;
}
};
复杂度分析
时间复杂度:O(n)
空间复杂度:O(1)
参考
[1]. LeetCode 原题. https://leetcode-cn.com/problems/add-strings/
欢迎分享,引用。若转载,请联系我,谢谢配合。 本文地址:https://qoogle.top/xiaoxu-tutorial-leetcode-415-add-string/
1emissions