题解 | #大数乘法#
大数乘法
http://www.nowcoder.com/practice/c4c488d4d40d4c4e9824c3650f7d5571
问题描述：
以字符串的形式读入两个数字，编写一个函数计算它们的乘积，以字符串形式返回。
数据范围： 读入的数字大小满足0≤n≤101000
要求：空间复杂度 O(n)，时间复杂度 O(n2)
要求：空间复杂度 O(n)，时间复杂度 O(n2)
问题分析：两个数相乘可以拆成较小的一个数的每位与较大的数乘积，然后每个乘积的和就是
两数相乘的结果。所以我们需要解决的问题就拆分成了1、1位数与一个大数相乘；2、两个大
数相加的问题。
两个大数相加，字符串形式比较简单，主要就是注意进位问题。
然后就是一个个位数与一个大数相乘的问题。因为不确定乘积是几位数，每次的乘积都不同，
所以我们可以将末尾放在前面然后逐个加到字符串后面，最后反转所得到的字符串。
大数相加具体过程看函数sadds()，个位数与大数相乘可以看函数Pro()；在需要注意的地方都
有相应的注释。代码中有个欲处理如果t的长度比s的长度大，那么就进行swap(s,t)操作，这样
是为了保证s在长度上是最大的，也能减少迭代次数，同时还能优化函数设计。
复杂度分析：假设s.size=m,t.size=n
时间复杂度O(n2)：Pro函数为O(n)，取决于m的大小；sadds()函数为O(n2)，取决于m*n的大小。
空间复杂度O(n2)：取决于m*n的大小。
class Solution {
public:
string solve(string s, string t) {
if(s.size()<t.size()) swap(s,t);
if(t[0]=='0') return "0";
int N=t.size();
int M=s.size();
string curZero="";//保存当前需要在得数后面添加0的个数
string res="";//保存答案
string cur;//当前乘积，t中每个数与s的乘积。
for(int i=N-1;i>=0;--i) {
if(t[i]=='0') cur="0";
else cur=Pro(s,M,t[i]-'0')+curZero;//每次需要在后面添加0
res=sadds(res,cur);
curZero+="0";
}
return res;
}
string sadds(string res,string str2) {
if(str2=="0") return res;
if(res.size()<str2.size()) swap(res,str2);//保证res是最大长度的
int k=0;//进位标志
int x;//保存两个字符串每位相加的和，需加进位。从底到高
int m=res.size()-1;
int n=str2.size()-1;
while(n>=0) {
x=res[m]-'0'+str2[n]-'0'+k;
res[m]=(x%10)+'0';
k=x/10;
--m,--n;
}
if(m==n&&k) {//当两个字符串长度相等时，需要考虑最后一次的进位
res.insert(res.begin(),'1');
return res;
}
while(m>=0&&k) {//较短字符串已经结束了，每次就看是否有进位
x=res[m]-'0'+k;
res[m]=(x%10)+'0';
k=x/10;
--m;
}
//如果上面一步一直到第一位，就需要看是否有进位
if(m==-1&&k) res.insert(res.begin(),'1');
return res;
}
string Pro(string s,int M,int x) {
// if(x==0) return "0";//主函数已经考虑了t[i]==‘0’
string m="";//保存当前乘积，是倒着的，方便操作
int k=0;//进位标
int mul=0;//x就是主函数t[i]的数字，保存每次x与s[j]的乘积
for(int j=M-1;j>=0;--j) {
mul=(s[j]-'0')*x+k;
m+=((mul%10)+'0');
k=mul/10;
}
if(k!=0) m+=(k+'0');//结束后需要看是否有进位
reverse(m.begin(),m.end());//最后反转字符串就是当前乘积
return m;
}
};
