Pascal’s Triangle II, Leetcode 解题笔记

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?

题目要求in-place操作,其实就是数组更新题,为了防止每次更新把还需要用到的旧的元素冲掉,可以每次先在list后面加个1,然后从后向前更新。注意index角标的范围和边界。

public class Solution {
    public ArrayList<Integer> getRow(int rowIndex) {
        ArrayList<Integer> ret = new ArrayList<Integer>();
        ret.add(1);
        if(rowIndex == 0) return ret;
        for(int i = 0; i < rowIndex; i++){
            int len = ret.size();
            ret.add(1);
            for(int j = len-1; j > 0; j--){
                ret.set(j, ret.get(j-1) + ret.get(j));
            }
        }
        return ret;
    }
}
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