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.
大整数乘法
我们以289*785为例
首先我们把每一位相乘,得到一个没有进位的临时结果,如图中中间的一行红色数字就是临时结果,然后把临时结果从低位起依次进位。对于一个m位整数乘以n位整数的结果,最多只有m+n位。
注意:结果中需要去掉前导0,还需要注意结果为0的情况
C++代码实现:
#include<iostream> #include<string> #include<vector> using namespace std; class Solution { public: string multiply(string num1,string num2) { string ret; int m=num1.length(); int n=num2.length(); vector<int> d(m+n,0); int i; int j; for(i=0; i<m; i++) for(j=0; j<n; j++) d[m-1+n-1-i-j]+=(num1[i]-'0')*(num2[j]-'0'); for(auto a:d) cout<<a<<" "; cout<<endl; int carry=0; for(i=0; i<m+n; i++) { d[i]+=carry; carry=d[i]/10; d[i]%=10; } auto del=d.end()-1; //分别为m和n的两个数相乘,最大的长度是m+n,如果没有进位则只有m+n-1位 while(*del==0) { d.erase(del); del--; } //防止全为零时,将d清空了 if(d.empty()) return "0"; for(auto a:d) cout<<a<<" "; cout<<endl; while(del>=d.begin()) { char c=*del+'0'; ret.push_back(c); del--; } return ret; } }; int main() { Solution s; string s1="123"; string s2="123"; cout<<s.multiply(s1,s2)<<endl; }
运行结果:
改进的代码:
对于长度分别为m和n的字符串相乘,此时得到的乘积最多为m*n位,如果首位没有进位,则只有m*n-1.对于每位的乘积等于两个字符串对应位的乘积,此时得到的乘积需要小于10,大于10的向前进位,从乘积的最低位开始与10比较,如果小于10,则直接保存,否则向前进位。
C++实现代码:
class Solution { public: string multiply(string num1, string num2) { if(num1=="0"||num2=="0") return "0"; int len1=num1.size(); int len2=num2.size(); int i,j; //len1与len2乘积最长为len1+len2,如果没有进位则只有len1+len2-1位 int res[len1+len2]; int arr1[len1]; int arr2[len2]; for(i=0;i<len1;++i) arr1[i]=num1[i]-'0'; for(i=0;i<len2;++i) arr2[i]=num2[i]-'0'; memset(res,0,sizeof(res)); string ss=""; for(i=0;i<len1;++i) { for(j=0;j<len2;++j) { res[i+j+1]+=arr1[i]*arr2[j]; } } for(i=len1+len2-1;i>=0;i--) { if(i>0) res[i-1]+=res[i]/10; res[i]%=10; ss=char(res[i]+'0')+ss; } if(ss[0]=='0') return ss.substr(1); return ss; } };