Re: [閒聊] 每日LeetCode

[leafff (leaf)]

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
推 sustainer123: 大師