LeetCode:Pascal's Triangle I II

时间:2022-07-10 05:36:30

LeetCode:Pascal's Triangle

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;
}
};

LeetCode:Pascal's Triangle II

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