Pascal's Triangle II

描述

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?

分析

滚动数组。

代码

  1. // Pascal's Triangle II
  2. // 滚动数组，时间复杂度O(n^2)，空间复杂度O(n)
  3. public class Solution {
  4.     public List<Integer> getRow(int rowIndex) {
  5.         List<Integer> array = new ArrayList<>();
  6.         for (int i = 0; i <= rowIndex; i++) {
  7.             for (int j = i - 1; j > 0; j--){
  8.                 array.set(j, array.get(j - 1) + array.get(j));
  9.             }
  10.             array.add(1);
  11.         }
  12.         return array;
  13.     }
  14. }
  1. // LeetCode, Pascal's Triangle II
  2. // 滚动数组，时间复杂度O(n^2)，空间复杂度O(n)
  3. class Solution {
  4. public:
  5.     vector<int> getRow(int rowIndex) {
  6.         vector<int> array;
  7.         for (int i = 0; i <= rowIndex; i++) {
  8.             for (int j = i - 1; j > 0; j--){
  9.                 array[j] = array[j - 1] + array[j];
  10.             }
  11.             array.push_back(1);
  12.         }
  13.         return array;
  14.     }
  15. };

相关题目

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