[LeetCode] 119. Pascal's Triangle II

Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal's triangle.

Note that the row index starts from 0.

In Pascal's triangle, each number is the sum of the two numbers directly above it.

Example:

Input: 3
Output: [1,3,3,1]

Follow up:

Could you optimize your algorithm to use only O(k) extra space?

杨辉三角II。

跟版本一类似，也是计算杨辉三角，但是只需要输出某一行的结果即可，规定只允许使用O(n)级别的额外空间。

参考版本一的思路二，重复利用 list 数组即可。版本一的思路是当前 index j 上的数字是之前一行的 j 和 j - 1 的和。但是这道题的 followup 是只能使用固定的额外空间，按照版本一的做法是会覆盖之前的结果的。所以对于每一行，只能从右往左开始算，这样就不会覆盖之前的结果了。记得最后加上每一行的最后一个 1。

时间O(n^2)

空间O(n)

Java实现

 1 class Solution {
 2     public List<Integer> getRow(int rowIndex) {
 3         List<Integer> res = new ArrayList<>();
 4         res.add(1);
 5         for (int i = 1; i <= rowIndex; i++) {
 6             for (int j = res.size() - 1; j > 0; j--) {
 7                 res.set(j, res.get(j - 1) + res.get(j));
 8             }
 9             res.add(1);
10         }
11         return res;
12     }
13 }

这里还有一种思路。我们可以把题目给的例子三角形转化一下，如果我们试着把他看做一个直角三角形，那么数字的排列会是如下。

121

1331

14641

注意到除了开头和结尾的 1，中间的数字 i = 上一行的 i + 上一行的 i - 1。又因为我们重复使用了同一个list，所以对于上一行的结果而言，中间某个位置 j 上的数字 + （j + 1位置上的数字）= 下一行位置 j 上的数字。开头和结尾的 1，每次是通过一开始就加的 1 从而隐式地被加入结果集的。

时间O(n^2)

空间O(n)

Java实现

 1 class Solution {
 2     public List<Integer> getRow(int rowIndex) {
 3         List<Integer> list = new ArrayList<>();
 4         for (int i = 0; i <= rowIndex; i++) {
 5             // first 1 at each row
 6             list.add(0, 1);
 7             for (int j = 1; j < list.size() - 1; j++) {
 8                 list.set(j, list.get(j) + list.get(j + 1));
 9             }
10         }
11         return list;
12     }
13 }