LeetCode: pascal's Triangle

LeetCode: pascal's Triangle

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

地址：https://oj.leetcode.com/problems/pascals-triangle/

算法：pascal's triangle的特点是第i+1行第j个元素为第i行第j个元素和第j-1个元素的和，当然头尾两个元素要特殊处理。掌握这个特点，写出代码应该不难：

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

第二题：

Given an index k, return the k^th row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

地址：https://oj.leetcode.com/problems/pascals-triangle-ii/

算法：要产生第k行的数组必须先产生第k-1行数组，但跟第k-2行的数组完全无关，所以可以用上一篇文章的方法来达到空间上的限制，而产生数组的方式跟第一题的方法一样。代码：

 1 class Solution {
 2 public:
 3     vector<int> getRow(int rowIndex) {
 4         if(rowIndex < 0)    return vector<int>();
 5         if(rowIndex == 0)   return vector<int>(1,1);
 6         vector<int> result1(rowIndex+1);
 7         vector<int> result2(rowIndex+1);
 8         result1[0] = 1;
 9         vector<int> *pre = &result1;
10         vector<int> *p   = &result2;
11         for(int i = 1; i <= rowIndex; ++i){
12             (*p)[0] = 1;
13             (*p)[i] = 1;
14             for(int j = 1; j < i; ++j){
15                 (*p)[j] = (*pre)[j] + (*pre)[j-1];
16             }
17             vector<int> *temp = pre;
18             pre = p;
19             p = temp;
20         }
21         return *pre;
22     }
23 };