Pascal's Triangle @LeetCode

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

	package leetcode;
	import java.util.ArrayList;
	/**
	* Solution: Classic Problem. just add layer by layer. use another list to receive last layer.
	* Add first layer, and then start from i = 1 make it easier.
	* @author jeffwan
	* @date Apr 3, 2014
	*/
	public class PascalTriangle {
	// use ArrayList operation directly. Space O(n^2)
	public ArrayList<ArrayList<Integer>> generate(int numRows) {
	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	if (numRows <= 0) {
	return result;
	}
	ArrayList<Integer> first = new ArrayList<Integer>();
	first.add(1);
	result.add(first);
	for (int i = 1; i < numRows; i++) {
	ArrayList<Integer> line = new ArrayList<Integer>(i + 1);
	ArrayList<Integer> prev = result.get(i - 1);
	// Initialize
	for (int j = 0; j < i + 1; j++) {
	line.add(-1);
	}
	// head and tail = 1
	line.set(0, 1);
	line.set(i, 1);
	for (int j = 1; j < i; j++) {
	line.set(j, prev.get(j - 1) + prev.get(j));
	}
	result.add(line);
	}
	return result;
	}
	// My version -- use matrix for easy operation. Extra space O(n^2)
	public ArrayList<ArrayList<Integer>> generate2(int numRows) {
	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	if (numRows <= 0) {
	return result;
	}
	int[][] matrix = new int[numRows][];
	for (int i = 0; i < numRows; i++) {
	matrix[i] = new int[i+1];
	int length = matrix[i].length;
	for (int j = 0; j < length; j++) {
	// Valuation
	if (j == 0 || j == length - 1) {
	matrix[i][j] = 1;
	} else {
	matrix[i][j] = matrix[i-1][j-1] + matrix[i-1][j];
	}
	}
	}
	// Copy matrix to ArrayList
	for (int i = 0; i < numRows; i++) {
	ArrayList<Integer> line = new ArrayList<Integer>();
	for (int j = 0; j < matrix[i].length; j++) {
	line.add(matrix[i][j]);
	}
	result.add(line);
	}
	return result;
	}
	}

view raw PascalTriangle.java hosted with ❤ by GitHub