题目

杨辉三角

给定一个非负整数 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年。
杨辉三角是中国数学史上的一个伟大成就。

杨辉三角形的规律如题目中所示。

题解思路

1. 
   
2. 定义一个集合存储结果集
   
3. 定义一个两重循环，分别进行运算，row 数为 numRows, 列数的值为 0 -> i 其中 i 表示当前是第几行.
   
4. 如果当前 row 的列是第一列或最后一个列的当前的值为 1。
   
5. 当前行其他的列的其他数据, 等于 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;

    }

}

提交后反馈结果：