Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle.
Example: Input: 5 Output: [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]
Solution analysis:
In each row, the first and last element are 1. And the other element is the sum of the two elements in the previous row. e.g.
1 3 3 1 Previous row
1 1+3 3+3 3+1 1 Next row
1 4 6 4 1 Previous row
1 1+4 4+6 6+4 4+1 1 Next row
Hence this problem can be solved directly as shown in the code below:
Solution in C++
#include<iostream> #include<string> #include<vector> using namespace std; vector<vector<int>> generate(int numRows) { vector<vector<int>> result; for(auto i=0;i<numRows;++i) { result.push_back(vector<int>(i+1,1)); for(auto j=1; j<i; ++j) { result[i][j] = result[i-1][j-1] + result[i-1][j]; } } return result; } int main() { int numRows = 4; vector<vector<int> > result = generate (numRows); for (int i = 0; i < result.size(); i++) { for (int j = 0; j < result[i].size(); j++) { cout<< result[i][j]<<" "; } cout<<endl; } }
Output:
1 1 1 1 2 1 1 3 3 1
No Responses