https://leetcode.com/problems/multiply-strings/?tab=Description
模拟我们平时做多位乘法的操作，依次把一个乘数与另一个乘数的每一位分别相乘，最后加和。
class Solution {
public:
string multiply(string num1, string num2) {
if (num1 == "0" || num2 == "0") return "0";
int n1 = num1.size(), n2 = num2.size();
string ret = "0", zeros = "";
for (int i = n2 - 1; i >= 0; --i) {
// compute num1 * nums2[i]
string numi = "";
int fac = num2[i] - '0', carry = 0;
for (int j = n1 - 1; j >= 0; --j) {
carry += (num1[j] - '0') * fac;
numi = to_string(carry % 10) + numi;
carry /= 10;
}
if (carry != 0) numi = to_string(carry) + numi;
numi += zeros; zeros += "0";
// add the result
ret = addBinary(ret, numi);
}
return ret;
}
string addBinary(string a, string b) {
int p1 = a.size() - 1, p2 = b.size() - 1, carry = 0;
string ret = "";
while (true) {
if (p1 >= 0) carry += (a[p1--] - '0');
if (p2 >= 0) carry += (b[p2--] - '0');
string next_digit = to_string(carry % 10);
carry /= 10;
if (p1 >= 0 || p2 >= 0 || carry != 0 || next_digit != "0") {
ret = next_digit + ret;
} else break;
}
// remove the prefix '0'
int i = 0;
while (i < ret.size()) {
if (ret[i] != '0') break;
i++;
}
if (ret.empty()) ret = "0";
return ret.substr(i, ret.size() - i);
}
};
其中addBinary函数就是大整数加法(leetcode 67: https://leetcode.com/problems/add-binary/
)。
上面这份代码可以AC。不过，虽然时间复杂度是O(n^2)，但是性能不高(C++ 190ms左右)。
-----懒惰与勤劳的分界线-----
举个例子，看能不能将代码写得更简单些，以乘法324 * 78为例，我们做乘法的方式是：
---------
3 2 4
x 7 8
---------
2 5 9 2
2 2 6 8
---------
2 5 2 7 2
我们将位数按从右往左的顺序编号为0,1,2... 观察结果：
- 第0位 = 4 * 8（除去进位），在两个乘数的位置是(0, 0)
- 第1位 = 2 * 8 + 4 * 7 + 结果第0位的进位（后除去进位），分别在两个乘数的位置是(1, 0), (0, 1)
- 第2位 = 3 * 8 + 2 * 7 + 结果第1位的进位（后除去进位），分别在两个乘数的位置是(2, 0), (1, 1)
- 第3位 = 3 * 7 + 结果第2位的进位（后除去进位），在两个乘数的位置是(2, 1)
- 第4位 = 第3位的进位
规律：结果的第i位 = 两个乘数位置相加恰好为i的数位乘积的加和，再加上结果第i-1位的进位。
实现上，可以用一个int数组mul（大小为两个乘数数位长度之和）存放数位乘积，按mul[i+j] += (num1[i] * num2[j])，然后再把进位算进去，构造出最后的结果。
class Solution {
public:
string multiply(string num1, string num2) {
if (num1 == "0" || num2 == "0") return "0";
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
int n1 = num1.size(), n2 = num2.size();
vector<int> mul(n1 + n2, 0);
for (int i = 0; i < n1; ++i) {
int mul1 = num1[i] - '0';
for (int j = 0; j < n2; ++j) {
mul[i+j] += mul1 * (num2[j] - '0');
}
}
string ret = "";
int carry = 0;
for (int i = 0; i < mul.size(); ++i) {
carry += mul[i];
ret = to_string(carry % 10) + ret;
carry /= 10;
}
if (carry != 0) ret = to_string(carry) + ret;
// remove the prefix '0'
int i = 0;
while (i < ret.size() && ret[i] == '0') i++;
return ret.substr(i, ret.size() - i);
}
};
上面这份代码的时间复杂度依然是$O(n^2)$，但是跑leetcode的所有数据降到了10ms左右，性能明显提升。
另外值得一提的是，大数乘法可以通过Fast Fourier Transform(FFT)算法计算多项式乘积将复杂度降到O(n logn)，而FFT则是基于分治的思想，这里就不深入下去了。