题解 | #大数乘法#

题解一：普通竖式法
题解思路： 模拟拆分乘法竖式，遍历t,每次相乘之和末位补n-1-i个零之后，与之前的值相加
图示：

复杂度分析：
时间复杂度：O(MN+N^2): M为s的长度，N为t的长度，中间存储字符串最长为(M+N),需要乘以N次，所以字符串相加次数也为N。所以时间复杂度为O((M+N)N)
空间复杂度：O(M+N):需要一个存储中间值的字符串，该字符串最长为(M+N);
实现如下:

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param s string字符串 第一个整数
     * @param t string字符串 第二个整数
     * @return string字符串
     */
    string add_string(string &s1,string &s2){
        if(s1=="0") return s2;
        int len1 = s1.length()-1,len2 = s2.length()-1;
        int jinwei = 0;  // 有没有进位
        string ans;
        while(len1>=0 || len2>=0 || jinwei>0)
        {
            int val1 = len1 >= 0 ? s1.at(len1) - '0' : 0;  // 提取s1各个位的值，将其转为int
            int val2 = len2 >= 0 ? s2.at(len2) - '0' : 0;  //提取s2各个位的值，将其转为int
            int res = val1 + val2 +jinwei;                 
            jinwei = res / 10;
            ans += to_string(res % 10);   // ans 加上相加之后的个位
            len1 --;
            len2 --;
        }
        reverse(ans.begin(),  ans.end()); // 同样，ans保存的是相加之后的逆序，所以需要翻转
        return ans;
    }
    string solve(string s, string t) {
        // write code here
        if(s == "0" || t == "0") return "0"; //判断是否是乘0
        int m = s.size();  //s的长度
        int n = t.size();  // t的长度
        string ans = "0"; //存储最后的答案
        for(int i = n-1;i>=0; i--)
        {
            string cur; // 存储本次乘法所产生的中间值
            int jinwei = 0; // 保存进位的值
            for(int j = n-1;j>i;j--) // 补n-1-i个0
                cur.push_back('0');
            int val = t.at(i) - '0';  //当前要乘以s的值，转为int型
            for(int j = m-1;j>=0;j--)  //循环取数相乘
            {
                int x = s.at(j) - '0';
                int pro = x * val + jinwei; // 相乘加上之前的进位
                jinwei = pro/10;            //需要向下一轮进位的数
                cur += to_string(pro % 10); // 加入当前乘完之后的个位上的值
            }
            if(jinwei) cur += to_string(jinwei);  //如果所有位乘完，进位值不为0,再将进位值加到末尾
            reverse(cur.begin(), cur.end()); //cur保存的是乘完之后值的逆序，需要翻转
            ans = add_string(ans, cur); // 加上中间值
          }
        return ans;
     }
};

题解二:多项式乘法
题解思路： 将每个数转换为多项式表示，这样就利用多项式乘法对其求积。
分析：
1.一个任意n位梳子可以用n-1次多项式表示:

2.两个多项式乘法，用A(x)和B(x)表示两个数：

可以看出得到的多项式：a与b的下标之和要等于幂次； 即 c(x):

其中m与n分别是两个数的长度。

复杂度分析：
时间复杂度：O(MN);多项式每一项都要与另一个数的多项式每一项相乘，如上图所示
空间复杂度：O(M+N);最差两个多项式的x次方都不相同，需要M+N的空间存储对应次方的系数
实现如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param s string字符串 第一个整数
     * @param t string字符串 第二个整数
     * @return string字符串
     */
    string solve(string s, string t) {
        if(s == "0" || t == "0") return "0"; // 乘以0直接返回字符串“0”
        int m = s.length(), n = t.length();
        vector<int> ans = vector<int>(m+n);  //用于保存相应幂次的权值
        for(int i = 0;i<m;i++)
        {
            int x = s[i]-'0';
            for(int j = 0;j<n;j++)
            {
                int y = t[j] - '0';
                ans[m+n-2-i-j] += x*y;   // 将权重加到相应幂次位上
            }
        }
        // 从低位向高位进位
        for(int i = 0;i<=m+n-2;i++)
        {
            ans[i+1] += ans[i] /10; // 向高位进位
            ans[i]  = ans[i] %10;
        }
        //最后是否有进位到最高位
        int index = (ans[m+n-1] == 0 ? m+n-2 : m+n-1);

        //从最高位组成字符串
        string res;
        while(index>=0){
            int tmp = ans[index--];
            res += to_string(tmp);
        }
        return res;
    }
};