【LeetCode】大数相乘

1. 模拟手工计算

原理：

将 string 反转存储在 int 数组中，如 A = 17 = (7, 1)，B = 25 = (5, 2)，亦即幂表示法，幂次是从低位到高位。
作逐位相乘，即 a_i × b_j，结果加入到积 C 的第 i+j 位，消除高位的 0，最后处理进位。
C = A × B = (7 × 5, 1 × 5 + 7 × 2, 1 × 2) = (35, 19, 2) -> (5, 22, 2) -> (5, 2, 4)
将 int 数组逆序转换为 string，C = (5, 2, 4) = 425。

 1 string multiply(string num1, string num2) {
 2     vector<int> n1 = string2Int(num1), n2 = string2Int(num2);
 3     vector<int> result = mul(n1, n2);
 4     return int2String(result);
 5 }
 6     
 7 vector<int> string2Int(string s) {
 8     vector<int> v;
 9     for (int i = s.size() - 1; i >= 0; i--)
10         v.push_back(s[i] - '0');
11     return v;
12 }
13     
14 vector<int> mul(vector<int> n1, vector<int> n2) {
15     vector<int> result(n1.size() + n2.size(), 0);
16     /* 逐位相乘 */
17     for (int i = 0; i < n1.size(); i++)
18         for (int j = 0; j < n2.size(); j++)
19             result[i + j] += n1[i] * n2[j];
20     /* 消除多余的0 */
21     for (int i = result.size() - 1; i > 0 && result[i] == 0; i--)
22         result.pop_back();
23     /* 进位 */
24     int c = 0;
25     for (int i = 0; i < result.size(); i++) {
26         result[i] += c;
27         c = result[i] / 10;
28         result[i] %= 10;
29     }
30     if (c)
31         result.push_back(c);
32     return result;
33 }
34     
35 string int2String(vector<int> v) {
36     string s = "";
37     for (int i = v.size() - 1; i >= 0; i--)
38         s += to_string(v[i]);
39     return s;
40 }

PS：

char 转 int —— ch - '0'

int 转 char —— i + '0'

int 转 string —— to_string(i)

【char 就是一种特殊的 int 啊有木有！！！】

另外还有两种较为复杂的算法，在下实力有限，没有研究透。

2. 分治法

当把大整数分为 2 段时，算法时间复杂度最低，为 O(n^log₂3) = O(n^1.58)

3. FFT法（快速傅里叶变换）

时间复杂度 O(nlogn)