題目

解題概念

  • 此題簡單來說，就是經典的 Pascal’s Triangle (帕斯卡三角形)
  • 此題型其實有公式解可以套用 : 第 $n$ 行的第 $k$ 個數字為 $\mathrm{ C }^{n-1}_{k-1}$
  • 但在實際執行上，我使用遞迴的方式去解 :
    1. 起始陣列為 [1]
    2. 接著每回合建構一個新陣列 temp :
      1. 設定temp第一個 & 最後一個元素為1
      2. 將前一回合之陣列arr的相鄰元素相加，並放入temp中

實際寫Code

  • 目標函式 : generate(numRows)
    • Input : numRows: int
    • Output : List[List[int]]
  • 前置作業 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    # 起始陣列為[1]，並放入result中
    result = []
    result.append([1])

    numRows -= 1 # 因為我們已完成第一回合，故 numRows 需減 1

    # 主要遞迴式
    def Recursion(arr):
        # ...
        
    while numRows != 0: # 若回合尚未歸零

        # 取出前一回合之結果，並將其丟入遞迴函數中
        length = len(result)
        Recursion(result[length - 1])

        # 回合數減 1
        numRows -= 1
        
    return result
  • 主要遞迴部分 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    # arr 為前一回合之結果陣列
    def Recursion(arr):

        # temp為這回合之目標陣列，且第一個元素為 1
        temp = [1]

        # 將 arr 的元素兩兩相加，並丟入 temp 中
        for i in range(len(arr)-1):
            temp.append(arr[i]+arr[i+1])

        # temp 的最後一個元素也為 1
        temp.append(1)

        # 將 temp 加入 result 中
        result.append(temp)