题目描述
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
样例
Example 1:
Input: num1 = "2", num2 = "3"
Output: "6"
Example 2:
Input: num1 = "123", num2 = "456"
Output: "56088"
注意事项
Note:
- The length of both num1 and num2 is < 110.
- Both num1 and num2 contain only digits 0-9.
- Both num1 and num2 do not contain any leading zero, except the number 0 itself.
- You must not use any built-in BigInteger library or convert the inputs to integer directly.
算法
(高精度乘法) $O(n^2)$
参考 Acwing 793 题目, 此时不是大数乘以低精度题目,而是两个大数进行相乘。在这采用思路与Acwing题目思路相同,把其中一个大数抽取每个位分别与第二个大数相乘,然后相加。中间注意移位补0,和手算时方法相同。
时间复杂度
因为是多重循环,时间复杂度应该会 $O(n^2)$
C++ 代码
class Solution {
public:
string multiply(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 = mul(A, B);
string res = "";
for (int i = C.size() - 1; i >= 0; i -- ) res += C[i] + '0';
return res;
}
vector<int> mul(vector<int> &A, vector<int> &B) {
if (A.size() > B.size()) return mul(B, A);
vector<int> Sum = {0};
for (int i = 0; i < A.size(); ++ i ) {
vector<int> C;
int t = 0;
for (int j = 0; j < B.size() || t; ++ j) {
if (j < B.size()) t += B[j] * A[i];
C.push_back(t % 10);
t /= 10;
}
for (int k = i; k > 0; k --) C.insert(C.begin(), 0);
Sum = add (Sum, C);
}
while (Sum.size() > 1 && Sum.back() == 0) Sum.pop_back();
return Sum;
}
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;
}
};