leetcode：119. 杨辉三角 II

题目

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
[简单] 119. 杨辉三角 II - 图1

示例：

  1. 输入: rowIndex = 3
  2. 输出: [1,3,3,1]
  1. 输入: rowIndex = 0
  2. 输出: [1]
  1. 输入: rowIndex = 1
  2. 输出: [1,1]

解答 & 代码

递推，逐行计算：
设 **result[i][j]** 代表杨辉三角第 **i** 行的第 **j** 个数

  • result[i][j] = result[i - 1][j - 1] + result[i - 1][j]，当 1 <= j <= i - 1
  • result[i][0] = result[i][i] = 1，即每行的最左端和最右端等于 1

由于计算每行的第 j 个数都只和前一行有关，因此可以压缩到一维数组 result，**result[j]** 代表当前行的第 **j** 个元素的值

  • 当 **1 <= j <= i - 1**：**result[j] = result[j - 1] + result[j]**
    • 注意：每一行应该倒序遍历！！！因为原本 result[i][j] 和上一行的前一个元素 result[i - 1][j - 1] 有关，压缩为一维数组后，如果正序遍历，那么上一行的第 j - 1 个元素就已经被当前行的第 j - 1 个元素覆盖了

  • **result[0] = result[i] = 1**，即每行的最左端和最右端等于 1

    1. class Solution {
    2. public:
    3.   vector<int> getRow(int rowIndex) {
    4.       int len = rowIndex + 1;            // 第 rowIndex 行的元素个数
    5.       // result[j] 代表当前行的第 j 个元素的值
    6.       vector<int> result(len, 1);        // 结果数组，全部初始化为 1（因为每行的两端都为 1）
    7.       // 递推
    8.       for(int i = 2; i <= rowIndex; ++i)        // 遍历行
    9.       {
    10.           for(int j = i - 1; j >= 1; --j)        // 逆序遍历列
    11.               result[j] = result[j - 1] + result[j];
    12.       }
    13.       return result;
    14.   }
    15. };

    复杂度分析：设要返回第 rowIndex 行

  • 时间复杂度[简单] 119. 杨辉三角 II - 图2：

  • 空间复杂度 O(1)：结果数组的空间复杂度不计入

执行结果：

  1. 执行结果：通过
  3. 执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
  4. 内存消耗：6.1 MB, 在所有 C++ 提交中击败了 87.56% 的用户