Friday, March 20, 2015

118. Pascal's Triangle Leetcode Java

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]
]
Solution:
The pattern is clear. For any row, the first and last element is 1. For all other elements, the res[i][j]=res[i-1][j-1]+res[i-1][j], where i is the row number and j is the column number.
 public List<List<Integer>> generate(int numRows) {  
    List<List<Integer>> res=new ArrayList<List<Integer>>();  
    for(int i=1;i<=numRows;i++){  
      List<Integer> items=new ArrayList<Integer>();  
      for(int j=0;j<i;j++){  
        if(j==0 || j==i-1) items.add(1);  
        else items.add(res.get(i-2).get(j)+res.get(i-2).get(j-1));  
      }  
      res.add(items);  
    }  
    return res;  
   }  

No comments:

Post a Comment