title: Pascals Triangle
tags:
- pascals-triangle
- No.118
- simple
- discrete-mathematics
Description
Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.
img
In Pascal's triangle, each number is the sum of the two numbers directly above it.
Example:
Input: 5
Output:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
Corner Cases
0
Solutions
Naive
The naive way. Running time is 1 + 2 + 3 + \cdots + n = \frac{n^2 + n}{2} = O(n^2)
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> llst = new LinkedList<List<Integer>>();
if (numRows == 0) {return llst;}
List<Integer> l0 = new LinkedList<Integer>();
List<Integer> last = l0;
l0.add(1);
llst.add(l0);
for (int i=1; i<numRows; i++) {
List<Integer> li = new LinkedList<Integer>();
li.add(1);
for (int j=1; j<i; j++) {
li.add(last.get(j-1) + last.get(j));
}
li.add(1);
llst.add(li);
last = li;
}
return llst;
}
}
