【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];}
}