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] ]
A:
public class PascalsTriangle { public ArrayList<ArrayList<Integer>> generate(int numRows) { ArrayList<ArrayList<Integer>> all = new ArrayList<ArrayList<Integer>>(); if(numRows<1)return all; // put the first ArrayList<Integer> al = new ArrayList<Integer>(); al.add(1); all.add(al); for(int i = 0;i<numRows - 1 ; i++){ al = all.get(i ); ArrayList<Integer> newAl = new ArrayList<Integer>(); for(int j = 0; j<al.size() -1;j++){ newAl.add(al.get(j)+al.get(j+1)); } newAl.add(0,1); newAl.add(1); all.add(newAl); } return all; } }
NOTE:
当numRow==0, 返回不应该是null,而是应该empty 的all 对象。
----------2nd pass------------
public class PascalsTriangle { public List<List<Integer>> generate(int numRows) { List<List<Integer>> all = new LinkedList(); for(int i =0;i < numRows; i++){ List<Integer> list = new LinkedList(); list.add(1); for(int j = 0;j < i-1;j++) list.add(all.get(i-1).get(j) + all.get(i-1).get(j+1)); if(i>0) list.add(1); all.add(list); } return all; } }Mistakes:
这里,j < i-1 开始考虑到i为index,因此没有减一。 导致了 j+1会 Out of bound
No comments:
Post a Comment