燕郊做网站公司,wordpress 游戏 模板下载,无锡专业做网站,望野怎么读算法的重要性#xff0c;我就不多说了吧#xff0c;想去大厂#xff0c;就必须要经过基础知识和业务逻辑面试算法面试。所以#xff0c;为了提高大家的算法能力#xff0c;这个公众号后续每天带大家做一道算法题#xff0c;题目就从LeetCode上面选 #xff01;今天和大家… 算法的重要性我就不多说了吧想去大厂就必须要经过基础知识和业务逻辑面试算法面试。所以为了提高大家的算法能力这个公众号后续每天带大家做一道算法题题目就从LeetCode上面选 今天和大家聊的问题叫做 字符串相乘我们先来看题面https://leetcode-cn.com/problems/multiply-strings/Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.题意给定两个以字符串形式表示的非负整数 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)或直接将输入转换为整数来处理。解题来源https://www.cnblogs.com/techflow/p/12544184.html高精度与打竖式这就需要我们的高精度算法出场了其实严格说起来高精度并不是一种算法而是一种思想。这个思想非常朴素我敢保证我们每一个人都学过。还记得小学的时候我们计算多位数的乘法是怎么算的吗大家应该都不陌生才对就是打竖式like this我们人类要打竖式是因为我们只能计算一位数以内的加减乘除超过一位的人脑不能直接计算我们就需要用纸笔记录下来进行计算。纸笔计算的方法很简单就是一位一位地计算用每一位数字依次去计算乘法最后再移位相加起来就得到结果了。比如在上图的第一个例子当中我们要计算15 * 16我们先计算6 * 15的结果再计算1 * 15最后将两个结果错位相加就得到了答案。我们要错位的原因也很简单因为我们在计算15 * 1的时候其实背后代表的是15 * 10。我们继续拆分问题当我们计算6和15相乘的时候又是怎么计算的呢顺着这个思路整个过程可以进一步被划分成先计算6和5相乘再计算6和1相乘。最后我们把两个较大数字的相乘拆分成了在每一位上的数字相乘。到了这里剩下的就简单了也就是说我们可以把这两个很大的数字用两个数组来存储数组当中的每一位存储数字上的一位。比如我们要计算123 * 224 我们的第一个数组是[1, 2, 3]我们的第二个数组是[2, 2, 4]。我们仿照乘法竖式中的方法计算这两个数组当中两两的乘积并将它们拼装成答案。123 * 224 ____________492246246 ____________27552同样我们用数组来存储中间和最后的结果最后的结果就是[2, 7, 5, 5, 2]。由于题目需要我们要返回的是字符串所以我们还需要将数组里的内容再拼接成字符串。这种用数组来模拟数字进行加减乘除运算的方法就叫做高精度算法相信大家也都看到了严格说起来这并不是一个算法而只是一种思想。今天的题目出的是乘法我们利用同样的方法也可以计算加减和除法。其中加减法非常简单而除法则要复杂得多也是高精度当中最难实现的部分。这里我们不做过多的拓展计算的方法同样是打竖式感兴趣的同学可以自行实现。进位和前导零当我们理清楚了打竖式的方法之后我们还要面临进位和前导零的问题。进位应该很容易理解我们需要在计算乘法的时候判断当前位置的元素是否大于等于10如果超过10的话我们则需要进行进位。我们只需要将它除以10得到的结果就是我们需要进位的值。除此之外就是前导零的问题我们都知道除了零以外的合法数字是不允许首位出现0的但是由于我们计算的是乘法所以当其中某一个数为0会得到整体的结果为0但是表示在数组当中则是多个0.举个简单的例子比如123 * 0最后得到的应该是0但是由于我们用数组表示了乘法运算当中的每一位并且还进行了加法计算所以会导致出现000的结果。这种情况我们要做特殊的处理不过这也不复杂。最后我们把上面所有的思路都整理一下就可以得到结果了。我们来看下代码class Solution:def multiply(self, num1: str, num2: str) - str:# 将字符串转化成数组# 翻转数组因为我们用第0位表示个位 arr1 [ord(i) - ord(0) for i in num1][:: -1] arr2 [ord(i) - ord(0) for i in num2][:: -1]# 创建结果数组可以证明结果的长度最多是n m n, m len(arr1), len(arr2) ret [0for i in range(n m 1)]for i in range(n):for j in range(m):# 按位相乘计算进位 ret[i j] arr1[i] * arr2[j]if ret[ij] 10: ret[ij1] ret[ij] // 10 ret[ij] % 10# 最后把数组再转化成字符串返回# 去除前导零 result .join(map(str, ret))[::-1].lstrip(0)return result if len(result) 0else0今天的题只是Medium难度并不算困难会选这题的原因主要是为了高精度算法。高精度算法本身并不难也并不常用即使是在算法比赛当中也不常见。但是它给了我们一个思路当我们要计算的数值超过计算机目前承载能力的时候我们还有什么方法当然这题我们也可以取巧因为Python当中内置了大整数当它检测到我们的计算结果超过范围的时候会自动转化成大整数来进行计算。所以这题如果我们使用Python可以只用几行代码搞定class Solution:def multiply(self, num1: str, num2: str) - str: num1 int(num1) num2 int(num2)return str(num1 * num2)好了今天的文章就到这里如果觉得有所收获请顺手点个在看或者转发吧你们的支持是我最大的动力。上期推文LeetCode1-20题汇总速度收藏LeetCode21-40题汇总速度收藏LeetCode刷题实战40组合总和 IILeetCode刷题实战41缺失的第一个正数LeetCode刷题实战42接雨水
