题目
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.
Note:
1.The length of both num1 and num2 is < 110.
2.Both num1 and num2 contains only digits 0-9.
3.Both num1 and num2 does not contain any leading zero.
4.You must not use any built-in BigInteger library or convert the inputs to integer directly.
解题之法
class Solution {
public:
string multiply(string num1, string num2) {
string res;
int n1 = num1.size(), n2 = num2.size();
int k = n1- 1 + n2 - 1, carry = 0;
vector<int> v(n1 + n2, 0);
for (int i = 0; i < n1; ++i) {
for (int j = 0; j < n2; ++j) {
v[k - i - j] += (num1[i] - '0') * (num2[j] - '0');
}
}
for (int i = 0; i < n1 + n2; ++i) {
v[i] += carry;
carry = v[i] / 10;
v[i] %= 10;
}
int i = n1 + n2 - 1;
while (v[i] == 0) --i;
if (i < 0) return "0";
while (i >= 0) res.push_back(v[i--] + '0');
return res;
}
};
分析
这道题让我们求两个字符串数字的相乘，输入的两个数和返回的数都是以字符串格式储存的，这样做的原因可能是这样可以计算超大数相乘，可以不受int或long的数值范围的约束。
我们小时候都学过多位数的乘法过程，都是每位相乘然后错位相加，那么这里就是用到这种方法，把错位相加后的结果保存到一个一维数组中，然后分别每位上算进位，最后每个数字都变成一位，然后要做的是去除掉首位0，最后把每位上的数字按顺序保存到结果中即可。
至于为什么n1位乘以n2位，结果最多为n1+n2位，具体的运算过程可以参见这篇博客。
