Given numRows, generate the first numRows of Pascal's triangle.
For example, given numRows = 5,
Return
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
分析:简单的模拟从第一层开始计算即可
class Solution {
public:
vector<vector<int> > generate(int numRows) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
vector<vector<int> >res;
if(numRows == )return res;
res.push_back(vector<int>{});
if(numRows == )return res;
vector<int>tmp;
tmp.reserve(numRows);
for(int i = ; i <= numRows; i++)
{
tmp.clear();
tmp.push_back();
for(int j = ; j < i-; j++)
tmp.push_back(res[i-][j-]+res[i-][j]);
tmp.push_back();
res.push_back(tmp);
}
return res;
}
};
Given an index k, return the kth row of the Pascal's triangle.
For example, given k = 3,
Return [1,3,3,1]
.
Note:
Could you optimize your algorithm to use only O(k) extra space?
分析:每次计算只和上一层有关系,因此只需要一个数组空间就可以 本文地址
class Solution {
public:
vector<int> getRow(int rowIndex) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
vector<int> res(rowIndex+,);
if(rowIndex == )return res;
for(int i = ; i <= rowIndex; i++)
{
int tmp = res[];
for(int j = ; j <= i-; j++)
{
int kk = res[j];
res[j] = tmp+res[j];
tmp = kk;
}
}
return res;
}
};
【版权声明】转载请注明出处:http://www.cnblogs.com/TenosDoIt/p/3436562.html