Re: [閒聊] 每日LeetCode
119. Pascal's Triangle II
https://leetcode.com/problems/pascals-triangle-ii/
給定一個整數rowIndex，
以串列形式返回帕斯卡三角形的第rowIndex層（最上層為第0層）。
久違的簡單題，
帕斯卡三角形的第n層的第k個元素的值為Cn取k，
公式為n!/(k!*(n-k)!)，
但反覆計算階乘很花時間，
於是可以先用串列儲存各階乘再套公式輸出值。
程式碼如下：
Python code:
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
f = [1] * (rowIndex+1)
for i in range(1,rowIndex+1): f[i] = f[i-1] * i
ans = [1] * (rowIndex+1)
for i in range(rowIndex+1):
ans[i] = f[rowIndex]//(f[i]*f[rowIndex-i])
return ans
題目還有問能否讓空間複雜度為O(rowIndex)，
想問各位有沒有想法
--
咖啡是一種豆漿，
茶是一種蔬菜湯。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 112.78.72.56 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1697454663.A.EF6.html
※ 編輯: leafff (112.78.72.56 臺灣), 10/16/2023 19:12:19
推
10/16 19:48,
7月前
, 1F
10/16 19:48, 1F
討論串 (同標題文章)