一、题目
1、算法题目
“给定一个非负整数numRows，生成杨辉三角前numRows行。”
题目链接：
来源：力扣（LeetCode）
链接： 118. 杨辉三角
2、题目描述
给定一个非负整数 numRows， 生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
网络异常，图片无法展示
|
示例 1： 输入: numRows = 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]] 复制代码
示例 2： 输入: numRows = 1 输出: [[1]] 复制代码
二、解题
1、思路分析
首先来了解一下什么是杨辉三角，杨辉三角是二项式系数在三角形中的一种几何排列，把二项式系数图形化，把组合数内在的一些代数性质直观地从图形中体现出来，是一种离散型的数与形的结合。
杨辉三角具有以下性质：
网络异常，图片无法展示
|
根据以上性质，可以逐行计算杨辉三角，当计算到第i行的时候，就可以在线性时间复杂度内计算出第i+1行的值。
2、代码实现
代码参考：
class Solution { public List<List<Integer>> generate(int numRows) { List<List<Integer>> ret = new ArrayList<List<Integer>>(); for (int i = 0; i < numRows; ++i) { List<Integer> row = new ArrayList<Integer>(); for (int j = 0; j <= i; ++j) { if (j == 0 || j == i) { row.add(1); } else { row.add(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j)); } } ret.add(row); } return ret; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(numRows2)
空间复杂度： O(1)
不考虑返回值的空间占用，只需要常数级的空间复杂度。
三、总结
第i行的第j个数=第i-1行的j-1个数 + 第i-1行的第j个数。
注意下，左右边界都是1。
