题解 LeetCode 第 43 题：字符串相乘

女爷i 2023-07-19 12:14 3阅读 0赞

点击上方蓝字设为星标![format_png][]

下面开始今天的学习～

![format_png 1][]

## 1 前言 ##

今天来写一道leetcode的中等难度的题目，声明一下：这不是最优解，就是常规思路。

之所以写出来，是因为我觉得：如果你的想法比较复杂或者比较冗长，那也没关系，写出来ac了它，能绕过层层关卡做出来同样值得。

就好像我们新接手了同事的代码，第一反应可能是这么复杂，但是竟然还能跑，所以尽管很绕，但是没有把他绕晕，那么我觉得他也挺厉害的了。

工作中我就遇到过这样的代码，同事的开发能力比较强，但是代码风格跟我差别很大，期间接过他一点代码，可能是过设计了，但是运行得很好。

在我们没有做那么多题目的前提下，第一想法很重要，面试的时候往往很紧张，把握住你的第一想法去实现它，最终做出来足够让面试官觉得你还不错，在此基础上优化就是加分。

有些题目的最优解或者优化解并不好想，如果不是acm打手或者天资异禀的高手还是有难度的。

所以不要嫌弃这不是最优解，最起码这是最容易想到的解法，当然你们也可以觉得不是最优解没有意义，非要嫌弃鄙视一下，那也么得办法，啊哈哈。

废话不说，开车开车！

## 2.题目描述 ##

> 给定两个以字符串形式表示的非负整数 num1 和 num2，  
> 返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

> 示例 1:  
> 输入: num1 = "2", num2 = "3"  
> 输出: "6"

> 示例 2:  
> 输入: num1 = "123", num2 = "456"  
> 输出: "56088"

> 说明：  
> num1 和 num2 的长度小于110。  
> num1 和 num2 只包含数字 0-9。  
> num1 和 num2 均不以零开头，除非是数字 0 本身。  
> 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

## 3.题目分析 ##

这个题目描述也比较清晰了，就是给了两个字符串格式的数字，让返回两个数的乘积字符串。

题目限定了不要使用bigint和输入转整数这种系统的机制，并且给定了num1和num2的长度小于110，这也说明了长度可能是100那么长，110位就已经非常大了，所以不要考虑转换整数的想法了。

其实这个问题很熟悉，这就是个计算器嘛，我们要把很长的两个字符串相乘。

第一想法就是那模拟一下两个数相乘的具体过程，再转换为代码，是的，这个想法就足够了。

## 4.手动模拟 ##

来吧，有了第一想法，那就开始在纸上划拉划拉。

![format_png 2][]

在纸上大致模拟了一下之后，基本上就能把握几个点了：

*  **乘数和被乘数的两个循环**  
    在计算循环过程中，涉及到一个默认补0的过程，因为数字所在的位不一样，这样是要注意的，这样我们得到三个字符串，这三个字符串本质上是逆序的，因为我们是先从低位开始计算的。
 *  **各个临时结果的累加**  
    也就是图中的第二部分，这里是把多个临时结果累加就可以了，最开始我把第一部分的结果做了reverse,但是在第二部分累加时发现没有必要，最后把结果reverse一下即可。
 *  **细节问题**  
    在基本了解流程之后，肯定会有一些需要注意的致错细节，这个很多时候是debug时发现的，这道题我代码写完之后debug出两个错误的点，反过来想是细节考虑不周全。

## 4.我的糙代码 ##

代码提交了几次才通过，看下时间和空间：

![format_png 3][]

无奈同行们太优秀，被80%的同行大败了，不过就算反面教材也可以看看吧：

