Leetcode No.119 杨辉三角 II
Leetcode No.119 杨辉三角 II
week
发布于 2021-05-06 15:59:41
发布于 2021-05-06 15:59:41
代码可运行
运行总次数：0
代码可运行
题目描述
给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。
[1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1]
示例:
输入: 3 输出: [1,3,3,1]
解题思路:动态规划
杨辉三角具有以下性质：
1、每行数字左右对称，由 1 开始逐渐变大再变小，并最终回到 1。 2、每个数字等于上一行的左右两个数字之和，可用此性质写出整个杨辉三角。即第 n 行的第 i 个数等于第 n−1 行的第 i-1个数和第 i 个数之和。
依据性质 2，我们可以一行一行地计算杨辉三角。每当我们计算出第 i 行的值，我们就可以使用动态规划的思想在线性时间复杂度内计算出第i+1 行的值。
首先我们构造整个三角形列表，三角形的每一行以子列表的形式存储。
然后我们会检查行数为0的特殊情况，否则我们返回[1]。
如果numRows>0，我们会用[1]来作为第一行来初始化三角形列表，并按照如下方式填充
1
1，1
1，2，1
1，3，3，1
1，4，6，4，1
动态转移方程为a[i][j]=a[i-1][j-1]+a[i-1][j]
最后我们返回第k行
class Solution {
public List<Integer> getRow(int rowIndex) {
List<List<Integer>> all=new ArrayList();
for(int i=0;i<=rowIndex;i++){
List<Integer> row=new ArrayList();
for(int j=0;j<=i;j++){
if(j==0||i==j){
row.add(1);
}else{
row.add(all.get(i-1).get(j-1)+all.get(i-1).get(j));
}
}
all.add(row);
}
return all.get(rowIndex);
}
}时间复杂度：O(numRows^2)。
空间复杂度：O(1)。不考虑返回值的空间占用。
注意到对第 i+1 行的计算仅用到了第 i行的数据，因此可以使用滚动数组的思想优化空间复杂度。
class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> pre=new ArrayList();
for(int i=0;i<=rowIndex;i++){
List<Integer> row=new ArrayList();
for(int j=0;j<=i;j++){
if(j==0||i==j){
row.add(1);
}else{
row.add(pre.get(j-1)+pre.get(j));
}
}
pre=row;
}
return pre;
}
}时间复杂度：O(numRows^2)。
空间复杂度：O(1)。不考虑返回值的空间占用。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/02/27 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
