字符串相乘（大数相乘）

1、思路(字符串模拟） O(n*m)

一、普通竖式

以num1 = 123 , num2 = 456为例：我们遍历 num2 每一位与 num1 进行相乘，将每一步的结果进行累加，在这个过程如果相乘或者相加的结果大于等于10 ，我们都要去满10进位，如下图所示：

这样模拟普通竖式计算的方法较为复杂，我们可以考虑优化版的竖式计算。

二、优化竖式

其实在相乘或者相加计算过程的每一位，我们可以考虑先不去满10进位，等到计算完所有的相乘结果以后，最终将其加到一块，再去满10进位 ，最后的结果和普通竖式 一样，但却可以大大简化我们的模拟过程。(如下图所示)

class Solution {
public:
    string multiply(string num1, string num2) {
        vector<int> A,B;
        int n=num1.size();
        int m=num2.size();
        vector<int> C(n+m);

        for(int ii=n-1;ii>=0;ii--) A.push_back(num1[ii]-'0');//-'0'把字符变成数字
        for(int ii=m-1;ii>=0;ii--) B.push_back(num2[ii]-'0');

        for(int ii=0;ii<A.size();ii++){
            for(int jj=0;jj<B.size();jj++){
                C[ii+jj]+=A[ii]*B[jj];
            }
        }

        int t=0;//存储进位
        for(int ii=0;ii<C.size();ii++){
            t+=C[ii];//为了利用上上面那个进位
            C[ii]=t%10;//进位操作的固定写法，先t%10取个位，然后再t/10进位
            t/=10;
        }

        int kk=C.size()-1;
        while(kk>0&&!C[kk]) kk--;//去除前导0 比如此例 "2" "3"->"06"

        string res;
        for(;kk>=0;kk--){
            res+=C[kk]+'0';//+'0'把数字变成字符
        }
        return res;
    }
};