118. 杨辉三角

• 题目描述
• 解题思路
• 代码

题目描述

解题思路

解法一：数学
思路：分两层，最外层的列表ret和列表内元素（也是列表）row。然后，对于杨辉三角的每一行，两边均为1（j0 || j1），中间的元素，利用上一行对应两个元素之和（ret.get(i-1).get(j-1)+ret.get(i-1.get(j))）。最后，再将每一行添加到ret中。
时间复杂度：O(numRows^2)。
空间复杂度：O(1)。不考虑返回值的空间占用

代码

 public static List<List<Integer>> generate(int numRows) {
            List<List<Integer>> ret = new ArrayList<List<Integer>>();
            for (int i = 0; i < numRows; ++i) {
                List<Integer> row = new ArrayList<Integer>();
                for (int j = 0; j <= i; ++j) {
                    if (j == 0 || j == i) {
                        row.add(1);
                    } else {
                        row.add(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));
                    }
                }
                ret.add(row);
            }
            return ret;
        }
}

链接：https://leetcode-cn.com/problems/pascals-triangle/solution/yang-hui-san-jiao-by-leetcode-solution-lew9/
来源：力扣（LeetCode）。