点击上方蓝字设为星标题解 LeetCode 第 43 题 :字符串相乘

下面开始今天的学习~

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

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.手动模拟

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

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

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

  • 乘数和被乘数的两个循环
    在计算循环过程中,涉及到一个默认补0的过程,因为数字所在的位不一样,这样是要注意的,这样我们得到三个字符串,这三个字符串本质上是逆序的,因为我们是先从低位开始计算的。

  • 各个临时结果的累加
    也就是图中的第二部分,这里是把多个临时结果累加就可以了,最开始我把第一部分的结果做了reverse,但是在第二部分累加时发现没有必要,最后把结果reverse一下即可。

  • 细节问题
    在基本了解流程之后,肯定会有一些需要注意的致错细节,这个很多时候是debug时发现的,这道题我代码写完之后debug出两个错误的点,反过来想是细节考虑不周全。

4.我的糙代码

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

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

无奈同行们太优秀,被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之后,惯例打开题解看看同行有什么妙招,其中有一个讲的比较好,是对算数过程的优化,说实话我的算数并不好,所以这个是第一次看到,现场我是想不到, 不过很有用一起看下:

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

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


最后依然是,感谢各位的观摩!


END



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

● 我这些年从来没有用过算法,除了出去面试的时候

● 恕我直言,我怀疑你没怎么用过枚举

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

关于计算机读研的小建议


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


点“在看你懂得 

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

原文始发于微信公众号(五分钟学算法):题解 LeetCode 第 43 题 :字符串相乘