大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。
一、题目
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。