【C++刷题】力扣-#119-杨辉三角II
题目描述
给定一个非负整数 rowIndex，返回杨辉三角的第 rowIndex 行。杨辉三角中的每一行的数字是它正上方两个数字的和。
示例
示例 1:
输入: rowIndex = 3
输出: [1,3,3,1]
示例 2:
输入: rowIndex = 0
输出: [1]
示例 3:
输入: rowIndex = 1
输出: [1,1]
题解
这个问题可以通过动态规划来解决。我们可以使用一个一维数组来存储当前行的值，然后根据上一行计算当前行的值。
- 初始化：如果 rowIndex 为 0，返回只有一个元素 [1] 的列表。
- 构建杨辉三角的当前行：创建一个列表 row，长度为 rowIndex + 1，初始值都为 1。
- 计算中间值：对于 row 中的每个位置 j（从 1 到 rowIndex - 1），计算 row[j] 的值为上一行的 row[j - 1] 和 row[j] 的和。
- 返回结果：返回 row。
代码实现
vector<int> getRow(int rowIndex) {
vector<int> row(rowIndex + 1, 1);
for (int i = 1; i < rowIndex; i++) {
for (int j = i; j > 0; j--) {
row[j] += row[j - 1];
}
}
return row;
}
复杂度分析
● 时间复杂度：O(rowIndex^2)，因为我们需要计算每一行的每个数字，每个数字的计算时间是 O(1)。
● 空间复杂度：O(rowIndex)，因为我们需要存储当前行的值。
这个算法的优势在于它直接模拟了杨辉三角的构建过程，不需要额外的数学计算。