題目出處
難度
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 3 3 1
1
- 上一層 1+3, 3+3, 3+1 填入
1 3 3 1
1 4 6 4
- 補上最後一個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],不符合我們的預期。