[承志的算法课堂]一道题让你学会高精度算法，LeetCode43 今天是LeetCode系列第22篇文章

今天是LeetCode系列第22篇文章，今天讲的内容是高精度算法。
今天和大家讨论的算法是高精度，对应的LeetCode是第43题。题面其实没什么好说的，以字符串的形式给定两个数字，要求返回这两个数字的乘积。之所以是以字符串的形式给数字是因为这个数字可能会非常大，题目当中给定的范围是110位的数字。对于Python来说这不是问题，但是对于C++和Java等语言来说这么大的数字是无法以int类型存储的，所以必须要使用字符串来接收。
如果你使用Python ，你可以不用任何算法就AC这题，但是这没有任何意义。那么正确的方法应该怎么做呢？
高精度与打竖式这就需要我们的高精度算法出场了，其实严格说起来高精度并不是一种算法，而是一种思想。这个思想非常朴素，我敢保证我们每一个人都学过。还记得小学的时候，我们计算多位数的乘法是怎么算的吗？大家应该都不陌生才对，就是打竖式， likethis：

文章图片
我们人类要打竖式是因为我们只能计算一位数以内的加减乘除，超过一位的人脑不能直接计算，我们就需要用纸笔记录下来进行计算。
纸笔计算的方法很简单，就是一位一位地计算，用每一位数字依次去计算乘法，最后再移位相加起来就得到结果了。
比如在上图的第一个例子当中，我们要计算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的结果。这种情况我们要做特殊的处理，不过这也不复杂。最后我们把上面所有的思路都整理一下，就可以得到结果了。