题目内容

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例

示例 1:

输入: num1 = “2”, num2 = “3”
输出: “6”

示例 2:

输入: num1 = “123”, num2 = “456”
输出: “56088”

提示

1、num1 和 num2 的长度小于110。
2、num1 和 num2 只包含数字 0-9。
3、num1 和 num2 均不以零开头，除非是数字 0 本身。
4、不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

题解

本题是高精度乘法的类型题中的一种。在求解本题时，可以回顾一种列竖式的方式求解，见下图：

每个位置的进位放置到最后处理，这样可以便于最后的计算求解。

这里，如果设A[i]和B[j]分别是num1和num2，C[k]为对应位置的乘积和，则A[i]与B[j]的乘积和应该加到C[i+j]中。

具体，请看代码注释

代码

class Solution {
public:
    string multiply(string num1, string num2) {
        //高精度乘法
        int n = num1.size(),m = num2.size();
        vector<int> A, B;
        for(int i = n - 1; i >= 0; i--) A.push_back(num1[i] - '0');//将其映射为逆序的数字
        for(int i = m - 1; i >= 0; i--) B.push_back(num2[i] - '0');//同上

        vector<int> C(n + m);
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                C[i + j] += A[i] * B[j]; //处理乘积，暂时忽略进位
        
        for(int i = 0, t = 0; i < C.size(); i++){
            //t表示进位，这里将C[i]处理成最终的答案的逆序
            t += C[i];
            C[i] = t % 10; //把个位数找出来,并赋值给C的对应位置
            t /= 10;
        }

        int k = C.size() - 1; //k代表数字位数
        while(k > 0 && !C[k]) k--;//将开头存在0的情况删除

        string res;
        while(k >= 0) res += C[k--] + '0'; //将最后的结果再映射为字符串

        return res;
    }
};