【每日一题】【算法题】【杨辉三角】给定一个非负索引|【每日一题】【算法题】【杨辉三角】给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行【每日一题】【算法题】【杨

文章图片

解法一：我们只需要一层一层的求。但是不需要把每一层的结果都保存起来，只需要保存上一层的结果，就可以求出当前层的结果了。

public List getRow(int rowIndex) { List pre = new ArrayList<>(); List cur = new ArrayList<>(); for (int i = 0; i <= rowIndex; i++) { cur = new ArrayList<>(); 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 cur; }

优化：

每层的第一个元素始终为1。基于这两点，我们把之前j == 0 || j == i的情况移到了for循环外进行处理。
最后一个也是1，也移到内循环的外面。
把pre与cur省去，然后把cur当作pre,用temp存j的数据，赋值给pre，更新j+1时用pre+j的值

public List getRow(int rowIndex) { int pre = 1; List cur = new ArrayList<>(); cur.add(1); for (int i = 1; i <= rowIndex; i++) { for (int j = 1; j < i; j++) { int temp = cur.get(j); cur.set(j, pre + cur.get(j)); pre = temp; } cur.add(1); } return cur; }

解法二公式法

如果熟悉杨辉三角，应该记得杨辉三角其实可以看做由组合数构成。

【每日一题】【算法题】【杨辉三角】给定一个非负索引|【每日一题】【算法题】【杨辉三角】给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行

文章图片

根据组合数的公式，将(n-k)!约掉，化简就是下边的结果。

文章图片
=n!/(k!(n?k)!)=(n?(n?1)?(n?2)?...(n?k+1))/k!
然后我们就可以利用组合数解决这道题。

public List getRow(int rowIndex) { List ans = new ArrayList<>(); int N = rowIndex; for (int k = 0; k <= N; k++) { ans.add(Combination(N, k)); } return ans; }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; }

我们可以优化一下。
上边的算法对于每个组合数我们都重新求了一遍，但事实上前后的组合数其实是有联系的。

文章图片
?=

文章图片
?×(n?k+1)/k
代码的话，我们只需要用pre变量保存上一次的组合数结果。计算过程中，可能越界，所以用到了long。

public List getRow(int rowIndex) { List ans = new ArrayList<>(); int N = rowIndex; long pre = 1; ans.add(1); for (int k = 1; k <= N; k++) { long cur = pre * (N - k + 1) / k; ans.add((int) cur); pre = cur; } return ans; }

【【每日一题】【算法题】【杨辉三角】给定一个非负索引|【每日一题】【算法题】【杨辉三角】给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行】