方法1:数学方法
时间复杂度:$O(numRows^2)$
空间复杂度:$O(1)$
空间复杂度是用来描述算法在执行过程中所需要的额外空间,通常不考虑函数的返回值所占用的空间,是因为这个返回值的空间是在函数执行完毕之后才被分配的,而不是在函数执行过程中需要的额外空间。
在实际的编程中,函数的返回值的空间占用通常是由调用者分配的,因此在计算算法的空间复杂度时,不应该考虑这部分空间占用。
当然,如果函数的返回值在算法执行过程中所需的空间非常大,可能会对算法的空间复杂度产生影响,这时需要对具体情况具体分析。但一般情况下,我们并不考虑函数的返回值所占用的空间。
解题思路
见官方解析。
Java 代码
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> list = new ArrayList<>();
for (int i = 0; i < numRows; i++) {
List<Integer> row = new ArrayList<>();
for (int j = 0; j <= i; j++){
if (j == 0 || j == i) {
row.add(1);
} else {
row.add(list.get(i - 1).get(j - 1) + list.get(i - 1).get(j));
}
}
list.add(row);
}
return list;
}
}