118. pascal’s triangle

Question

Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle.

Analysis

除了0 和 i位固定为1,

其他位置

  • triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j-1]

Complexity

Time: O(n)

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> triangle = new ArrayList<>();
if (numRows <= 0){
return triangle;
}
for (int i = 0; i < numRows; i++) {
List<Integer> row = new ArrayList<>();
for (int j = 0; j < i + 1; j++) {
if (j == 0 || j == i) {
row.add(1);
} else {
row.add(triangle.get(i-1).get(j-1) + triangle.get(i-1).get(j));
}
}
triangle.add(row);
}
return triangle;
}