每天 3 分钟，走上算法的逆袭之路。
前文合集
代码仓库
GitHub： https://github.com/meteor1993/LeetCode
Gitee： https://gitee.com/inwsy/LeetCode
题目：杨辉三角
题目来源：https://leetcode-cn.com/problems/pascals-triangle-ii/
给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。
示例:
输入: 3
输出: [1,3,3,1]
进阶：
你可以优化你的算法到 O(k) 空间复杂度吗？
解题方案一：暴力求解
这道题和昨天那道题非常像，基本上昨天那道题返回结果稍微改动下就可以了。
先看下修改自昨天的那个答案：
public List<Integer> getRow(int numRows) {
List<List<Integer>> triangle = new ArrayList<List<Integer>>();
// 直接给第一行赋值，永远是 1
triangle.add(new ArrayList<>());
triangle.get(0).add(1);
for (int i = 1; i <= numRows; i++) {
// 定义当前行
List<Integer> row = new ArrayList<>();
// 定义上一行
List<Integer> prevRow = triangle.get(i - 1);
// 当前行开头为 1
row.add(1);
// 计算每一个数值，结果是上一行的 j 和 j + 1 位置的和
for (int j = 1; j < i; j++) {
row.add(prevRow.get(j - 1) + prevRow.get(j));
}
// 当前行添加末尾数字 1
row.add(1);
// 把当前行添加到要返回的列表中
triangle.add(row);
}
return triangle.get(numRows);
}
这么做其实有点浪费，我们把每一行的结果全记了下来，实际上我们只需要记录上一行的结果就可以了，那么代码可以稍微优化一下：
public List<Integer> getRow(int numRows) {
List<Integer> row = new ArrayList<> ();
List<Integer> prevRow = new ArrayList<> ();
for (int i = 0; i <= numRows; i++) {
row = new ArrayList<> ();
for (int j = 0; j <= i; j++) {
if (j == 0 || j == i) {
row.add(1);
} else {
row.add(prevRow.get(j - 1) + prevRow.get(j));
}
}
prevRow = row;
}
return row;
}
这段代码中，我没有再保存杨辉三角所有的结果，只保留了当前行 row 和上一行 prevRow 。通过每次循环中，当前行赋值给上一行，来求解下一行的数据，当然，时间复杂度和前面的方案是一样的，只是节省了一定程度上的空间。
解题方案二：通项公式求解
这个方案是看了答案以后才知道的，我原以为还有什么我想不到的优化方案，结果是通过数学的方式总结出来通项公式直接进行计算。
杨辉三角实际上是组合数构成的：
如果要求其中某一个数字 \(C_n^k\) 有一个通项公式如下：
\[C_n^k = n!/(k!(n - k)!) = (n * (n - 1) * (n - 2) * ... (n - k + 1))/k! \]
我们可以根据这个通项公式来写算法。
public List<Integer> getRow_2(int numRows) {
List<Integer> list = new ArrayList<>();
int N = numRows;
for (int k = 0; k <= N; k++) {
list.add(combination(N, k));
}
return list;
}
private int combination(int N, int k) {
long res = 1;
for (int i = 1; i <= k; i++) {
res = res * (N - k + i) / i;
}
return (int) res;
}
这个方案我们是按照通项公式，对每一项都进行了从头到尾的计算得出来的结果，实际上这个组合数是有联系的，如下：
\[C_n^k = C_n^{k - 1} * (n - k + 1)/k \]
这样我们就不用每次都从头计算每个数字了，只需要将前一个数字记录下来，就可以通过上面这个公式直接求解。
public List<Integer> getRow_3(int numRows) {
List<Integer> list = new ArrayList<>();
int N = numRows;
long pre = 1;
list.add(1);
for (int k = 1; k <= N; k++) {
long cur = pre * (N - k + 1) / k;
list.add((int) cur);
pre = cur;
}
return list;
}
这个算法到这里就结束了么？当然没有，这个还能接着优化，因为杨辉三角的每一行都是左右对称的，我们没有必要所有的值都求出来，可以只计算一半，后面一半由前面一半直接进行补充。
public List<Integer> getRow_4(int numRows) {
List<Integer> list = new ArrayList<>();
int N = numRows;
long pre = 1;
list.add(1);
for (int k = 1; k <= N; k++) {
if (k <= (N + 1) / 2) {
long cur = pre * (N - k + 1) / k;
list.add((int) cur);
pre = cur;
} else {
list.add(list.get(N - k));
}
}
return list;
}
果然在答案中是能人辈出，我一个大写的佩服。