每日Leetcode—算法（12）

118.杨辉三角

输入: 5
输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

算法一（自己写的）：

def generate(self, numRows: int) -> List[List[int]]:
    if numRows == 0:     #第0行为空
        return []
    if numRows == 1:
        return [[1]]        #返回第1行
    a = [[1],[1,1]]       #前两行
    for i in range(3,numRows+1):        #从第三行开始进行循环
        b = [1]              #每一行头一个数均为1
        for j in range(2,i):           #需要加入i-2个数字  
            b.append(a[i-2][j-2]+a[i-2][j-1])    #第i行的第一个数为上一行前两个数相加
        b.append(1)       #最后一个数仍为1
        a.append(b)      #将第i行加入数列
    return a 

分析：该算法的语句较多，不够简洁美观。

算法二

def generate(self, numRows: int) -> List[List[int]]:
    l = [[1]]
    for i in range(1,numRows):           #循环numRows-1次
        l.append(list(map(lambda x,y:x+y, [0]+r[-1], r[-1]+[0])))
    return l[:numRows]       #如果numRows为0，则返回[]

分析：该算法利用了杨辉三角下一行等于上一行错格相加的特性。
高手们都使用了lambda、map等函数进行编写，写出来的算法简洁美观。下面进行从map等基础函数开始介绍。

lambda函数

lambda是匿名函数，通常是在想用一个简单的函数，但是又不想def一个新函数的情况下使用，表达式为：
lambda 形参列表 : 函数返回值表达式语句

>>>f = lambda x,y: x+y
>>>f(1,2)
3

zip()函数

zip函数是Python的一个内建函数，可以接受一系列可迭代的对象作为参数，将对象打包成一个个元组（tuple），然后返回由元组组成的列表（list）。若传入参数的长度不等，则以最短长度的对象为最终list的长度。

>>> b = [4,5,6]
>>> c = [7,8,9]
>>> d = [4,5]
>>>list(zip(a,b))
[(4,7), (5,8), (6,9)]
>>>list(zip(a,b,c))
[(4,7,4),(5,8,5)]

利用*号操作符，可以将list unzip（解压），下面是将矩阵行列互换

>>> a = [[1,2,3],[4,5,6],[7,8,9]]
>>>list(map(list, zip(*a)))
[[1, 4, 7], [2, 5, 8], [3, 6, 9]]

map()函数

map(func,seq[,seq2…])
map函数将func用于seq中的每一个元素，并用一个列表将结果返回。如果func为空，则作用等同于zip()。

>>>list(map(lambda x:x%2), range(4)))
[0,1,0,1]
>>>list(map(lambda x,y:x+y), [1,2],[3,4]))
[4,6]
>>>list(map(lambda x,y: (x+y, x*y), [1,2,3],[4,5,6]))
[(5,4),(7,10),(9,18)]

reduce函数

reduce(func,seq[,init])
reduce()函数即为化简，前两个元素进行func，结果与下一个元素再次进行func。
reduce(func,[1,2,3]) = func(func(1,2),3)
其中init可选：如存在init，则init作为第一个元素。使用reduce函数需要从functool中调用。

>>>from functools import reduce
>>>reduce(lambda x,y:x+y, [1,2,3,4,5])  #阶乘
120
>>>reduce(lambda x,y:x+y, [1,2,3,4,5], 2)   #二倍阶乘
240

filter()函数

filter()函数用于过滤序列。函数接受一个func与数列，函数一次作用于元素，根据布尔返回值决定是否返回元素。True则返回，False则不返回。

>>>list(filter(lambda x:x%2 == 1, [1,2,3,4,5]))
[1,3,5]