runnig

[leetcode] 118 Pascal Triangle c++

Feb 3rd, 2013
139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.92 KB | None | 0 0
  1. /*
  2. http://leetcode.com/onlinejudge#question_118
  3.  
  4. Given numRows, generate the first numRows of Pascal's triangle.
  5.  
  6. For example, given numRows = 5,
  7. Return
  8.  
  9. [
  10.      [1],
  11.     [1,1],
  12.    [1,2,1],
  13.   [1,3,3,1],
  14.  [1,4,6,4,1]
  15. ]
  16.  
  17. */
  18. class Solution {
  19. public:
  20.     vector<vector<int> > generate(int numRows) {
  21.         typedef vector<int> row_t;
  22.         typedef vector<row_t> tri_t;
  23.        
  24.         tri_t tri;
  25.        
  26.         for(size_t row_no = 0; row_no < numRows; ++row_no)
  27.         {
  28.             const size_t row_size = row_no + 1;
  29.                        
  30.             tri.push_back(row_t(row_size));
  31.             tri[row_no][0] = tri[row_no][row_no] = 1;
  32.            
  33.             for(size_t pos = 1; pos < row_no; ++pos)
  34.             {
  35.                 tri[row_no][pos] =
  36.                     tri[row_no-1][pos-1] + tri[row_no-1][pos];
  37.             }
  38.            
  39.         }
  40.        
  41.         return tri;
  42.     }
  43. };
Advertisement
Add Comment
Please, Sign In to add comment