LeetCode--43.字符串相乘

发布于:2025-07-12 ⋅ 阅读:(21) ⋅ 点赞:(0)

前言:没脸提了,连续断更两天了,我会尽力克制自己的懒惰的

解题思路:

        1.获取信息:

                给定两个字符串形式表示的非负整数,返回这两个非负整数的乘积的字符串形式

                提示信息:字符串只由数字组成

                                  不包含任何前导零,除了单独一个数字0这种情况

        2.分析题目:

                既然要求出它们的乘积,那肯定会有将字符串形式转换为数字形式的过程,

                转换为了数字形式,那么就会用到乘法或者以加法来模拟乘法等方式求出乘积,

                之后还会有将数字形式转换为字符串形式的过程

                我们要设计代码的话,肯定是要根据需求来设计的

                我看了几种方法吧,其实大概中心思路都是一样的,毕竟只是一个乘法嘛

                所以,我用我自己的理解写了一份自己的代码,我的侧重点是防止溢出,你可以品味一下

        3.示例查验:

                略

        4.尝试编写代码:

                (1)暴力法(侧重于防止溢出)

                        思路:我想到由于数字是以字符串形式来展现出来的,所以我们在将它转换为数字形式的时候,难免可能会溢出,万一它是一个很大很大的数,那么我们该怎么办呢?

                        对于一个数,我们可以创建一个数组,将它各个位数上的数字依次存入其中,就从下标为0的位置开始存入,这样不仅各个位数上的数字我们都存入了,我们还可以根据它的下标来判断它的位数是多少

                        现在知道怎么存入一个数了,那么该怎么实现它们的乘法呢?

                        你试着在纸上将两个数分别按每个位数分开来,将它们相乘,按照乘法分配律展开,就会发现,每个位数的数与另一个乘数的每个位数的数相乘,得到的结果,只反映了该位数和一个更高的位数上的数,所以可以利用这个性质来进行乘法,并且储存结果

class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1=="0"||num2=="0")return "0";//如果有任意一个数为0,则返回0
        int m=num1.size();//数字1的位数
        int n=num2.size();//数字2的位数
        vector<int>Num1(m,0);//创建数组来存储它们的数字形式
        vector<int>Num2(n,0);
        for(int i=m-1;i>=0;i--){//开始取出各个位数上的数字
            Num1[m-i-1]=num1[i]-'0';
        }
        for(int i=n-1;i>=0;i--){
            Num2[n-i-1]=num2[i]-'0';
        }
        vector<int>Num(m+n+1,0);//存储结果的数组
        for(int i=0;i<m;i++){//开始进行乘法的操作
            for(int j=0;j<n;j++){
                int num=Num1[i]*Num2[j];
                int les=0;
                for(int k=i+j;num>0||les!=0;k++){
                    Num[k]+=(num%10+les);
                    num/=10;
                    les=0;
                    if(Num[k]>9){
                        les=Num[k]/10;
                        Num[k]%=10;
                    }
                }
            }
        }
        string res;//结果的字符串形式
        for(int i=m+n-1;i>=0;i--){//将数字形式转换为字符串形式
            if(res==""&&Num[i]==0)continue;
            res+=('0'+Num[i]);
        }
        return res;
    }
};

完了哦,有没有意犹未尽的感觉,如果有的话,就自己动手做做吧

我尽量从今天开始不断更,如果要断更了,我是会说的,不是小哑巴


网站公告

今日签到

点亮在社区的每一天
去签到