杨辉三角

WangScaler: 一个用心创作的作者。

声明：才疏学浅，如有错误，恳请指正。

题目

给定一个非负整数 numRows， 生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

初次分析

这个题上大学那会儿，就做过，在数学上好像也有做过。杨辉三角就是把二项式进行了图形化。如上图所示，每个数的值为

A(j,k）=A(j−1,k−1)+A(j−1,k)

解决这个题必须两层for循环，第一层循环是层数，也就是numRows是几，我们就遍历几次。

第二层循环是把该层的值计算出来放到LIst里面。

也就是说解决这个题的关键就在第二次for循环上。

继续分析

那么我们怎么如何得到每一层的值呢。

• 每一层的第一个数和最后一个数都是1
• 每一层的剩下的数都是上一层左右两边的数之和。
• 每一层的数量等于层数

找到这些规律，那么这个题的答案就不难写出了。

答案

public static List<List<Integer>> generate(int numRows) {
    int count = 1;
    List<List<Integer>> lists = new ArrayList<>();
    while (count <= numRows) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        if (count != 1) {
            for (int i = 0; i < lists.get(count - 2).size() - 1; i++) {
                list.add(lists.get(count - 2).get(i) + lists.get(count - 2).get(i + 1));
            }
            list.add(1);
        }
        lists.add(list);
        count++;
    }
    return lists;
}

复杂度

• 时间复杂度: O(n2)。其中n为层次的值，因为两次循环，所有为O(n2)
• 空间复杂度：O(1)。不考虑返回值的空间占用。

总结

我的答案专门写了个if条件判断是否是第一层，我感觉这个地方有优化空间，改天有时间了再来调整下代码。如果你看到了，欢迎指正哦。我这里没把第一层的数写到while循环外边，是为了防止传个小于等于0的数进来，那样直接返回第一层的答案，显然是不和逻辑的。

但是题目有强调1 <= numRows <= 30，所以可以放到外边。

都来了，点个赞再走呗！

关注WangScaler，祝你升职、加薪、不提桶！