我倒在了美团面试算法题：字符串大数相加

话说之前换工作的时候，我经历了一次美团的视频面试。

不像腾讯面试有自家软件，美团面试是在第三方网页上进行的，长这样：

看见中间的代码编辑区，我笑了，难道？真的？算法？

我的算法，有点差呀。而且没怎么刷过题。

默默祈祷不要考算法。

可就在我以为面试要结束的时候，该来的还是来了。

题目：

给定两个字符串形式的非负整数 num1 和 num2，计算它们的和。
注意，不能把 string 转换为 int 后直接相加。

面试官笑了，我也笑了，好，我写一下。

我隐约记得是模拟人工手算：

一位一位来加，有进位就在左边那位加个 1。

因为没有刷过题，只能按我自己的思路去写，越写越乱，最后还是没能写出来。

面完后，我不禁陷入了沉思。

测试需要学算法？部分需要。

哪些需要？大厂、高级职位、测试开发。

怎么练？刷题。

哪里刷？力扣。

本文就跟大家讲一下字符串大数相加的算法。希望在面试时被问到了，能自信的写出来。

对这个算法，首先要考虑的是，怎么来遍历这 2 个数，可以用 2 个指针，分别指向这 2 个数的尾部，边计算边向左移动。

数的长度可能会不一样，短的那个数的指针就会先到达最左边的头部，为了能够继续计算，可以给缺失的位补 0。

加数长度不一致的问题就解决了。

指针的数相加后，可以通过除以 10 的余数，来算出当前位的结果。

进位，则可以通过对 10 的整除数，来算。

例如：

指针指向的 2 个数是 5 和 6。

5 + 6 = 11，用 tmp 变量来存，tmp = n1 + n2 + carry，因为有可能右边有进位，需要加上。

11 对 10 的整除数是 1，用 carry 来存进位。

11 除以 10 的余数是 1，用 res 来存结果，需要在 res 最左边添加 “1”，把 “9084” 变为 “19084”。

最后分析代码：

class Solution:
    # 加法函数，入参num1和num2，返回计算结果，str类型
    def addStrings(self, num1: str, num2: str) -> str:
        res = ""
        # 定义i,j两个指针，分别指向两个数的尾部
        # 定义进位，默认0
        i, j, carry = len(num1) - 1, len(num2) - 1, 0
        # 循环，直到2个指针都到达头部
        while i >= 0 or j >= 0:
            # 如果没有到达头部，就通过-'0'转为int
            # 如果到达头部了，就补0
            n1 = num1[i] - '0' if i >= 0 else 0
            n2 = num2[j] - '0' if j >= 0 else 0
            # n1 + n2 + carry
            tmp = n1 + n2 + carry
            # 进位 = 对10的整除数
            carry = tmp // 10
            # 结果左边添加除以10的余数
            res = str(tmp % 10) + res
            # 每次计算后向左移动1位
            i, j = i - 1, j - 1
        # 2个指针都到达了头部，如果还有进位，就在res左边添加"1"
        # 否则直接返回res
        return "1" + res if carry else res

参考资料：力扣 415. 字符串相加

最后的最后，希望大家都能找到满意的工作，拿到超高的薪资。我也会继续向大厂努力。