118 Pascal's Triangle
Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.
Input: 5
Output:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> ans = new ArrayList<>();
if (numRows == 0) {
return ans;
}
for (int i = 0; i < numRows; i++) {
ans.add(new ArrayList<>());
}
ans.get(0).add(1);
for (int i = 1; i < numRows; i++) {
List<Integer> prev = ans.get(i - 1);
List<Integer> sub = ans.get(i);
for(int j = 0; j <= i; j++) {
if (j == 0 || j == i) {
sub.add(1);
}else {
int num = prev.get(j - 1) + prev.get(j);
sub.add(num);
}
}
}
return ans;
}
}
Edward method
time : O(n^2)
space : O(n)
* @param numRows
* @return
*/
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < numRows; i++) {
list.add(0, 1);
for (int j = 1; j < list.size() - 1; j++) {
list.set(j, list.get(j) + list.get(j + 1));
}
res.add(new ArrayList<>(list));
}
return res;
}