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?
用数学方法搞定,直接generate出第n行,其实如果把每一行都算出来也是O(k)的extra space。

需要注意的是如果直接用int算r(k-1)*(n+k-1)会溢出,所以要先将所有的数都cast成double。或者先算除法,但是如果算除法也要cast成double不然会算错。

public class Solution {
    public ArrayList<Integer> getRow(int rowIndex) {
        //math matically, nth, kth element can be calculated as r(k) = C(n,k) = r(k-1)*(n-k+1)/k
        ArrayList<Integer> result = new ArrayList<Integer>();
        result.add(1);
        for (int k = 1; k <= rowIndex; k++)
        {
            result.add((int)(((double)result.get(k-1))*(double)(rowIndex-k+1)/(double)k));
        }
        return result;
    }
}

2nd Submission:
No mathmatic, just compute the Kth row line by line. Uses only O(k) space

public class Solution {
    public ArrayList<Integer> getRow(int rowIndex) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if (rowIndex < 0)
            return result;
        for (int i = 0; i <= rowIndex; i++) {
            if (i == 0) {
                result.add(1);
            }
            else {
                ArrayList<Integer> last = result;
                result = new ArrayList<Integer>();
                result.add(1);
                for (int j = 1; j < last.size(); j++) {
                    result.add(last.get(j-1) + last.get(j));
                }
                result.add(1);
            }
        }
        return result;
    }
}

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