【数组篇】118. 杨辉三角

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 <= numRows <= 30

算法分析

解题思路

数学法：从头往后处理

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans = new ArrayList<>();
        if (numRows <= 0) {
            return ans;
        }
        List<Integer> one = new ArrayList<>();
        one.add(1);
        ans.add(one);
        for (int i = 1; i < numRows; i++) {
           List<Integer> res = new ArrayList<>();
           res.add(1);
           List<Integer> temp = ans.get(i - 1);
           for (int j = 1; j < i; j++) {
               res.add(temp.get(j - 1) + temp.get(j));
           }
           res.add(1);
           ans.add(res);
        }
        return ans;
    }
}

复杂性分析

时间复杂度：O(numRows2)
空间复杂度：O(1)