Leetcode(119) Pascal Triangle II

发表于 | 分类于

Description

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.

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

Example:

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

Follow up:

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

解法

118题的变体，这里我先用递归写了一遍：

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public List<Integer> getRow(int rowIndex) {
        if(rowIndex < 0){
            return null;
        }
        if(rowIndex == 0){
            List<Integer> res = new ArrayList<Integer>();
            res.add(1);
            return res;
        }
        else{
            List<Integer> lastRow = getRow(rowIndex - 1);
            List<Integer> res = new ArrayList<Integer>();
            for(int i = 0; i <= rowIndex; i++){
                if(i == 0 || i == rowIndex){
                    res.add(1);
                }
                else{
                    res.add(lastRow.get(i-1)+lastRow.get(i));
                }
            }
            return res;
        }
    }
}

在网上看到有更妙的解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
 public List<Integer> getRow(int rowIndex) {
    List<Integer> list = new ArrayList<Integer>();
    if (rowIndex < 0)
        return list;

    for (int i = 0; i < rowIndex + 1; i++) {
        list.add(0, 1);
        for (int j = 1; j < list.size() - 1; j++) {
            list.set(j, list.get(j) + list.get(j + 1));
        }
    }
    return list;
}

在0的位置添上1：[1]，此时为第一行，不满足则继续；
不执行小循环，继续0的位置添上1：[1，1]，此时为第二行，不满足则继续；
不执行小循环，继续0的位置添上1：[1，1，1]，执行小循环，得[1，2，1]，此时为第三行，不满足则继续；
此时继续0的位置添上1：[1，1，2，1]，执行小循环，得[1，3，3，1]，此时为第四行，不满足则继续；
……

这样下去确实可以得到每一行的数据，其实就是在一个List内模拟杨辉三角的性质，确实很赞。
原文链接：https://blog.csdn.net/Cloudox_/article/details/52993117