LeetCode-hot-100杨辉三角
目录
LeetCode hot 100—杨辉三角
题目
给定一个非负整数
numRows
，
生成「杨辉三角」的前
numRows
行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例
示例 1:
输入: numRows = 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]示例 2:
输入: numRows = 1 输出: [[1]]
分析
数学构造法
首先创建一个二维向量
triangle
用于存储杨辉三角的每一行。
杨辉三角的第一行只有一个元素
1
，将其添加到
triangle
中。
从第二行开始，使用
for
循环逐行生成。对于每一行，先创建一个长度为
i + 1
的向量
row
，并将其首尾元素初始化为
1
。然后，使用内层
for
循环计算中间元素的值，每个中间元素等于上一行相邻两个元素之和。最后，将生成的行添加到
triangle
中。
时间复杂度：O(
)
空间复杂度：O(1)
class Solution {
public:
std::vector<std::vector<int>> generate(int numRows) {
std::vector<std::vector<int>> triangle;
if (numRows == 0) return triangle;
// 第一行
triangle.push_back({1});
for (int i = 1; i < numRows; ++i) {
std::vector<int> row(i + 1, 1);
for (int j = 1; j < i; ++j) {
row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
}
triangle.push_back(row);
}
return triangle;
}
};