題目:

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%)

那我們下題見