LeetCode刷题 #118 杨辉三角 Java

题目： 给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。在杨辉三角中，每个数是它左上方和右上方的数的和。 示例： 输入： 5

输出：

[ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]

  杨辉三角（也称帕斯卡三角），它是一个无限对称的数字金字塔，从顶部的单个1开始，下面一行中的每个数字都是上面两个数字的和。   它是二项式系数在三角形中的一种几何排列，在中国南宋数学家杨辉1261年所著的《详解九章算法》一书中出现。在欧洲，帕斯卡（1623—-1662）在1654年发现这一规律，所以这个表又叫做帕斯卡三角形。帕斯卡的发现比杨辉要迟393年，比贾宪迟600年。

思路：   第一行是一个 1，第二行是两个 1，前两行就可以直接写，以及每一行的第一和最后一个数必然是 1 。   第三行之后，运用相加的规则进行计算：前一行此位置的数 + 前一行此位置的前一个数。

代码：

class Solution {
          
   
    public List<List<Integer>> generate(int numRows) {
          
   
    // 注意小于等于零的情况
        if (numRows <= 0) {
          
   
            return new ArrayList<>();
        } 
        List<List<Integer>> result = new ArrayList<>();  
    // 第一行：只有一个数 1
        List<Integer> firstLine = new ArrayList<>();
        firstLine.add(1);
        result.add(firstLine);
        if (numRows == 1) {
          
   
            return result;
        }    
    // 第二行：两个数即两个 1 
        List<Integer> secondLine = new ArrayList<>();
        secondLine.add(1);
        secondLine.add(1);
        result.add(secondLine);
        if (numRows == 2) {
          
   
            return result;
        }
    // 第三行开始，运用规则，相加来进行计算
        for (int row = 3;row <= numRows;row ++) {
          
   
            List<Integer> curLine = new ArrayList<>();
            curLine.add(1);
    // row - 1 是当前行减一，再减一是因为 get()是按照下标来取
            List<Integer> prevLine = result.get(row - 1 - 1);
            for (int col = 2;col <= row - 1;col ++) {
          
   
                int num1 = prevLine.get(col - 1);  // 上一行此位置的数
                int num2 = prevLine.get(col - 1 - 1);  // 上一行此位置前一个位置的数
                curLine.add(num1 + num2);
            }
            curLine.add(1);
            result.add(curLine);
        }
        return result;
    }
}