如图:根据题目要求直接装string转换为int计算不显示,因为num1和num2的位数最大为110位,int或者long long int都实现不了,那么我们可以考虑模拟乘法运算。
这里可以从右往左遍历乘数,将乘数的每一位与被乘数相乘得到对应的结果,再将每次得到的结果累加,但整个过程中涉及到较多字符串相加的操作,时间复杂度会像滚雪球一样越往后越高。
如果使用数组代替字符串存储结果,则可以减少对字符串的操作。所以在这里我们考虑用一个数组去存储每一位字符串的运算,
令 m 和 n 分别表示num1和num 2的长度,并且它们均不为 0,则num 1 和 num 2的乘积的长度为m+n−1 或 m+n。
简单证明如下:
由于num 1和 num 2的乘积的最大长度为m+n,因此创建长度为m+n 的数组res 用于存储乘积。
对于任意 0≤i<m和0≤j<n,num1[i]×num 2[j] 的结果位于res[i+j+1],
如果res[i+j+1]≥10,则将进位部分加到res[i+j]。
注意:因为我们是倒着读取运算数据所以i+j实际是比i+j+1更高一位,同时数组都是从0开始读取数据,所以坐标为i和j实际对应的位数是j+1和i+1,i+j+2对应于存储数组res又是i+j+1位。
最后,将数组 res 转成字符串,如果最高位是 0 则舍弃最高位。
看代码:
class Solution {
public:
string multiply(string num1, string num2) {
if(num1=="0"||num2=="0")return "0";
int m=num1.size(),n=num2.size();
vector<int> res(m+n);
for(int i=m-1;i>=0;i--){
for(int j=n-1;j>=0;j--){
int ans=int(num1[i]-'0')*int(num2[j]-'0');
res[i+j+1]+=ans;
}
}
for(int i=m+n-1;i>=1;i--){
res[i-1]+=res[i]/10;
res[i]=res[i]%10;
}
string s;
for(int i=0;i<m+n;i++){
s +=to_string(res[i]);
}
if(s[0]=='0')s.erase(s.begin());
return s;
}
};
测试用例
int main()
{
Solution *x=new Solution;
cout << x->multiply("123456", "445");
}
测试结果