118. 楊輝三角
輸入: numRows = 5
輸出: [
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]]
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
# 二維數(shù)組的生成
result = []
# 外循環(huán)實現(xiàn)對元素的添加到大數(shù)組
for i in range(numRows):
row = []
# 內(nèi)循環(huán)實現(xiàn)對數(shù)組的計算
for j in range(i+1):
# 首元素賦值為1
if j == 0 or j == i:
row.append(1)
else:
row.append(result[i-1][j-1]+result[i-1][j])
result.append(row)
return result
119. 楊輝三角 II
給定一個非負索引 rowIndex湘纵，返回「楊輝三角」的第 rowIndex 行貌笨。
在「楊輝三角」中桅滋，每個數(shù)是它左上方和右上方的數(shù)的和僧著。
- 方法1：記錄每個求解結(jié)果
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
result = []
for i in range(rowIndex+1):
row = []
for j in range(i+1):
if j == 0 or j == i:
row.append(1)
else:
row.append(result[i-1][j-1] + result[i-1][j])
result.append(row)
return result[-1]
- 方法2：直接求解 降低空間復(fù)雜度
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
result = [0]*(rowIndex+1)
for i in range(rowIndex+1):
# 逆序遍歷
for j in range(i, -1, -1):
if j == 0 or j == i:
result[j] = 1
# 中間值為之前元素前兩個位置之和
else:
result[j] = result[j] + result[j-1]
return result
