Leetcode No.118 杨辉三角
一、题目描述
给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。
示例:
输入: 5 输出: [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,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]
三、代码
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> rs=new ArrayList();
for(int i=0;i<numRows;i++){
List<Integer> list=new ArrayList();
for(int j=0;j<=i;j++){
System.out.println("i:"+i+",j:"+j);
if(j==0||j==i){
list.add(1);
}else{
int element=rs.get(i-1).get(j)+rs.get(i-1).get(j-1);
list.add(element);
}
System.out.println(list);
}
rs.add(list);
}
return rs;
}
}四、复杂度分析
时间复杂度：O(numRows^2)。
空间复杂度：O(1)。不考虑返回值的空间占用。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021-02-27 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录