LeetCode经典算法题 no.118杨辉三角

题目：杨辉三角

题目描述：

给定一个非负整数 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
• 其余元素满足等式nums[i][j]=nums[i-1,j-1][i-1,j]
• 第n（n从0开始）行中，有n+1个元素
• 前n行中共有 [n(n+1)]/2 个元素【等差数列前n项求和】

代码实现：

知识点回顾：

ArrayList类是一个特殊的数组–动态数组。通过添加和删除元素，就可以动态改变数组的长度。

优点：1、支持自动改变大小 2、可以灵活的插入元素 3、可以灵活的删除元素

局限：比一般的数组的速度慢一些

ArrayList是List接口的一个实现类，是继承AbstractList抽象类和实现List接口的一个实现类。因此，List接口不能被构造，也就是我们说的不能创建实例对象，而ArrayList实现类的实例对象就充当了这个指向List接口的对象引用。

class Solution {
    public List> generate(int numRows) {
        List> result = new ArrayList>();
        for(int i=0;i
            List list = new ArrayList();
            for(int j=0;j<=i;j++){
                if(j == 0 || j ==  i){
                    list.add(1);
                }else{
                    list.add(result.get(i-1).get(j-1) + result.get(i-1).get(j));
                }
            }
            result.add(list);
        }
        return result;
    }
}