119. Pascal’s Triangle II

Given an index k, return the kth row of the Pascal’s triangle.

For example, given k = 3,
Return [1,3,3,1].

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

思路:118的变体, 求第kth row的元素集合, space要求为O(k).我们需要做in-place的变换。 时间复杂度同样为O(n^2). 遍历的时候我们可以从后往前来遍历,利用row(i) = preRow(i) + preRow(i+1)来推断出当前i+1行元素,更新list。

public class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> res = new ArrayList<>();
        if (rowIndex < 0) return res;
        res.add(1); // add first element
        for (int i = 0; i < rowIndex; i++) {
            // get ith row, scan from right to left
            for(int j = res.size() - 2; j>=0; j-- ) {
                int ele = res.get(j) + res.get(j + 1);
                res.set(j+ 1, ele);
            }
            res.add(1);
        }
        return res;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s