118. Pascal’s Triangle帕斯卡(杨辉)三角形Python

给定一个非负整数numRows，生成Pascal三角形。

Input：4

Output：[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]]

Pascal triangle行和列都从0开始，比如6的位置是C(4,2)=4!/[2!(4-2)!]

C(n,k)=n*(n-1)*...*(n-k+1)/k!

Method.1 因为要用list输出，所以用yield存储每次的sublist，用zip[row,column]进行错位

class Solution:
    def triangles(self):
        subl=[1]
        while True:
            yield subl
            subl=[sum(i) for i in zip([0]+subl,subl+[0])]
    def generate1(self, numRows: int) -> List[List[int]]:
        l=[]
        n=0
        if numRows==0:
            return l[:]
        for t in self.triangles():
            l.append(t)
            n+=1
            if n==numRows:
                break
        return l[:]
'''Output subl=[sum(i) for i in zip([0]+subl,subl+[0])]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
'''

然后我发现太麻烦，太慢了=  =于是有了Method.2

def generate2(numRows: int):
    l = []
    for line in range(1, numRows + 1):
        a = 1
        subl= []
        for i in range(1, line + 1):
            subl.append(a)
            a = int(a * (line - i) / i)#不加int就会有**.0变成float，运用C(n,k)
        l.append(subl)
    return l

i：C(n,k)中的k

a：n的阶乘

line-i：n-k+1

但是以上两种方法都要理解杨辉三角排列组合，所以有了第三种不需要研究那么多的，比较直观的方法

Method.3 从三角形第三行i开始，除了第一位和最后一位，第j个数 j=(i-1, j-1)+(i-1, j)，先定义sublist=[1,1]然后将值插入进去。

def generate3(numRows: int):
    l=[[1],[1,1]]
    if numRows<=1:
        return l[:numRows]
    for i in range(2,numRows):
        subl=[1,1]
        while len(subl)<=i:
            j=len(subl)//2
            what = l[i - 1][j - 1] + l[i - 1][j]
            subl.insert(j,what)
        l.append(subl)
    return l
'''Test output:
i 2
len,j,what 3 1 2
i 3
len,j,what 3 1 3
len,j,what 4 1 3
i 4
len,j,what 3 1 4
len,j,what 4 1 4
len,j,what 5 2 6
i 5
len,j,what 3 1 5
len,j,what 4 1 5
len,j,what 5 2 10
len,j,what 6 2 10
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1]]
'''

Method.4 同和方法3类似，只是变成了初始化sublist里面的元素都变成1，然后再更改里面的数字

def generate4(numRows: int):
    l=[]
    for i in range(numRows):
        subl=[1 for _ in range(i+1)]
        for j in range(1,len(subl)-1):
            subl[j]=l[i-1][j-1]+l[i-1][j]
        l.append(subl)
    return l