版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/SunnyYoona/article/details/43562277
题目
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]
]
思路
模拟
代码
/**------------------------------------
* 日期:2015-02-06
* 作者:SJF0115
* 题目: 118.Pascal's Triangle
* 网址:https://oj.leetcode.com/problems/pascals-triangle/
* 结果:AC
* 来源:LeetCode
* 博客:
---------------------------------------**/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int> > generate(int numRows) {
vector<int> row;
vector<vector<int> > triangle;
if(numRows >= 1){
row.push_back(1);
triangle.push_back(row);
}//if
if(numRows >= 2){
row.push_back(1);
triangle.push_back(row);
}//if
for(int i = 2;i < numRows;++i){
row.clear();
row.push_back(1);
for(int j = 1;j < i;++j){
row.push_back(triangle[i-1][j-1]+triangle[i-1][j]);
}//for
row.push_back(1);
triangle.push_back(row);
}//for
return triangle;
}
};
int main(){
Solution s;
int n = 5;
vector<vector<int> > result = s.generate(n);
// 输出
for(int i = 0;i < result.size();++i){
for(int j = 0;j < result[i].size();j++){
cout<<result[i][j]<<" ";
}//for
cout<<endl;
}//for
return 0;
}
运行时间
思路二
/**------------------------------------
* 日期:2015-02-06
* 作者:SJF0115
* 题目: 118.Pascal's Triangle
* 网址:https://oj.leetcode.com/problems/pascals-triangle/
* 结果:AC
* 来源:LeetCode
* 博客:
---------------------------------------**/
class Solution {
public:
vector<vector<int> > generate(int numRows) {
vector<vector<int>> triangle(numRows);
for (int i = 0;i < numRows;++i) {
triangle[i].resize(i + 1);
triangle[i][0] = triangle[i][i] = 1;
for (int j = 1;j < i;++j) {
triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
}//for
}//for
return triangle;
}
};
运行时间