[LeetCode] Pascal's Triangle I, II

Pascal's Triangle I

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]
]

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].

思路：

I, II都是简单题，可以递归构建，也可以循环构建。但效率最高的是利用滚动数组，避免反复申明向量，并且只需要O(k)额外内存空间。

Pascal's Triangle I

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

class Solution { public: vector<vector<int> > generate(int numRows) { vector<vector<int>> res; if(numRows<1) return res; vector<int> row(1,1); res.push_back(row); for(int i=2; i<=numRows; i++) { int prev = 1; for(int j=1; j<i-1; j++) { int temp = row[j]; row[j] += prev; prev = temp; } row.push_back(1); res.push_back(row); } return res; } };

Pascal's Triangle II

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

class Solution { public: vector<int> getRow(int rowIndex) { vector<int> row(rowIndex+1,1); for(int i=1; i<=rowIndex; i++) { int prev = 1; for(int j=1; j<i; j++) { int temp = row[j]; row[j] += prev; prev = temp; } } return row; } };