415. 求两数之和

发表于 分类于 阅读次数： 本文字数： 971 阅读时长 ≈ 4 分钟

这个题目其实可以说是很多算法比赛训练的入门题目了，我一早就知道。

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。

提示：

num1 和num2 的长度都小于 5100

num1 和num2 都只包含数字 0-9

num1 和num2 都不包含任何前导零

你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式

415. 求两数之和 <– 传送门

甚至我们公司也有出过这个题目作为笔试题，但是，昨天我自己做了一遍，发现做得非常差，虽然还是做出来了，但是，写得极其啰嗦。我列在下面：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        l1 = len(num1)
        l2 = len(num2)
        if l1 > l2 :
            num1, num2 = num2, num1
            l1, l2 = l2 , l1
        shift = 0
        newstr = ''
        i = l1
        while i > 0:
            lowbit1 = ord(num1[l1 - (l1 - i + 1)]) - 48
            lowbit2 = ord(num2[l2 - (l1 - i + 1)]) - 48
            lowbit3 = lowbit1 + lowbit2 + shift
            if lowbit3 > 9:
                lowbit3 = lowbit3 - 10
                shift = 1
            else:
                shift = 0
            newstr = str(lowbit3) + newstr
            i = i - 1
        left = l2 - l1
        if left > 0:
            j = left
            while j > 0:
                lowbit1 = ord(num2[j - 1]) - 48
                lowbit2 = lowbit1 + shift
                if lowbit2 > 9:
                    lowbit2 = lowbit2 - 10
                    shift = 1
                else:
                    shift = 0
                newstr =  str(lowbit2) + newstr
                j = j - 1
        if shift == 1:
            newstr = str(shift) + newstr
        return newstr

这真是太糟糕了…… 做完题目我发现，一年前我就做过这个题目，那时候是用 go 语言写的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import "strconv"

func addStrings(num1 string, num2 string) string {
    i := len(num1) - 1
    j := len(num2) - 1
    c := 0
    result := ""
    for i >= 0 && j >= 0 {
        sum := int(num1[i]) - 48 + int(num2[j]) - 48 + c
        if sum < 10 {
            c = 0
            result = strconv.Itoa(sum) + result
        } else {
            c = 1
            result = strconv.Itoa(sum % 10) + result
        }
        i --
        j --
    }
    
    for i >= 0 {
        sum := int(num1[i]) - 48 + c
        if sum < 10 {
            c = 0
            result = strconv.Itoa(sum) + result
        } else {
            c = 1
            result = strconv.Itoa(sum % 10) + result
        }
        i --
    }
    
    for j >= 0 {
        sum := int(num2[j]) - 48 + c
        if sum < 10 {
            c = 0
            result = strconv.Itoa(sum) + result
        } else {
            c = 1
            result = strconv.Itoa(sum % 10) + result
        }
        j --
    }
    
    if c > 0 {
        result = "1" + result
    }
    
    return result
}

也够糟糕的，但是我看了一下，同时用了两个指针做第一遍遍历，那就比这次还好一点，可见，编码能力是退化了的。

这道题目虽然直觉上非常简单，无非就是笔算加法的代码表达，如果真的这么去写，恐怕就会写成我那个样子。还是需要有一点数据结构和算法的知识。

这道题里，数据结构是字符串，字符串的本质是一个字符的数组。所以，这道题的数据结构就是数组。然后我们计算加法，是从个位加到十位百位的，对应字符串数组，是从数组的最后一个元素，向数组的第一个元素遍历，是一个逆序遍历数组的问题，只不过要同时遍历两个，还要处理边界条件。

不管用什么语言，这里还有一个字符串 string，字符 char，整数 int 三者之间的转换方法之类的问题。属于一门语言的基础知识，所以这道题要顺顺利利快速做出来，其实要求是很高的。没点积累搞不定，忘记了基础也搞不定。

然后我又写了一遍：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        i = len(num1) - 1
        j = len(num2) - 1
        result = ""
        carry = 0
        while i >= 0 and j >= 0:
            add = int(num1[i]) + int(num2[j]) + carry
            carry = add // 10
            add = add % 10
            result = str(add) + result
            i = i - 1
            j = j - 1
        if i >= 0:
            while i >= 0:
                add = int(num1[i]) + carry
                carry = add // 10
                add = add % 10
                result = str(add) + result
                i = i - 1
        if j >= 0:
            while j >= 0:
                add = int(num2[j]) + carry
                carry = add // 10
                add = add % 10
                result = str(add) + result
                j = j - 1
        if carry > 0:
            result = "1" + result
        return result

差不多这水平吧，比第一段好多了，这里首先选用了整数除法作为计算进位的方法，而不是像第一段里写的那样，用大于 10 做判断，用了取模来取单个数位求和的个位，这是一个数学小知识，而不是用减 10，我第一段不是故意写那么烂的，是真的就那么烂忘记这些事情了。用整除法和取模，计算的效率未必高，因为是除法和移位之类的，比起用 if 哪个效率高不好说，但是一个很大的好处是，写法非常统一。然后，我又写错了 N 次的边界，终于对了。

这时候，就发现，代码重复得很厉害。然后我把重复得代码合并了一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        i = len(num1) - 1
        j = len(num2) - 1
        result = ""
        carry = 0
        add = 0
        while i >= 0 or j >= 0:
            if i >= 0:
                add = add + int(num1[i])
                i = i - 1
            if j >= 0:
                add = add + int(num2[j])
                j = j - 1
            add = add + carry
            carry = add // 10
            add = add % 10
            result = str(add) + result
            add = 0

        if carry > 0:
            result = "1" + result
        return result

变成了这样，就短了很多了，算法得效率没变。只是写起来简洁多了。然后仔细观察一下，发现，add 变量和 carry 变量是可以合并的，去掉一个：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        i = len(num1) - 1
        j = len(num2) - 1
        result = ""
        carry = 0
        while i >= 0 or j >= 0:
            if i >= 0:
                carry += int(num1[i])
                i = i - 1
            if j >= 0:
                carry +=  int(num2[j])
                j = j - 1
            result = str(carry % 10) + result
            carry //= 10
        if carry > 0:
            result = "1" + result
        return result

到这里，应该已经是我的极限了，当然，可以利用一些语法糖，写得再短一点，我觉得那就纯粹是炫技了，说明作者对语法糖的熟练，也是好的，不过从代码运行角度看，没什么区别，从可读性上看，哪个好还不一定。

这个题目里复习了哪些知识呢？

  1. Python 字符串、字符转换成整数 int() 函数，转换成字符串 str() 函数；
  2. Python 整除的写法是 // 如果用一个 / 回得到 浮点数；
  3. 两个线性数据结构的同时遍历，可以用两个指针（下标）一起遍历；