杨辉三角蕴含的编程哲学

Published On 十二月 07, 2017

category algorithm | tags combination interview


这是一道非常妙的面试题,并没有涉及到动态规划等比较复杂的算法,但是通过手写代码却可以区分出面试者的水平,尤其是在工作中编程的素养。应届生往往会认为这是一道送分题,不假思索的给出答案,结果却漏洞百出;水平一般的程序员则会考虑到一些边界情况的处理,从而保证功能的正确性;而久经沙场的程序员,不仅知道哪里需要优化,还会考虑到程序在线上环境运行的健壮性。

源码地址

问题

我们从小学就接触过的杨辉三角,在国外被称为帕斯卡三角形(Pascal's triangle),前9行写出来如下:

        1
       1 1
      1 2 1
     1 3 3 1
    1 4 6 4 1
   1 5 10 10 5 1
  1 6 15 20 15 6 1
 1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
可以这样定义杨辉三角:

  1. 第n行的数字个数为n个
  2. 除每行最左边与最右边的数字为1以外,每个数字等于它的左上方与右上方两个数字之和(也就是说,第n行第k个数字等于第n-1行的第k-1个数字与第k个数字的和)

问题是这样的: 实现一个接口给线上用,求第n行第k个数字。函数的签名如下:

def solve(n, k):
    pass

解(python实现)

递归实现

根据定义很容易使用递归来实现,并且递归版本的代码一如既往的简洁:

pt_recursive.py:50分

def solve(n, k):
    if k==1 or k==n:
        return 1
    return solve(n-1, k-1) + solve(n-1, k)
然而,求第n行第k个数字时,它上面的某些数字会被重复计算很多遍,性能极低。另一方面,递归代码的调用栈过长,函数调用开销大,并且很容易超出最大递归层数的限制。

迭代实现

pt_iteration1.py:50分

把上面的代码用迭代改写:

def solve(n, k):
    L = [[]]
    for i in range(1, n+1):
        l = [None]
        for j in range(1, i+1):
            if j==1 or j==i:
                v = 1
            else:
                v = L[i-1][j-1] + L[i-1][j]
            if i==n and j==k:
                return v
            l.append(v)
        L.append(l)
该答案从第一个数字开始遍历到目标为止,没有重复计算,但是内存占用很高,所以需要优化空间,完全没有必要保留前面遍历过的所有数字。

pt_iteration2.py:60分

遍历的时候只需要保留上一行的数字,代码如下:

def solve(n, k):
    for i in range(1, n+1):
        l = [None]
        for j in range(1, i+1):
            if j==1 or j==i:
                v = 1
            else:
                v = ll[j-1] + ll[j]
            l.append(v)
        ll = l # keep last line
    return ll[k]
内存问题解决了,但还是不够高效,时间复杂度是N平方。

pt_iteration3.py:65分

借助python的列表生成器,上面的解法可以写的非常优雅,然而对于性能却毫无帮助:

# add 0 in 2 sides
def triangles1():
    l = [1]
    while True:
        yield l
        l.append(0)
        l = [l[i-1] + l[i] for i in range(len(l))]

# zip
def triangles2():
    l = [1]
    while True:
        yield l
        l = [sum(t) for t in zip([0]+l, l+[0])]

def solve(n, k):
    for l in triangles1():
        n -= 1
        if n==0:
            return l[k-1]
如果需要输出/打印整个杨辉三角,那么最优解是pt_iteration3。

组合数

杨辉三角有很多规律,其中有一条对于解答本题很关键:

第n行的第k个数字恰好为组合数(n-1)C(k-1)

通过直接计算组合数就可以避免遍历所有的数字,时间复杂度将为N。

pt_combination1.py:70分

该问题转化为计算组合数:\[C_{n}^k = \frac{n!}{k!(n-k)!}\] 该公式可以从排列数推导出来。

import operator

def fac(n):
    if n == 0:
        return 1 # 0! = 1
    return reduce(operator.mul, range(1,n+1))

def c(n, k):
    return fac(n)/(fac(k)*fac(n-k))

def solve(n, k):
    return c(n-1, k-1)
代码足够精简了,但是计算阶乘的时候有大量重复的计算,还可以优化。

pt_combination2.py:80分

因为\[\frac{n!}{k!(n-k)!} = \frac{n(n-1)...(n-k+1)}{k(k-1)...1}\]

import operator

def c(n,k):
    if k == 0:
        return 1
    return reduce(operator.mul, range(n-k+1, n+1))/reduce(operator.mul, range(1, k+1))

def solve(n, k):
    return c(n-1, k-1)
k == 0时,range返回空列表,reduce报错,所以必须特殊处理。

pt_combination3.py:90分

如果传入的参数是(1000, 1000),那么上面的方法需要计算两遍999的阶乘,而计算阶乘是比较耗时的,考虑到这种特殊情况,当n == k时,直接返回1,代码如下:

import operator

def c(n,k):
    if k == 0:
        return 1
    if n == k:
        return 1
    return reduce(operator.mul, range(n-k+1, n+1))/reduce(operator.mul, range(1, k+1))

def solve(n, k):
    return c(n-1, k-1)

满分答案

到目前为止,我们的代码很优雅也很高效,但我们忘了题目的要求——要给“线上使用”。在线上环境我们不能保证传入的参数是合法的,比如k比n大,比如n超过了上限,导致溢出或者超出计算能力,因此需要对参数的类型、范围等进行校验。这里为了简单处理,对于不合法的参数返回None,线上的话最好有日志和错误信息,方便排错,提到这一点就是加分项。

pt_final.py:100分

import operator

def c(n,k):
    if k == 0:
        return 1
    if n == k:
        return 1
    return reduce(operator.mul, range(n-k+1, n+1))/reduce(operator.mul, range(1, k+1))

def check(n, k):
    for a in (n, k):
        if type(a) is not int:
            return False
        if not (a >= 1 and a <= 30000):
            return False
    if k > n:
        return False
    return True

def solve(n, k):
    if not check(n, k):
        return None
    return c(n-1, k-1)
虽然python中的int没有上限,但是当n足够大时(一般是异常情况),会导致服务被占用,因此有必要限制最大值。

总结

希望读者可以体会到以下几点编程的哲学:

  1. 在学校和公司编程的差别在于,学校只要求输出正确的结果,而公司还注重优化性能和在线上环境的健壮性;
  2. 如果说算法是程序的灵魂,那么数学就是计算机的灵魂,很多复杂的编程问题都可以借助于数学的手段化简为繁;
  3. 解决一个问题有很多方法,然而最优解只有一个;

qq email facebook github
© 2018 - 晏旭瑞. All rights reserved
Built using pelican