Wednesday, May 11, 2016

Pascal's Triangle -- Leetcode

Question:
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]
]

Answer:

public class Solution {

    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(numRows <= 0) return res;
       
        List<Integer> subres = new ArrayList<Integer>();
        subres.add(1);
        res.add(new ArrayList<Integer>(subres));
       
        for(int i = 1; i < numRows; ++i){
            for(int j = i-2; j >= 0; --j){
                subres.set(j+1, subres.get(j) + subres.get(j+1));
            }
            subres.add(1);
            res.add(new ArrayList<Integer>(subres));
        }
       
        return res;
    }
}

No comments:

Post a Comment