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

分析

本题可以用队列，计算下一行时，给上一行左右各加一个0，然后下一行的每个元素，就等于左上角和右上角之和。

另一种思路，下一行第一个元素和最后一个元素赋值为1，中间的每个元素，等于上一行的左上角和右上角元素之和。

从左到右

  1. // LeetCode, Pascal's Triangle
  2. // 时间复杂度O(n^2)，空间复杂度O(n)
  3. class Solution {
  4. public:
  5.     vector<vector<int> > generate(int numRows) {
  6.         vector<vector<int> > result;
  7.         if(numRows == 0) return result;
  9.         result.push_back(vector<int>(1,1)); //first row
  11.         for(int i = 2; i <= numRows; ++i) {
  12.             vector<int> current(i,1);  // 本行
  13.             const vector<int> &prev = result[i-2];  // 上一行
  15.             for(int j = 1; j < i - 1; ++j) {
  16.                 current[j] = prev[j-1] + prev[j]; // 左上角和右上角之和
  17.             }
  18.             result.push_back(current);
  19.         }
  20.         return result;
  21.     }
  22. };

从右到左

  1. // LeetCode, Pascal's Triangle
  2. // 时间复杂度O(n^2)，空间复杂度O(n)
  3. class Solution {
  4. public:
  5.     vector<vector<int> > generate(int numRows) {
  6.         vector<vector<int> > result;
  7.         vector<int> array;
  8.         for (int i = 1; i <= numRows; i++) {
  9.             for (int j = i - 2; j > 0; j--) {
  10.                 array[j] = array[j - 1] + array[j];
  11.             }
  12.             array.push_back(1);
  13.             result.push_back(array);
  14.         }
  15.         return result;
  16.     }
  17. };

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/simulation/pascal-s-triangle.html