Pascal’s Triangle II

Leave a comment

November 22, 2016 by oneOokay

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?


首先要注意的是第k行的元素是有k + 1个

我第二层for-loop的迭代从0开始,发现不行,因为更新第4点的值需要原来的第3的值和第4的值。于是在4点的值更新之后,接着更新5点的时候,需要第5点和第4点的值。然而第4点的值已经发生变化了,从而得出错误的结论。

所以当发现循环从头开始走行不通的时候,可以考虑从后往前走。这题就是第二层for-loop改为从后向前走:更新第5点的时候:取第4和第5点;接下来更新第4点的时候是取第4点和第3点;已经更新过的第5点并不会对这个造成影响。

public class Solution {
    public List getRow(int rowIndex) {
        List ans = new ArrayList();
        ans.add(1);
        if (rowIndex == 0){
            return ans;
        }
        for (int i = 1; i <= rowIndex; i ++){
             //第i行一共有i + 1个元素;所以之前的第i-1行有i个元素
             //这里的j是index值,第i-1行的最后一个元素的index是i - 1
             for (int j = i - 1; j >= 1; j --){ 
             //并不需要计算第0个元素,因为第0个元素永远是1.且当j=0的时候;j - 1会报错
                    ans.set(j, ans.get(j) + ans.get(j - 1));
            }
            ans.add(1);//处理完之后,直接在最后加上1即可
        }
        return ans;
    }
}
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

%d bloggers like this: