Given two numbers represented as strings, return multiplication of the numbers as a string.
Note: The numbers can be arbitrarily large and are non-negative.
题意：计算字符串对应数字的乘积。参考JustDoIT的博客。
思路：先用一维向量存放计算的中间值，中间值存放对应位置乘积的和（暂不考虑进位的情况）；然后针对进位的情况，进行计算；注意要跳过开始为0的情况（因为向量开始全部初始为0）；然后将数字转化为字符串。以234*156为例：
1 class Solution {
public:
string multiply(string num1, string num2)
{
int len1=num1.size();
int len2=num2.size();
vector<int> midVal(len1+len2,);
int k=len1+len2-;
for(int i=;i<len1;++i)
for(int j=;j<len2;++j)
{
midVal[k-i-j]+=(num1[i]-'')*(num2[j]-''); //从右向左
}
int carry=; //进位
for(int i=;i<len1+len2;++i)
{
midVal[i]+=carry;
carry=midVal[i]/;
midVal[i]%=;
}
int i=len1+len2-;
while(midVal[i]==) //去除向量中最开始的0
i--;
if(i<) return ""; //全部为0时
//将值变成字符串
string res;
for(;i>=;--i)
res.push_back(midVal[i]+'');
return res;
}
};
另外更高效的计算大整数乘法一般有：（1）karatsuba算法，复杂度为3nlog3≈3n1.585，可以参考百度百科、乘法算法-Karatsuba算法。（2）基于FFT(快速傅里叶变换)的算法，复杂度为o(nlogn), 可以参考FFT, 卷积, 多项式乘法, 大整数乘法