【Leetcode 完整Python解答筆記】118. Pascal’s Triangle

先解釋題目,題目會提供一個數字,我們需要輸出對應的 Pascal 三角形。

如果還不知道甚麼是 Pascal 三角形的可以看下面的動態圖。

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 as shown:

Example 1:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1
Output: [[1]]

Constraints:

  • 1 <= numRows <= 30

Python 解答:

先來看大神的解答,精簡有力,這裡用了 map 函數形式,map(function, sequence)。

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        res = [[1]]
        for i in range(1, numRows):
            res += [list(map(lambda x, y: x+y, res[-1] + [0], [0] + res[-1]))]
        return res[:numRows]

如果不明白 map 是甚麼的可以看這裡:

對 sequence 中的 item 依次執行 function(item),並將結果組成一個 「迭代器」 返回。資料來源在這裡

如果不是很清楚,可以看以下例子。

輸入:

nums= [1,-2,-3]
ans = map(abs,nums) 
print(list(ans))

輸出 nums:

[1, 2, 3]

abs是內建函數,代表將數字取絕對值。

list(ans) 則是為了將迭代器轉回正常的列表,不可缺少。

那到這裡應該都知道 map 的基本用法。

接下來我們看看 map 在這道 leetcode 的用途。

首先,我想看看每一次的 res 的輸出結果。

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        res = [[1]]
        for i in range(1, numRows):
            res += [list(map(lambda x, y: x+y, res[-1] + [0], [0] + res[-1]))]
            print(res)
        return res

輸入 numRows = 5。

輸出結果:

[[1], [1, 1]]
[[1], [1, 1], [1, 2, 1]]
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]]
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

每次循環,map 都會加上一層,然後 list 再把迭代器轉回正常的列表。

接下來我們看看程式中 lambda 的作用。

先把 lambda 的部分單獨拿出來看。

lambda x, y: x+y, res[-1] + [0], [0] + res[-1]

在大神的解釋中,他清楚的舉了一個例子,如下:

    1 3 3 1 0 
 +  0 1 3 3 1
 =  1 4 6 4 1

這裡以第四層([1, 3, 3, 1]),要往第五層走為例。

簡單來說,就是在 res 的最後面加上 [0] ,然後和前面加上 [0] 的 res 相加。

也就是和前一個數字相加的其中一種寫法。

res[-1] + [0] [0] + res[-1] 分別代表了 x 和 y。

每次 x 和 y 的相加都會加到 list 裡頭。

看到這裡,是不是覺得大神的解答很精彩。

大神的解答在這裡,有興趣可以看一下。

Leave a Comment

Your email address will not be published. Required fields are marked *