118. 杨辉三角
题目描述
输入一个整数 numRows，生成杨辉三角最上面的 numRows 行。
杨辉三角第一行只有一个 1。之后每一行比上一行多一个数，首尾都是 1，中间每个数等于上一行中位于它左上和右上的两个数之和。
按从上到下的顺序返回这些行，每行是一个整数列表。
示例 1
输入：numRows = 5 输出：[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
解释：例如第 5 行中间的 6 来自上一行的 3 + 3。
示例 2
输入：numRows = 1 输出：[[1]]
解释：只需第一行 [1]。
数据范围
1 <= numRows <= 30
解题思路
每行首尾为 1，中间元素由上一行相邻两数相加得到。
为什么正确
生成新行前，triangle 中的每一行都已满足组合数递推。
复杂度分析
时间和空间均为 O(numRows²)。
易错点
更新一维行时要从右向左；本实现每次新建行，因此不会覆盖上一行。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
from typing import List
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
triangle = []
for r in range(numRows):
row = [1] * (r + 1)
for j in range(1, r):
row[j] = triangle[r - 1][j - 1] + triangle[r - 1][j]
triangle.append(row)
return triangleclass Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> triangle = new ArrayList<>();
for (int r = 0; r < numRows; r++) {
List<Integer> row = new ArrayList<>(Collections.nCopies(r + 1, 1));
for (int j = 1; j < r; j++)
row.set(j, triangle.get(r - 1).get(j - 1) + triangle.get(r - 1).get(j));
triangle.add(row);
}
return triangle;
}
}class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> triangle;
for (int r = 0; r < numRows; r++) {
vector<int> row(r + 1, 1);
for (int j = 1; j < r; j++)
row[j] = triangle[r - 1][j - 1] + triangle[r - 1][j];
triangle.push_back(row);
}
return triangle;
}
};func generate(numRows int) [][]int {
triangle := [][]int{}
for r := 0; r < numRows; r++ {
row := make([]int, r+1)
for j := range row {
row[j] = 1
}
for j := 1; j < r; j++ {
row[j] = triangle[r-1][j-1] + triangle[r-1][j]
}
triangle = append(triangle, row)
}
return triangle
}var generate = function(numRows) {
const triangle = [];
for (let r = 0; r < numRows; r++) {
const row = Array(r + 1).fill(1);
for (let j = 1; j < r; j++)
row[j] = triangle[r - 1][j - 1] + triangle[r - 1][j];
triangle.push(row);
}
return triangle;
};function generate(numRows: number): number[][] {
const triangle: number[][] = [];
for (let r = 0; r < numRows; r++) {
const row: number[] = Array(r + 1).fill(1);
for (let j = 1; j < r; j++)
row[j] = triangle[r - 1][j - 1] + triangle[r - 1][j];
triangle.push(row);
}
return triangle;
};