LeetCode43,一题让你学会高精度算法

2019/04/10 10:10
阅读数 21

本文始发于个人公众号:TechFlow,原创不易,求个关注

<br>

<section id="nice" data-tool="mdnice编辑器" data-website="https://www.mdnice.com" style="font-size: 16px; color: black; padding: 0 10px; line-height: 1.6; word-spacing: 0px; letter-spacing: 0px; word-break: break-word; word-wrap: break-word; text-align: left; font-family: Optima-Regular, Optima, PingFangSC-light, PingFangTC-light, 'PingFang SC', Cambria, Cochin, Georgia, Times, 'Times New Roman', serif; margin-top: -10px;"><p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">今天是<strong style="font-weight: bold; color: rgb(71, 193, 168);">LeetCode系列第22篇</strong>文章,今天讲的内容是高精度算法。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">今天和大家讨论的算法是高精度,对应的LeetCode是第43题。题面其实没什么好说的,以字符串的形式给定两个数字,要求返回这两个数字的乘积。之所以是以字符串的形式给数字是因为<strong style="font-weight: bold; color: rgb(71, 193, 168);">这个数字可能会非常大</strong>,题目当中给定的范围是110位的数字。对于Python来说这不是问题,但是对于C++和Java等语言来说这么大的数字是无法以int类型存储的,所以必须要使用字符串来接收。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">如果你使用Python,你可以不用任何算法就AC这题,但是这没有任何意义。那么<strong style="font-weight: bold; color: rgb(71, 193, 168);">正确的方法</strong>应该怎么做呢?</p> <h2 data-tool="mdnice编辑器" style="font-weight: bold; font-size: 22px; border-bottom: 2px solid rgb(89,89,89); margin-bottom: 50px; margin-top: 100px; color: rgb(89,89,89);"><span class="prefix" style="font-size: 22px; border-bottom: 2px solid rgb(89,89,89); display: none;"></span><span class="content" style="font-size: 22px; display: inline-block; border-bottom: 2px solid rgb(89,89,89);">高精度与打竖式</span><span class="suffix" style="font-size: 22px; display: inline-block; border-bottom: 2px solid rgb(89,89,89);"></span></h2> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">这就需要我们的<strong style="font-weight: bold; color: rgb(71, 193, 168);">高精度算法</strong>出场了,其实严格说起来高精度并不是一种算法,而是一种思想。这个思想非常朴素,我敢保证我们每一个人都学过。还记得小学的时候,我们计算多位数的乘法是怎么算的吗?大家应该都不陌生才对,就是<strong style="font-weight: bold; color: rgb(71, 193, 168);">打竖式</strong>,like this:</p> <figure data-tool="mdnice编辑器" style="margin: 0; margin-top: 10px; margin-bottom: 10px;"><img src="https://user-gold-cdn.xitu.io/2020/3/22/170ffe9af707fa57?w=512&h=414&f=png&s=120968" alt style="display: block; margin: 0 auto; width: auto; max-width: 100%;"></figure> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">我们人类要打竖式是因为我们<strong style="font-weight: bold; color: rgb(71, 193, 168);">只能计算一位数以内的加减乘除</strong>,超过一位的人脑不能直接计算,我们就需要用纸笔记录下来进行计算。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">纸笔计算的方法很简单,就是一位一位地计算,用每一位数字依次去计算乘法,最后再移位相加起来就得到结果了。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">比如在上图的第一个例子当中,我们要计算15 * 16,我们先计算6 * 15的结果,再计算1 * 15,最后将两个结果错位相加,就得到了答案。我们要错位的原因也很简单,因为我们在计算15 * 1的时候,其实背后代表的是15 * 10。我们继续拆分问题,当我们计算6和15相乘的时候,又是怎么计算的呢?顺着这个思路,整个过程可以进一步被划分成先计算6和5相乘,再计算6和1相乘。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">最后,我们把两个较大数字的相乘拆分成了在每一位上的数字相乘。到了这里,剩下的就简单了,也就是说我们可以<strong style="font-weight: bold; color: rgb(71, 193, 168);">把这两个很大的数字用两个数组来存储</strong>,数组当中的每一位存储数字上的一位。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">比如我们要计算123 * 224, 我们的第一个数组是[1, 2, 3],我们的第二个数组是[2, 2, 4]。我们仿照乘法竖式中的方法计算这两个数组当中两两的乘积,并将它们拼装成答案。</p> <pre class="custom" data-tool="mdnice编辑器" style="margin-top: 10px; margin-bottom: 10px;"><code class="hljs" style="overflow-x: auto; padding: 16px; color: #333; background: #f8f8f8; display: -webkit-box; font-family: Operator Mono, Consolas, Monaco, Menlo, monospace; border-radius: 0px; font-size: 12px; -webkit-overflow-scrolling: touch;"> <span class="hljs-number" style="color: #008080; line-height: 26px;">1</span> <span class="hljs-number" style="color: #008080; line-height: 26px;">2</span> <span class="hljs-number" style="color: #008080; line-height: 26px;">3</span><br> * <span class="hljs-number" style="color: #008080; line-height: 26px;">2</span> <span class="hljs-number" style="color: #008080; line-height: 26px;">2</span> <span class="hljs-number" style="color: #008080; line-height: 26px;">4</span><br> ____________<br> <span class="hljs-number" style="color: #008080; line-height: 26px;">4</span> <span class="hljs-number" style="color: #008080; line-height: 26px;">9</span> <span class="hljs-number" style="color: #008080; line-height: 26px;">2</span><br> <span class="hljs-number" style="color: #008080; line-height: 26px;">2</span> <span class="hljs-number" style="color: #008080; line-height: 26px;">4</span> <span class="hljs-number" style="color: #008080; line-height: 26px;">6</span><br> <span class="hljs-number" style="color: #008080; line-height: 26px;">2</span> <span class="hljs-number" style="color: #008080; line-height: 26px;">4</span> <span class="hljs-number" style="color: #008080; line-height: 26px;">6</span><br> ____________<br> <span class="hljs-number" style="color: #008080; line-height: 26px;">2</span> <span class="hljs-number" style="color: #008080; line-height: 26px;">7</span> <span class="hljs-number" style="color: #008080; line-height: 26px;">5</span> <span class="hljs-number" style="color: #008080; line-height: 26px;">5</span> <span class="hljs-number" style="color: #008080; line-height: 26px;">2</span><br></code></pre> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">同样我们用数组来存储中间和最后的结果,最后的结果就是:[2, 7, 5, 5, 2]。由于题目需要我们要返回的是<strong style="font-weight: bold; color: rgb(71, 193, 168);">字符串</strong>,所以我们还需要将数组里的内容再拼接成字符串。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">这种<strong style="font-weight: bold; color: rgb(71, 193, 168);">用数组来模拟数字进行加减乘除运算的方法</strong>就叫做高精度算法,相信大家也都看到了,严格说起来这并不是一个算法,而只是一种思想。今天的题目出的是乘法,我们利用同样的方法也可以计算加减和除法。其中加减法非常简单,而除法则要复杂得多,也是高精度当中最难实现的部分。这里我们不做过多的拓展,计算的方法同样是打竖式,感兴趣的同学可以自行实现。</p> <h2 data-tool="mdnice编辑器" style="font-weight: bold; font-size: 22px; border-bottom: 2px solid rgb(89,89,89); margin-bottom: 50px; margin-top: 100px; color: rgb(89,89,89);"><span class="prefix" style="font-size: 22px; border-bottom: 2px solid rgb(89,89,89); display: none;"></span><span class="content" style="font-size: 22px; display: inline-block; border-bottom: 2px solid rgb(89,89,89);">进位和前导零</span><span class="suffix" style="font-size: 22px; display: inline-block; border-bottom: 2px solid rgb(89,89,89);"></span></h2> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">当我们理清楚了打竖式的方法之后,我们还要面临<strong style="font-weight: bold; color: rgb(71, 193, 168);">进位和前导零</strong>的问题。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">进位应该很容易理解,我们需要在计算乘法的时候判断当前位置的元素是否大于等于10,如果超过10的话,我们则需要进行进位。我们只需要将它除以10,得到的结果就是我们需要进位的值。除此之外就是<strong style="font-weight: bold; color: rgb(71, 193, 168);">前导零</strong>的问题,我们都知道除了零以外的合法数字是不允许首位出现0的,但是由于我们计算的是乘法,所以当其中某一个数为0会得到整体的结果为0,但是表示在数组当中则是多个0.</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">举个简单的例子,比如123 * 0,最后得到的应该是0,但是由于我们用数组表示了乘法运算当中的每一位,并且还进行了加法计算,所以会导致出现000的结果。这种情况我们要做特殊的处理,不过这也不复杂。最后我们把上面所有的思路都整理一下,就可以得到结果了。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">我们来看下代码:</p> <pre class="custom" data-tool="mdnice编辑器" style="margin-top: 10px; margin-bottom: 10px;"><code class="hljs" style="overflow-x: auto; padding: 16px; color: #333; background: #f8f8f8; display: -webkit-box; font-family: Operator Mono, Consolas, Monaco, Menlo, monospace; border-radius: 0px; font-size: 12px; -webkit-overflow-scrolling: touch;"><span class="hljs-class" style="line-height: 26px;"><span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">class</span> <span class="hljs-title" style="color: #458; font-weight: bold; line-height: 26px;">Solution</span>:</span><br> <br> <span class="hljs-function" style="line-height: 26px;"><span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">def</span> <span class="hljs-title" style="color: #900; font-weight: bold; line-height: 26px;">multiply</span><span class="hljs-params" style="line-height: 26px;">(self, num1: str, num2: str)</span> -&gt; str:</span><br> <span class="hljs-comment" style="color: #998; font-style: italic; line-height: 26px;"># 将字符串转化成数组</span><br> <span class="hljs-comment" style="color: #998; font-style: italic; line-height: 26px;"># 翻转数组,因为我们用第0位表示个位</span><br> arr1 = [ord(i) - ord(<span class="hljs-string" style="color: #d14; line-height: 26px;">'0'</span>) <span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">for</span> i <span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">in</span> num1][:: <span class="hljs-number" style="color: #008080; line-height: 26px;">-1</span>] <br> arr2 = [ord(i) - ord(<span class="hljs-string" style="color: #d14; line-height: 26px;">'0'</span>) <span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">for</span> i <span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">in</span> num2][:: <span class="hljs-number" style="color: #008080; line-height: 26px;">-1</span>]<br> <br> <span class="hljs-comment" style="color: #998; font-style: italic; line-height: 26px;"># 创建结果数组,可以证明结果的长度最多是n + m</span><br> n, m = len(arr1), len(arr2)<br> ret = [<span class="hljs-number" style="color: #008080; line-height: 26px;">0</span> <span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">for</span> i <span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">in</span> range(n + m + <span class="hljs-number" style="color: #008080; line-height: 26px;">1</span>)]<br> <br> <span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">for</span> i <span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">in</span> range(n):<br> <span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">for</span> j <span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">in</span> range(m):<br> <span class="hljs-comment" style="color: #998; font-style: italic; line-height: 26px;"># 按位相乘,计算进位</span><br> ret[i + j] += arr1[i] * arr2[j]<br> <span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">if</span> ret[i+j] &gt;= <span class="hljs-number" style="color: #008080; line-height: 26px;">10</span>:<br> ret[i+j+<span class="hljs-number" style="color: #008080; line-height: 26px;">1</span>] += ret[i+j] // <span class="hljs-number" style="color: #008080; line-height: 26px;">10</span><br> ret[i+j] %= <span class="hljs-number" style="color: #008080; line-height: 26px;">10</span><br> <br> <span class="hljs-comment" style="color: #998; font-style: italic; line-height: 26px;"># 最后把数组再转化成字符串返回</span><br> <span class="hljs-comment" style="color: #998; font-style: italic; line-height: 26px;"># 去除前导零</span><br> result = <span class="hljs-string" style="color: #d14; line-height: 26px;">''</span>.join(map(str, ret))[::<span class="hljs-number" style="color: #008080; line-height: 26px;">-1</span>].lstrip(<span class="hljs-string" style="color: #d14; line-height: 26px;">'0'</span>)<br> <span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">return</span> result <span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">if</span> len(result) &gt; <span class="hljs-number" style="color: #008080; line-height: 26px;">0</span> <span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">else</span> <span class="hljs-string" style="color: #d14; line-height: 26px;">'0'</span><br></code></pre> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">今天的题只是<strong style="font-weight: bold; color: rgb(71, 193, 168);">Medium</strong>难度,并不算困难,会选这题的原因主要是为了高精度算法。高精度算法本身并不难,也并不常用即使是在算法比赛当中也不常见。但是它给了我们一个思路,当我们要计算的数值超过计算机目前承载能力的时候,我们还有什么方法?</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">当然这题我们也可以取巧,因为Python当中内置了大整数,当它检测到我们的计算结果超过范围的时候,会自动转化成大整数来进行计算。所以这题如果我们使用Python,可以只用几行代码搞定:</p> <pre class="custom" data-tool="mdnice编辑器" style="margin-top: 10px; margin-bottom: 10px;"><code class="hljs" style="overflow-x: auto; padding: 16px; color: #333; background: #f8f8f8; display: -webkit-box; font-family: Operator Mono, Consolas, Monaco, Menlo, monospace; border-radius: 0px; font-size: 12px; -webkit-overflow-scrolling: touch;"><span class="hljs-class" style="line-height: 26px;"><span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">class</span> <span class="hljs-title" style="color: #458; font-weight: bold; line-height: 26px;">Solution</span>:</span><br> <span class="hljs-function" style="line-height: 26px;"><span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">def</span> <span class="hljs-title" style="color: #900; font-weight: bold; line-height: 26px;">multiply</span><span class="hljs-params" style="line-height: 26px;">(self, num1: str, num2: str)</span> -&gt; str:</span><br> num1 = int(num1)<br> num2 = int(num2)<br> <span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">return</span> str(num1 * num2)<br></code></pre> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">今天关于高精度算法的内容就到这里,如果觉得有所收获,请顺手点个<strong style="font-weight: bold; color: rgb(71, 193, 168);">关注或者转发</strong>吧,你们的举手之劳对我来说很重要。</p> </section>

原文出处:https://www.cnblogs.com/techflow/p/12544184.html

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部