题目概览

给定一个非负整数 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

来源：118. 杨辉三角 - 力扣（LeetCode）

解题分析

方法：数学

第 n 层的数组等于 [1, n - 1 层每两个数据的和, 1]，因此只需要按照上一层求和再前后加上1就行。

时间复杂度：O(n²)     （n 是 numRows）
空间复杂度：O(1)

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> pre = new ArrayList<>();
        pre.add(1);
        result.add(pre);
        for (int i = 1; i < numRows; i++) {
            List<Integer> fn = buildFN(pre);
            result.add(fn);
            pre = fn;
        }
        return result;
    }

    public List<Integer> buildFN(List<Integer> list) {  
        List<Integer> fn = new ArrayList<>();
        fn.add(1);
        for (int i = 0; i < list.size() -1; i++) {
            fn.add(list.get(i) + list.get(i+1));
        }
        fn.add(1);
        return fn;
    }
}