大数问题

Posted on | In ,

夸父与日逐走，入日；渴，欲得饮，饮于河、渭；河、渭不足，北饮大泽。未至，道渴而死。弃其杖，化为邓林。

大数加法

大数乘法

令$m$和$n$分别为num1与num2的长度，且均不为0，则num1和num2乘积的长度为$m+n$或$m+n-1$。因此我们创建一个长度为$m+n$的数组arr用于保存结果。对于任意的$0\le i<m$和$0\le j<n$，num1[i]和num2[j]的乘积位于arr[i+j+1]中，如果有进位，那么将进位部分加至arr[i+j]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") {
            return "0";
        }
        int m = num1.size(), n = num2.size();
        auto ansArr = vector<int>(m + n);
        for (int i = m - 1; i >= 0; i--) {
            int x = num1.at(i) - '0';
            for (int j = n - 1; j >= 0; j--) {
                int y = num2.at(j) - '0';
                ansArr[i + j + 1] += x * y;
            }
        }
        for (int i = m + n - 1; i > 0; i--) {
            ansArr[i - 1] += ansArr[i] / 10;
            ansArr[i] %= 10;
        }
        int index = ansArr[0] == 0 ? 1 : 0;
        string ans;
        while (index < m + n) {
            ans.push_back(ansArr[index] + '0');
            index++;
        }
        return ans;
    }
};

大数减法

参考文献

0%