题目
给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: rowIndex = 3
输出: [1,3,3,1]示例 2:
输入: rowIndex = 0
输出: [1]示例 3:
输入: rowIndex = 1
输出: [1,1]提示:
0 <= rowIndex <= 33
进阶：
你可以优化你的算法到 *O*(*rowIndex*) 空间复杂度吗？
解答
- 得到33行的所有结果，再按照要求返回对应的行的数组
得到33行的结果的代码可以直接从leetcode118里复制粘贴，最后只需要修改一下return的值就行，需要返回的是result数组里需要的那一行的结果数组。
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<vector<int>> results; // 初始化结果数组
for (int i = 0; i < 34; i++) { // 按行进行遍历
// i是当前行号
vector<int > temp_arr(i+1, 1); // 初始化temp_arr数组用于暂时存储每行的数字
for (int j = 0; j <= i; j++) { // 每行的元素等于每行的行号，行号从0开始，所以j <= i
int temp = -1; // 用temp存储一行里单个元素的临时值
if (j == 0 || j == i || i == 1) { // 如果遍历到了这一行的第一个元素或者最后一个元素，或者现在在遍历第一行
continue; // 此时无需赋值，因为temp_arr在初始化的时候给所有元素都是1的值
}
else {
temp_arr[j] = results[i-1][j-1] + results[i-1][j]; // 否则该行元素就是它左上方和右上方的数的和
}
}
results.push_back(temp_arr); // 将遍历完这一行的结果push进最终的结果数组
}
return results[rowIndex];// 返回结果数组
}
};- 空间复杂度优化
本题要求生成杨辉三角的第 rowIndex 行，其中第 i 行有 i+1 个数，即第一行有 1 个数，第二行有 2 个数，第三行有 3 个数，以此类推。
因为杨辉三角的每一行只依赖于上一行的值，所以我们可以只存储上一行的值，不断地更新，直到得到第 rowIndex 行为止。
我们可以用一个一维数组来存储上一行的值，并不断地更新数组中的值，最终得到第 rowIndex 行的值。在更新的过程中，我们需要注意到数组的下标从 0 开始，而杨辉三角每一行的第一个数和最后一个数都是 1，所以我们需要在数组的第一个位置和最后一个位置都赋值为 1。
由于本题要求空间复杂度为 O(rowIndex)，因此我们不能开辟二维数组。在更新数组中的值时，我们需要用到上一行中前面的数和当前行中前面的数，因此我们需要用一个变量 pre 来存储上一行中前面的数，并在更新数组中的值时更新 pre 的值。
时间复杂度为 O(rowIndex^2)，空间复杂度为 O(rowIndex)。
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> res(rowIndex + 1, 1); // 初始化结果数组为全 1
for (int i = 2; i <= rowIndex; ++i) { // 从第 2 行开始更新
int pre = res[0]; // 存储上一行前面的数
for (int j = 1; j < i; ++j) {
int temp = res[j]; // 保存当前位置的值
res[j] += pre; // 更新当前位置的值
pre = temp; // 更新 pre
}
}
return res;
}
};在上述代码中，我们用 res 数组存储上一行的值，并初始化为全 1。然后从第 2 行开始更新，用变量 pre 存储上一行前面的数，并在更新数组中的值时更新 pre 的值。最终返回更新后的结果数组即可。
由于题目要求返回的是第 rowIndex 行，因此数组的大小应该为 rowIndex + 1。