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. // Pascal's Triangle
  2. // 时间复杂度O(n^2)，空间复杂度O(n)
  3. public class Solution {
  4.     public List<List<Integer>> generate(int numRows) {
  5.         List<List<Integer>> result = new ArrayList<>();
  6.         if(numRows == 0) return result;
  8.         result.add(new ArrayList<>(Arrays.asList(1))); //first row
  10.         for(int i = 2; i <= numRows; ++i) {
  11.             Integer[] current = new Integer[i]; // 本行
  12.             Arrays.fill(current, 1);
  13.             List<Integer> prev = result.get(i - 2); // 上一行
  15.             for(int j = 1; j < i - 1; ++j) {
  16.                 current[j] = prev.get(j-1) + prev.get(j); // 左上角和右上角之和
  17.             }
  18.             result.add(new ArrayList<>(Arrays.asList(current)));
  19.         }
  20.         return result;
  21.     }
  22. }

从右到左

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

相关题目

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