Wednesday, July 16, 2014

Pascal's Triangle I & II

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,
Return
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

利用上一行更新下一行
public class Solution {
    //Time: O(n ^ 2)  Space: O(n ^ 2)
    public ArrayList<ArrayList<Integer>> generate(int numRows) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (numRows <= 0) {
            return res;
        }
        
        ArrayList<Integer> first = new ArrayList<Integer>();
        first.add(1);
        res.add(first);
        for (int i = 1; i < numRows; i++) {
            ArrayList<Integer> last = res.get(res.size() - 1);
            ArrayList<Integer> tmp = new ArrayList<Integer>();
            tmp.add(1);
            for (int j = 0; j < last.size() - 1; j++) {
                tmp.add(last.get(j) + last.get(j + 1));
            }
            tmp.add(1);
            res.add(tmp);
        }
        return res;
    }
}

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?
public class Solution {
    //Time: O(n^2) Space: O(n)
    public ArrayList<Integer> getRow(int rowIndex) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (rowIndex < 0) {
            return res;
        }
        
        res.add(1);
        for (int i = 1; i <= rowIndex; i++) {
            ArrayList<Integer> temp = new ArrayList<Integer>();
            temp.add(1);
            for (int j = 1; j < res.size(); j++) {
                temp.add(res.get(j) + res.get(j - 1));
            }
            temp.add(1);
            res = temp;
        }
        return res;
    }
}

No comments:

Post a Comment