leetcode with python:118. Pascal's Triangle

题目:

Given an integer numRows, return the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it.

给定一数n,以list型态回传帕斯卡三角形的前n列
ex:input:5=>output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

帕斯卡三角形,是如图这般由数字构成的三角形

可以发现除第一二列外
其他列都是由上一列每一项与其下一项相加的结果,两侧再加上1
也就是说,只要知道该列前一列,就能推断出该列

知道规则后,我们就可以开始实作了

class Solution:    def generate(self, numRows: int) -> List[List[int]]:        if numRows==1: #若只要求一列就回传一列的结果            return [[1]]                    ans=[[1],[1,1]] #定下起始两项                for i in range(2,numRows):            temp=[1]            for j in range(len(ans[-1])-1):                temp.append(ans[-1][j]+ans[-1][j+1])            temp.append(1)            ans.append(temp)        return ans

如上面所说,用当前最后一列(ans[-1])就能推断出新的一列
因此我们推断出新列时将其append到我们要回传的阵列(将其变为ans[-1])
然后再用此阵列用同样手法製造出下一列
如此循环直到做出前numRows列便可回传
最后执行时间29ms(faster than 95.93%)

那我们下题见