class Solution {
    public:
        //将string指定位置的字符转换为数字
        int getvalue (string &num, int index){
            return num[index]-'0';
        }
    
    
        //遍历子结果字符串 累加
        void calthem(vector<string> &resvec, int maxlen, string &resstr){
            //按照最大长度开始从低位向高位遍历
            int veclen = resvec.size();
            int jinwei = 0;
    
    
            for(int i=0;i<maxlen;i++){
                //开始遍历每一次的结果
                int this_sum = 0;
                this_sum += jinwei;
                for(int j=0;j<veclen;j++){
                    if(i<resvec[j].length()){
                        this_sum+=getvalue(resvec[j],i);
                    }
                }
                jinwei = this_sum/10;
                int remain = this_sum%10;
                resstr+=to_string(remain);
            }
            if(jinwei!=0)
                resstr+=to_string(jinwei);
            reverse(resstr.begin(),resstr.end());
        }
    
    
        string multiply(string num1, string num2) {
            //特殊情况
            string res("");
            if(num1=="0"||num2=="0")
                return "0";
            //其他情况
            /* 1.完全模拟乘法的计算过程
               2.使用两个循环 增加每次计算的结果 以及进位
               3.由于要求不可直接将输入转换为整数 可以使用ascii来确定单个字符的数值
            */
            int len1 = num1.length();
            int len2 = num2.length();
            //存储每次循环的结果 后续的累加 要从其中进行遍历
            vector<string> resvec;
            int maxlen=0;
            //我们从乘数 nums2开始作为外层循环 即456 并且从个位开始循环
            //为了对齐将结果后默认补齐0
            for(int i=len2-1;i>=0;i--){
                int jinwei = 0;
                //从低位到高位循环被乘数 并初始化进位
                int outer = getvalue(num2,i);
                int zero_cnt = len2-1-i;
                string this_round_res="";
                this_round_res.append(zero_cnt,'0');
                for(int j=len1-1;j>=0;j--){
                    int inner = getvalue(num1,j);
                    //计算两个位的乘积 并取保留值和进位
                    //eg 8*9=72 上一次进位0 综合得：保留位2 进位7
                    int calres = inner*outer+jinwei;
                    jinwei = calres/10;
                    int remain = calres%10;
                    //这里注意 乘积是从低位开始运算的 因此需要注意方向问题
                    //为了方便解决 将低位放在字符串首位 高位依次追加 最后反转即可
                    this_round_res+=to_string(remain);
                }
                if(jinwei!=0)
                    this_round_res+=to_string(jinwei);
                maxlen = maxlen>=this_round_res.length()?maxlen:this_round_res.length();
                resvec.push_back(this_round_res);
            }
            //累加vector中的数据
            calthem(resvec,maxlen,res);
            return res;
        }
    };

代码好像还是比较长，不过本质上就两个部分，第一个是利用两个循环获得临时结果字符串，把字符串存储在vector中，第二部分就是把vector中的临时字符串累加返回。

其中尽量不用api,能自己造的轮子就自己写了，权当一题多练了。

## 5.优化解 ##

我的糙代码ac之后，惯例打开题解看看同行有什么妙招，其中有一个讲的比较好，是对算数过程的优化，说实话我的算数并不好，所以这个是第一次看到，现场我是想不到， 不过很有用一起看下：

![format_png 4][]

这个优化法是把计算过程中的值的坐标都提前知道了，所以就相当于一步到位，不过我还没来得及实验可以快多少，等下试试。

最后依然是，感谢各位的观摩！

**END**

--------------------

![format_png 5][]

● [我这些年从来没有用过算法，除了出去面试的时候][Link 1]

[● ][Link 2][恕我直言，我怀疑你没怎么用过枚举][Link 3]

● [面试了15位来自985/211高校的2020届研究生，熬夜赶出了这篇文章][15_985_211_2020]

● [关于计算机读研的小建议][Link 4]

![format_png 6][]

点“在看”你懂得

![format_png 7][]

[format_png]: /images/20230528/686a75bf5321499d853dd463a4cbe94f.png
[format_png 1]: /images/20230528/92972df21b6041b894a7d0394c67c06b.png
[format_png 2]: /images/20230528/60ade766a22f40e6990dc1daba405eb0.png
[format_png 3]: /images/20230528/fe9b9a94b6db46dfa27c789847df8ac2.png
[format_png 4]: /images/20230528/a436d329f6d240b1b1a213ad023497e5.png
[format_png 5]: /images/20230528/a343c9348c8740d0827e7893b77320ad.png
[Link 1]: https://blog.csdn.net/kexuanxiu1163/article/details/105190257
[Link 2]: http://mp.weixin.qq.com/s?__biz=Mzg2MzE5MjMxNQ%3D%3D&chksm=ce7ef418f9097d0e01bfe9410a9e40e9f4337c835c87e28332e6a8d8fd8b91b4794164f4c1a1&idx=1&mid=2247491980&scene=21&sn=5ef03c0108a5730fa28e492ec77e22d9#wechat_redirect
[Link 3]: https://blog.csdn.net/kexuanxiu1163/article/details/105132009
[15_985_211_2020]: https://blog.csdn.net/kexuanxiu1163/article/details/105172002
[Link 4]: https://blog.csdn.net/kexuanxiu1163/article/details/104078939
[format_png 6]: /images/20230528/f31a91ab235d4121a32c0a477cbc07f0.png
[format_png 7]: /images/20230528/9e74e9abee304c06b1960af21ff3dae8.png