119. Pascals Triangle II

Leetcode Array

Given a non-negative index $k$ where $k \le 33$, return the $k^{th}$ 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?

分析

杨辉三角。一开始写的笨办法，保存需要求和的两个值，轮流更新。

public List<Integer> getRow(int rowIndex) {
    List<Integer> res = new ArrayList<>();
    int prev = 1, before = 1;
    for (int i = 0; i <= rowIndex; i++) {
        res.add(1);
        for (int j = 0; j <= i; j++) {
            prev  = res.get(j);
            if (!(j == 0 || j == i))
                res.set(j, prev + before);
            before = prev;
        }
    }
    return res;
}

比较好的办法是对于第$i$行杨辉三角，从后往前遍历，可以保证值没有被覆盖掉。

• $\text{row}_0 = 1$
• $\text{row}_1 = (\text{row}_0[0], \text{row}_1[1] + \text{row}_0[0]) = 1, 1$
• $\text{row}_2 = (\text{row}_0[0], \text{row}_1[1] + \text{row}_1[0], \text{row}_2[2] + \text{row}_1[1]) = 1, 2, 1$
• $\text{row}_3 = (\text{row}_0[0], \text{row}_2[1] + \text{row}_2[0], \text{row}_2[2] + \text{row}_2[1], \text{row}_2[3] + \text{row}_2[2]) = 1, 3, 3, 1$

public List<Integer> getRow(int rowIndex) {
    List<Integer> res = new ArrayList<>(rowIndex + 1);
    res.add(1);
    for (int i = 1; i <= rowIndex; i++) {
        res.add(0); 
        for (int j = i; j >= 1; j--)
            res.set(j, res.get(j) + res.get(j - 1));
    }
    return res;
}