文章目录
1.Description
给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。
2.Example
输入: 3
输出: [1,3,3,1]
3.Solution
https://leetcode-cn.com/problems/pascals-triangle-ii/solution/yang-hui-san-jiao-ii-by-leetcode-solutio-shuk/
杨辉三角具体性质见官方题解。
法一：递推（时间复杂度都是平方）
一行一行地计算。
class Solution {
public List<Integer> getRow(int rowIndex) {
List<List<Integer>> C = new ArrayList<List<Integer>>();
for (int i = 0; i <= rowIndex; ++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(C.get(i - 1).get(j - 1) + C.get(i - 1).get(j));
}
}
C.add(row);
}
return C.get(rowIndex);
}
}
优化：注意到对第 i+1行的计算仅用到了第 i 行的数据，因此可以使用滚动数组的思想优化空间复杂度。
class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> pre = new ArrayList<Integer>();
for (int i = 0; i <= rowIndex; ++i) {
List<Integer> cur = new ArrayList<Integer>();
for (int j = 0; j <= i; ++j) {
if (j == 0 || j == i) {
cur.add(1);
} else {
cur.add(pre.get(j - 1) + pre.get(j));
}
}
pre = cur;
}
return pre;
}
}
进一步优化：
递推式
表明，当前行第 ii 项的计算只与上一行第 i-1 项及第 i 项有关。因此我们可以倒着计算当前行，这样计算到第 ii 项时，第 i-1 项仍然是上一行的值。（做背包问题的时候遇到过类似的）
class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> row = new ArrayList<Integer>();
row.add(1);
for (int i = 1; i <= rowIndex; ++i) {
row.add(0);
for (int j = i; j > 0; --j) {
row.set(j, row.get(j) + row.get(j - 1));
}
}
return row;
}
}
2.线性递推（时间复杂度为k）
class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> row = new ArrayList<Integer>();
row.add(1);
for (int i = 1; i <= rowIndex; ++i) {
//因为两个数相乘的值可能会溢出int，所以先改成long再改回int
row.add((int) ((long) row.get(i - 1) * (rowIndex - i + 1) / i));
}
return row;
}
}