题目
杨辉三角
给定一个非负整数 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 <= numRows <= 30
题解
解题分析
杨辉三角介绍：
杨辉三角，是二项式系数在三角形中的一种几何排列，南宋时期数学家杨辉在 1261年 所著《详解九章算法》中出现。
在欧洲，帕斯卡（1623-1662）在1654年发现这一数学规律，所以这个又叫做帕斯卡三角形。帕斯卡的发现比 杨辉 要迟393年，比 贾宪 迟600年。 杨辉三角是中国数学史上的一个伟大成就。
杨辉三角形的规律如题目中所示。
题解思路
- 定义一个集合存储结果集
- 定义一个两重循环，分别进行运算，row 数为 numRows, 列数的值为
0 -> i其中 i 表示当前是第几行.
- 如果当前 row 的列是第一列或最后一个列的当前的值为 1。
- 当前行其他的列的其他数据, 等于
re.get(i-1).get(j-) + re.get(i -1).get(j)之和
复杂度分析
- 时间复杂度：O(num * numRow ^2)
- 空间复杂度：O(1)
解题代码
题解代码如下（代码中有详细的注释说明）：
class Solution { public List<List<Integer>> generate(int numRows) { List<List<Integer>> re = new ArrayList<>(); for (int i =0; i< numRows; i++) { List<Integer> row = new ArrayList<>(); for (int j=0; j<=i; j++) { // 行中的第一数据和最后一个数据的值为 1 if (j == 0 || j == i) { row.add(1); } else { // 其他数据, 等于 re.get(i-1).get(j-) + re.get(i -1).get(j) 之和 row.add(re.get(i -1).get(j -1) + re.get(i -1).get(j)); } } re.add(row); } return re; } }
提交后反馈结果：
