长大后想做什么？做回小孩！

0%

LeetCode——杨辉三角I&II

发表于 分类于 Valine：
本文字数： 352

NO.118 杨辉三角 简单

JNnh8J.png

思路一：模拟 第一行是1，每一行的首尾都是1，中间的数字是上一行左右”肩膀”上的两个数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> res = new ArrayList<>();
    if (numRows == 0) return res;
    //第一行是1
    res.add(new ArrayList<>());
    res.get(0).add(1);
    for (int i = 1; i < numRows; i++) {
        //上一行
        List<Integer> pre = res.get(i - 1);
        //当前行
        List<Integer> curr = new ArrayList<>();
        //行首是1
        curr.add(1);
        //填充当前行中间元素
        for (int j = 1; j < i; j++) {
            curr.add(pre.get(j - 1) + pre.get(j));
        }
        //行尾是1
        curr.add(1);
        res.add(curr);
    }
    return res;
}

时间复杂度：O(numRows^2)

NO.119 杨辉三角II 简单

JNK4n1.png

思路一：模拟 和NO.118一样，不过本题只需要返回第K行，而且要求空间复杂度O(k)。

去掉之前代码中的res和pre两个集合，只保留curr用于保存当前行，当计算下一行时curr还要充当pre，就可以实现O(k)空间要求。

用这种方式我们需要逆序计算每一行的值，不然会覆盖掉(j-1)的值。

PS：踩了一个坑，本题输出的行K是从0开始的。。。0、1、2、3。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public List<Integer> getRow(int rowIndex) {
    List<Integer> curr = new ArrayList<>();
    curr.add(1);
    //一行一行计算
    for (int i = 1; i <= rowIndex; i++) {
        //逆序计算每个值
        for (int j = i - 1; j > 0; j--) {
            curr.set(j, curr.get(j - 1) + curr.get(j));
        }
        //行尾的1
        curr.add(1);
    }
    return curr;
}

时间复杂度：O(numIndex^2) 本题可以有更好时间实现，就是使用数学的方法直接公式计算。

空间：O(k)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github