【Leetcode 每日一题】119. 杨辉三角 II

问题背景

给定一个非负索引 $rowIndex$，返回「杨辉三角」的第 $rowIndex$ 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。

数据约束

• $0\le rowIndex\le 33$

解题过程

这题其实之前做过，定义列表并且按规则计算对应位置上的值即可。
另外考虑到要求的结果范围有限，也可以先打表，根据实际情况返回结果。这种做法严格地说来不符合 $O(rowIndex)$ 的空间要求，但其实效率非常不错。

具体实现

模拟计算

class Solution {
    public List<Integer> getRow(int rowIndex) {
        if (rowIndex == 0) {
            return List.of(1);
        }
        List<Integer> pre = new ArrayList<>();
        pre.add(1);
        pre.add(1);
        List<Integer> res;
        while (--rowIndex > 0) {
            res  = new ArrayList<>(pre);
            for (int i = 1; i < pre.size(); i++) {
                res.set(i, pre.get(i - 1) + pre.get(i));
            }
            res.add(1);
            pre = new ArrayList<>(res);
        }
        return pre;
    }
}

打表预处理

class Solution {
    private static final int MAX_N = 34;
    private static final List<Integer>[] res = new List[MAX_N];

    static {
        res[0] = List.of(1);
        for (int i = 1; i < res.length; i++) {
            List<Integer> row = new ArrayList<>(i + 1);
            row.add(1);
            for (int j = 1; j < i; j++) {
                row.add(res[i - 1].get(j - 1) + res[i - 1].get(j));
            }
            row.add(1);
            res[i] = row;
        }
    }


    public List<Integer> getRow(int rowIndex) {
        return res[rowIndex];
    }
}