Pascal’s Triangle

Given numRows, generate the first numRows of Pascal’s triangle.

For example, given numRows = 5,
Return

  1. [
  2.      [1],
  3.     [1,1],
  4.    [1,2,1],
  5.   [1,3,3,1],
  6.  [1,4,6,4,1]
  7. ]

要得到一个帕斯卡三角，我们只需要找到规律即可。

  • 第k层有k个元素
  • 每层第一个以及最后一个元素值为1
  • 对于第k（k > 2）层第n（n > 1 && n < k）个元素A[k][n]，A[k][n] = A[k-1][n-1] + A[k-1][n]

知道了上面的规律，就很好做了，我们使用一个二维数组来存储整个三角，代码如下：

  1. class Solution {
  2. public:
  3.     vector<vector<int> > generate(int numRows) {
  4.         vector<vector<int> > vals;
  5.         vals.resize(numRows);
  7.         for(int i = 0; i < numRows; i++) {
  8.             vals[i].resize(i + 1);
  9.             vals[i][0] = 1;
  10.             vals[i][vals[i].size() - 1] = 1;
  11.             for(int j = 1; j < vals[i].size() - 1; j++) {
  12.                 vals[i][j] = vals[i - 1][j - 1] + vals[i - 1][j];
  13.             }
  14.         }
  16.         return vals;
  17.     }
  18. };

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

不同于上一题，这里我们仅仅需要得到的第k层的集合，但只能使用O(k)的空间。所以不能用前面二维数组的方式，只能使用一位数组滚动计算。

在第一题里面，我们知道，帕斯卡三角的计算公式是这样的，A[k][n] = A[k-1][n-1] + A[k-1][n]。

假设现在数组存放的第3层的数据，[1, 3, 3, 1]，如果我们需要计算第4层的数据，如果我们从前往后计算，譬如A[4][2]= A[3][1] + A[3][2]，也就是4，但是因为只有一个数组，所以需要将4这个值覆盖到2这个位置，那么我们计算A[4][3]的时候就会出现问题了，因为这时候A[3][2]不是3，而是4了。

为了解决这个问题，我们只能从后往前计算，仍然是上面那个例子，我们实现计算A[4][3] = A[3][2] + A[3][3]，也就是6，我们将6直接覆盖到3这个位置，但不会影响我们计算A[4][2]，因为A[4][2] = A[3][1] + A[3][2]，已经不会涉及到3这个位置了。

理解了如何计算，代码就很简单了：

  1. class Solution {
  2. public:
  3.     vector<int> getRow(int rowIndex) {
  4.         vector<int> vals;
  6.         vals.resize(rowIndex + 1, 1);
  8.         for(int i = 0; i < rowIndex + 1; ++i) {
  9.             for(int j = i - 1; j >= 1; --j) {
  10.                 vals[j] = vals[j] + vals[j - 1];
  11.             }
  13.         }
  15.         return vals;
  16.     }
  17. };