118 Pascal's Triangle

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

Lesson Learned:

• Construct a List of List

List<List<Integer>> list = new ArrayList<List<Integer>>();

list.add(new ArrayList<Integer>())

http://stackoverflow.com/questions/24796273/incompatible-types-list-of-list-and-arraylist-of-arraylist http://docs.oracle.com/javase/tutorial/java/generics/inheritance.html

The reason is that generics are not covariant.

Consider simpler case:

    List<Integer> integers = new ArrayList<Integer>();
    List<Number> numbers = integers; // cannot do this
    numbers.add(new Float(1337.44));
Now List holds a Float, which is certainly bad.

Same for your case.

    List<ArrayList<Integer>> al = new ArrayList<ArrayList<Integer>>();
    List<List<Integer>> ll = al; // cannot do this
    ll.add(new LinkedList<Integer>())
Now you have a list ll which holds LinkedList, but the al is declared as a List of ArrayLists.





public class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> tri = new ArrayList<List<Integer>>();

        for (int i = 0; i < numRows; i++) {
            tri.add(new ArrayList<Integer>());  //
            for (int j = 0; j < i + 1; j++) {
                if (j == 0 || j == i) {
                    tri.get(i).add(1);
                } else {
                    tri.get(i).add(tri.get(i-1).get(j-1) + tri.get(i-1).get(j));
                }
            }
        }
        return tri;
    }
}