項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 search-input 尚未註冊或是沒有一個 view.php 檔案.

【Leetcode】python – [118] Pascal’s Triangle 個人解法筆記 (內含範例程式碼) 內含 sum of two list (list add 相加方法整理)

題目出處

118. Pascal’s Triangle

難度

easy

題目分類

array

個人範例程式碼

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        ans = [[1]]
        if numRows == 0:
            return [[]]
        else:
            layer = 1 # start from layer 2
            while layer < numRows:
                this_layer = self.generate_layer(ans[len(ans)-1]) 
                ans.append(this_layer)
                layer+=1

            return ans

    def generate_layer(self, last_layer):
        this_layer = []
        for idx, ele in enumerate(last_layer):
            if idx == 0:
                this_layer.append(1)
            else:
                this_layer.append(last_layer[idx-1]+last_layer[idx])
        this_layer.append(1)

        return this_layer

Time Complexity

O(n^2)

Space Complexity

O(n^2) = 剛好題目要求

算法說明

這題很直覺,我是直接用類似「dp(n) = dp(n-1) + k」的方式做出來的,
因為「上一層」與「下一層」有強烈的相關性。

算法簡單來說是:

先產生下層的第一位數字 1,
第二位開始,都是由上一層的 n-1, n 組成
最後補上一個 1

圖示如下

  1. 先產生 1
1 3 3 1
1
  1. 上一層 1+3, 3+3, 3+1 填入
1 3 3 1
1 4 6 4
  1. 補上最後一個1
1 3 3 1
1 4 6 4 1

corner case 特殊情況處理

雖然題目有說到 「1 <= numRows <= 30」,
但我把 0, 1 的情形都考慮了進去

Boundary conditions/ Edge conditions 邊際情況處理

傳入上層 layer 時,我是以目前 ans 的 len 大小判斷,
上一層 layer 的「index 位置」會是 「目前 len(ans) – 1」,
而不是「目前 len(ans) – 2」,因為目前這層尚未新增。

特殊酷解法

這是我在 leetcode 討論區看到的很酷的解法,
這邊紀錄一下

連結:

大概念就是,下一層的 layer 可以視為「上層補 0 與 此反轉的總和」,
文字敘述太難懂了,不如我們直接看圖示。

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

一看圖示就懂了,真的太強了這個 Orz!!!

可以寫出來的程式碼也很簡潔:
(這邊保留註解的部分是留給我自己看的,下面會說明,實際上 2, 3 選一種即可)

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        ans = [[1]]
        for _ in range(numRows - 1): # we already have layer 1, do "numRows-1" times.
            tmp = ans[-1] + [0]
            # this_layer = tmp + tmp[::-1] # wrong! will be 1,0,0,1 
            # print(this_layer)

            this_layer2 = [x + y for x, y in zip(tmp, tmp[::-1])] # add reverse
            # print(this_layer2)

            # this_layer3 = list(map(lambda x, y: x+y, tmp, tmp[::-1])) # add reverse
            # print(this_layer3)           
            ans.append(this_layer2)

        return ans

這裡我們會碰到一個陷阱與問題,
就是 python 的 list 該如何相加?

注意:python 裡面 list 的「+」,是相當於「把內容往後堆」,
而非「兩者相加」。

python list add 加法 (sum of two list)

主要有兩種流派,map 流與 zip 流。
(官方文件寫 map 的方法)

這邊我先自己寫一次看看

zip 做 list sum

只需要注意 zip 出來的資料型態是 zip,
需要用 list 再轉一次格式。

可參考:

a = [1,2]
b = [3,4]
sum =  [x + y for x,y in zip(a,b)]
print(sum)
# or you can use
sum2 =  list(x + y for x,y in zip(a,b))
print(sum2)

map 做 list sum

一樣,需要注意 map 出來的資料型態是 map,
需要用 list 再轉一次格式。

可參考:

a = [1,2]
b = [3,4]
sum =  list(map(lambda x, y: x + y,  a, b))
print(sum)

這裡注意一下,我們不能直接用上面 zip 中的 [] 方式直接轉,
會顯示 [map object],不符合我們的預期。