【一天一道Leetcode】杨辉三角
题目描述：
给定一个非负整数numRows，
生成杨辉三角的前numRows行。
杨辉三角中，每个数是它左上方和右上方数之和。
如下面的示例：
输入: 5
输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]提示：
1. 0 <= key <= 10^6
2. 最多调用 10^4 次 add、remove 和 contains。
02
方法和思路
从题意和杨辉三角的特性可知。
每个数是它左上方和右上方的数的和。
我们可以创建一个空数组res，
接着采用递归的方式，从第一行开始由上往下不断生成元素均为1的新数组tmp，
同时根据杨辉三角，每个数是它左上方和右上方的数的和的原理，不断更新tmp数组的值，将每一个更新数字后的数组tmp保存到空数组res中，
例如：
我输入的数字是5，则我会生成5次tmp数组的值。
第一次：tmp=[1]
此时为第一行，直接将该数组存入空数组res中。
res=[[1]]第二次：tmp=[1,1]
此时为第二行，直接将该数组存入数组res中。
res=
[[1],
[1,1]]第三次：tmp=[1,1,1]
此时为第三行，进行每个数是它左上方和右上方的数的和的计算。
计算完之后tmp=[1,2,1],将该数组存入数组res中。
res=
[[1],
[1,1],
[1,2,1]]第四次：tmp=[1,1,1,1],
此时为第四行，进行每个数是它左上方和右上方的数的和的计算。
计算完之后tmp=[1,3,3,1],将该数组存入数组res中。
res=
[[1],
[1,1],
[1,2,1],
[1,3,3,1]]第五次：tmp=[1,1,1,1,1]
此时为第四行，进行每个数是它左上方和右上方的数的和的计算。
计算完之后tmp=[1,4,6,4,1],将该数组存入数组res中。
res=
[[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]]最后输出完全体杨辉三角res。
我们用代码表示此题的解法如下：
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
res = []
for i in range(numRows):
tmp = [1] * (i + 1)
for j in range(i + 1):
if 0 < j < i:
tmp[j] = res[i - 1][j - 1] + res[i - 1][j]
res.append(tmp)
return res本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2021-03-23，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录