pascal's triangle I II

pascal's triangle I II

I easy problem

 1 class Solution {
 2 public:
 3     vector<vector<int> > generate(int numRows) {
 4         vector< vector< int > > result;
 5         result.clear();
 6         if ( 0 == numRows ) {
 7             return result;
 8         }
 9         vector< int > t;
10         t.push_back(1);
11         result.push_back(t);
12         for ( int i = 1; i < numRows; i++ ) {
13             t.clear();
14             t.push_back(1);
15             for ( int j = 1; j <= i-1; j++ ) {
16                 t.push_back(result[i-1][j-1]+result[i-1][j]);
17             }
18             t.push_back(1);
19             result.push_back(t);
20         }
21         return result;
22     }
23 };

II not hard too

Time complexity O(n*n), and sapce complexity O(n). It is rowIndex, not rowNumber...

 1 class Solution {
 2 public:
 3     vector<int> getRow(int rowIndex) {
 4         vector<int > result;
 5         result.clear();
 6         if ( 0 > rowIndex )  {
 7             return result;
 8         }
 9         result.push_back(1);
10         for ( int i = 1; i <= rowIndex; i++ ) {
11             int pre = result[0];
12             for ( int j = 1; j < i; j++ ) {
13                 int t = result[j];
14                 result[j] += pre;
15                 pre = t;
16             }
17             result.push_back(1);
18         }
19         return result;
20     }
21 };

Loading Disqus comments...
Table of Contents