杨辉三角
题目描述
给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。
示例 1:
输入: 3
输出: [1,3,3,1]
进阶:
你可以优化你的算法到 O(k) 空间复杂度吗？
思路1
初始化前两层，后面层直接累加左上方和右上方的数的和
代码实现
class Solution {
public:
//思路：初始化前两层，后面层直接累加左上方和右上方的数的和
vector<vector<int>> generate(int numRows) {
vector<vector<int>> result(numRows);
if(numRows == 0){ return result;}
else if(numRows == 1)
{
result[0].push_back(1);
return result;
}
else if(numRows == 2)
{
result[0].push_back(1);
result[1].push_back(1);
result[1].push_back(1);
return result;
}
else{
result[0].push_back(1);
result[1].push_back(1);
result[1].push_back(1);
for(int i = 2; i < numRows; ++i)
{
for(int j = 0; j <= i; ++j)
{
if(j == 0){result[i].push_back(1);}
else if(j == i){result[i].push_back(1);}
else{
//cout<<" "<<result[i-1][j-1]<<" "<<result[i-1][j]<<endl;
int tmp = result[i-1][j-1] + result[i-1][j];
result[i].push_back(tmp);
}
}
}
}
return result;
}
};
思路2
进阶，空间复杂度O(K),因为要使用O(K)的空间复杂度，所以创建rowIndex + 1个元素的数组，因为第rowIndex行有rowIndex + 1个元素从第1行开始计算直到rowIndex层，每一层计算该层具体数值，需要注意从后往前计算，避免了第i-1行计算结果被覆盖丢失
代码实现
class Solution {
public:
//思路：因为要使用O(K)的空间复杂度，所以创建rowIndex + 1个元素的数组，因为第rowIndex行有rowIndex + 1个元素
//从第1行开始计算直到rowIndex层，每一层计算该层具体数值，需要注意从后往前计算，避免了第i-1行计算结果被覆盖丢失
vector<int> getRow(int rowIndex) {
vector<int> result(rowIndex + 1,0);
result[0] = 1;
for(int i = 1; i <= rowIndex; ++i){//表示第i行
for(int k = i; k > 0; --k){//k是第k个数 从i开始，是因为第i行共有i+1个数字，从后往前计算，避免了第i-1行计算结果被覆盖丢失
result[k] = result[k] + result[k-1];
}
}
return result;
}
};