图解精选 TOP 面试题 007 | 杨辉三角
该系列题目取自 LeetCode 精选 TOP 面试题列表：https://leetcode-cn.com/problemset/top/
题目描述
LeetCode 118. 杨辉三角：https://leetcode-cn.com/problems/pascals-triangle/
给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。
示例:
输入: 5
输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
解题思路
杨辉三角可以说是一道大家非常熟悉的题目了，一开始学 C 语言的时候就经常做打印杨辉三角的作业。
杨辉三角的特征是：每个数是它左上方和右上方的数的和。
但是，由于我们使用的数组都是规整的矩形，不是三角形，没有所谓「左上方」、「右上方」的说法。为了方便观察，我们将每行的数字左对齐：
杨辉三角左对齐
这样一来，我们很容易观察到：
- 杨辉三角每一行的第一位和最后一位都为 1
- 中间位置的数字是由它上一行对应位置的数字以及上一行对应位置左侧的数字相加得到
因为下一行的情况总需要由上一行的情况推出，即我们需要记录每一行的结果。所以构建杨辉三角本质上是一个动态规划问题，我们可以总结出如下推导式：
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
其中，dp[i][j] 表示第 i 行的第 j 个数。
具体实现
Python
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
res = []
for i in range(numRows):
tmp = []
for j in range(i + 1):
# 首项和末项都是 1
if j == 0 or j == i:
tmp.append(1)
else:
tmp.append(res[i - 1][j - 1] + res[i - 1][j])
res.append(tmp)
return res
Go
func generate(numRows int) [][]int {
var res [][]int = make([][]int, numRows)
for i := 0; i < numRows; i++ {
res[i] = make([]int, i + 1)
for j := 0; j < i + 1; j++ {
if j == 0 || j == i {
res[i][j] = 1
} else {
res[i][j] = res[i - 1][j - 1] + res[i - 1][j]
}
}
}
return res
}
复杂度
时间复杂度
具体实现中我们使用了两层循环，其中外层循环次数为 numRows 次，其每次对应的内层循环次数为：
- 外层第 1 次循环：内层循环 1 次
- 外层第 2 次循环：内层循环 2 次
- ……
- 外层第
numRows循环：内层循环numRows次
因此，总的循环次数为：，根据高斯公式可以计算得出：
所以复杂度为 。
空间复杂度
每次循环都会有一个数字加入结果集，所以需要的空间复杂度也是 。
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-12-26，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
