Friday, September 20, 2013

Triangle

Q:
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