LeetCode 415. 字符串相加 和 43. 字符串相乘

这两个题目是关于string类的相关使用的练习题。同时，这也是关于大数运算的题目，让我们来分析一下吧！

字符串相加

难度 简单OJ链接

我们以示例2来讲解这题思路：

首先，我们用两个下标指向两个字符串最后的位置。然后让这两个数相加6+7=13，所以这里我们要进1。

然后将3头插到一个新的字符串里。然后下标往前移一位。

5+7=12，12还要加进位上的数12+1=13，13那么还要进位，进位还是1。我们把3头插到新的字符串里，然后下标再往前移一位。

此时，有一个字符串结束了。但此时还不能结束，我们把剩下的位置都看作0。也就是4+0+1(进位)=5。5是小于10的不需要进位，我们就把进位改为0。然后我们把5再头插到新字符串里。

此时两个字符串的数都结束了，才是真正的结束。

那么，我们再看这道题的写法：

首先，我们要把进位设为0，因为一开始两个数相加没有进位。这里，为什么会用三目操作符呢？原因是：可能有一个字符串先结束，如果结束了，我们还去取那里的位置就会出现越界了。所以如果有一个先结束，我们就直接给0。还有这里我们减了一个字符0，如果我们没有减字符0，那么我们取的是字符数字。像’1’的ASCII值为49，而我们需要的数字就是1，所以要减去一个字符0。

如果相加的数大于9，那么我们就把进位设为1，没有的话就改为0。

然后我们再把每一个字符头插进去。此时我们也需要把字符0加上才行。

但此时还有一点问题：就是如果’9’+'1’这个字符串，按照上面的写法9+1=10，是大于9的，然后减10，ret=0，carry=1。把字符0插入字符串里，然后end1–，end2–，循环就结束。此时字符串里只有一个0，没有1。所以我们还要再判断一下。

但是每次的头插它的时间复杂度是O(N^2)，所以时间上会很慢。我们可以这样去写：

我们直接尾插，当所有的数尾插完了。我们再把全部给翻转过来。这样的时间复杂度为O(N)。

字符串相乘

难度 简单OJ链接

思路流程：
我们以下面的数据为例：

根据我们小学时学习的乘法。47=28，我们要把8留下，然后进2。但是在这里，我们先不进位。而是把28保留下来。后面37=21也不进位把它保留下来。所有的计算都不进位。

然后，我们把每一列的数全加起来。

此时，我们再从后往前，一位一位的开始进位。

下面就开始一步一步来实现：
第一步：如果这两个字符串当中有一个字符串为空字符串，则直接返回空字符串。

第二步：开辟一个数组，把每次的数据累计到数组中。

这里我们先计算了两个字符串的长度m，n。而这个数组该开多大呢？举个例子：100100=10000，两个三位数相乘，最小的是5位数。999999=998001，两个三位数相乘，最大的是6位数。所以，我们就开辟m+n个空间就足以放下。因为最小是m+n-1，最大是m+n，然后我们再把里面的空间初始化0。

第三步：两个字符串的数字从后往前每一位相乘，然后累加到数组里。

这里可能有的同学不知道为什么是i+j+1？

这是两个字符串的下标位置。

这是数组里数据的下标位置显示。我们看到4 * 7=28，28在数组下标为6的地方，此时的i为3，j为2，所以2+3+1=6。像3*7=21，在数组下标为5的地方，此时i为2，j为2，所以2+2+1=5。其它的也是一样的道理。

第四步：将数组里的数据开始每一位进位。

第五步：将数组里的数据从头开始尾插到新字符串中。

可能有的同学不知道这是什么意思？这是判断数组开头有没有数据。如果开头是0，说明没有进位进到开头处。我们只需从数组下标为1的地方开始尾插。如果不是0，说明有进位进到开头处，我们需要从数组下标为0的地方开始尾插。

好了，这两道题我们以讲解完毕。如果大家觉得有帮助，可以点赞收藏一下。谢谢大家！！！