题目描述
Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.
Note:
- The length of both num1 and num2 is < 5100.
- Both num1 and num2 contains only digits 0-9.
- Both num1 and num2 does not contain any leading zero.
- You must not use any built-in BigInteger library or convert the inputs to integer directly.
算法
(高精度加法) $O(n)$
参考 Acwing 791 大数相加 ,可以直接移植使用,秒掉水题
时间复杂度
只有单层for循环,时间复杂度应该是 $O(n)$
C++ 代码
class Solution {
public:
string addStrings(string num1, string num2) {
vector<int> A, B;
for (int i = num1.size() - 1; i >= 0; -- i ) A.push_back(num1[i] - '0');
for (int i = num2.size() - 1; i >= 0; -- i ) B.push_back(num2[i] - '0');
vector<int> C;
string res = "";
C = add(A, B);
for (int i = C.size() - 1; i >= 0; -- i ) res += C[i] + '0';
return res;
}
vector<int> add(vector<int> &A, vector<int> &B) {
if (A.size() < B.size()) return add(B, A);
vector<int> C;
int t = 0;
for (int i = 0; i < A.size(); ++ i ) {
t += A[i];
if (i < B.size()) t += B[i];
C.push_back(t % 10);
t /= 10;
}
if (t) C.push_back(t);
return C;
}
};