首页 > 代码库 > Multiply Strings

Multiply Strings

2024-08-04 04:34:12   217人阅读

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为例

image

 

首先我们把每一位相乘，得到一个没有进位的临时结果，如图中中间的一行红色数字就是临时结果，然后把临时结果从低位起依次进位。对于一个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;}

运行结果：

Multiply Strings


联系
我们