每天 3 分钟，走上算法的逆袭之路。

前文合集

每日一道 LeetCode 前文合集

代码仓库

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>>();// 直接给第一行赋值，永远是 1triangle.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);// 当前行开头为 1row.add(1);// 计算每一个数值，结果是上一行的 j 和 j + 1 位置的和for (int j = 1; j < i; j++) {row.add(prevRow.get(j - 1) + prevRow.get(j));}// 当前行添加末尾数字 1row.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;
}

果然在答案中是能人辈出，我一个大写的佩服。

您的扫码关注，是对小编坚持原创的最大鼓励：）