帕斯卡的三角形
DescriptionExample题意解题思路code1code2
118. Pascal’s Triangle Easy
Description
Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle. In Pascal’s triangle, each number is the sum of the two numbers directly above it.
Example
Input: 5
Output:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
题意
输入一个数字，按题目规则输出对应行数的帕斯卡三角形
解题思路
这题没啥技巧而言，直接将题目所给规则实现出来就好。每行的首元素和末尾元素为1，中间元素等于前一行对应元素两数之和。开始用非常暴力的方法实现的，后来改进了一下。
code1
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
if numRows == 0:
return []
if numRows == 1:
return [[1]]
if numRows == 2:
return [[1],[1,1]]
res = []
res.append([1])
res.append([1,1])
for i in range(1,numRows-1):
for j in range(len(res[i])):
if j == 0:
temp = []
temp.append(1)
else:
temp.append(res[i][j-1]+res[i][j])
if j == len(res[i])-1:
temp.append(1)
res.append(temp)
return res
code2
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
res = []
for i in range(numRows):
res.append([1])
for j in range(1,i+1):
if j == i:
res[i].append(1)
else:
res[i].append(res[i-1][j-1]+res[i-1][j])
return res
