难度: 简单
原题连接
内容描述
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 - 时间复杂度: O(N^2) - 空间复杂度: O(N)
高中数学知识,把行数理理清楚就ok, beats 99.11%
class Solution(object):
def generate(self, numRows):
"""
:type numRows: int
:rtype: List[List[int]]
"""
if numRows == 0:
return []
res = [[1]]
for i in range(1, numRows):
tmp = [1]
for j in range(1, i):
tmp.append(res[-1][j-1] + res[-1][j])
tmp.append(1)
res.append(tmp)
return res
总结:
- 网上还有很多其他写法,两三行搞定,但是可读性就差了些。