題目
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;
}
};
分析
這道題讓我們求兩個(gè)字符串?dāng)?shù)字的相乘涌献，輸入的兩個(gè)數(shù)和返回的數(shù)都是以字符串格式儲(chǔ)存的飒货，這樣做的原因可能是這樣可以計(jì)算超大數(shù)相乘蚜退，可以不受int或long的數(shù)值范圍的約束糙俗。
我們小時(shí)候都學(xué)過多位數(shù)的乘法過程，都是每位相乘然后錯(cuò)位相加卫病，那么這里就是用到這種方法绿满，把錯(cuò)位相加后的結(jié)果保存到一個(gè)一維數(shù)組中色罚，然后分別每位上算進(jìn)位，最后每個(gè)數(shù)字都變成一位赋除，然后要做的是去除掉首位0阱缓，最后把每位上的數(shù)字按順序保存到結(jié)果中即可。
至于為什么n1位乘以n2位举农，結(jié)果最多為n1+n2位荆针，具體的運(yùn)算過程可以參見這篇博客。
