LeetCode 题目 119：杨辉三角 II

作者介绍：10年大厂数据\经营分析经验，现任字节跳动数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python，欢迎探讨交流
欢迎加入社区：码上找工作
作者专栏每日更新：
LeetCode解锁1000题: 打怪升级之旅
python数据分析可视化：企业实战案例
漫画版算法详解
python源码解读
程序员必备的数学知识与应用

题目描述

给定一个非负索引 rowIndex，返回杨辉三角的第 rowIndex 行。在这里，rowIndex 从 0 开始。

此题与生成杨辉三角的完整图形略有不同，要求的是能够直接计算出杨辉三角的某一特定行。因此，优化算法的空间复杂度是关键。

方法一：线性迭代

解题步骤：

1. 初始化结果列表为 [1]。
2. 使用迭代方法更新列表，以模拟杨辉三角的每一行的计算。
3. 对于每一行，从后向前更新，利用上一行的值计算当前行的值，避免前值被提前覆盖。

Python 代码示例

def getRow(rowIndex):
    row = [1] * (rowIndex + 1)
    for i in range(2, rowIndex + 1):
        for j in range(i - 1, 0, -1):
            row[j] += row[j - 1]
    return row

方法一使用线性迭代的方式计算杨辉三角的特定一行，这里通过 ASCII 图形来展示这个方法的工作过程，特别是如何迭代更新列表元素来模拟杨辉三角中的每一行的构建。

杨辉三角的特定行构建过程：线性迭代

假设我们需要计算杨辉三角的第5行（rowIndex = 4，从0开始计数）。

初始状态

1. 初始化包含单个元素1的列表，代表杨辉三角的第0行。

[1]

第1行

2. 迭代更新，添加一个1，现在列表代表第1行。

[1, 1]

第2行

3. 开始第一个真正的迭代，将列表更新为第2行。先复制前一个元素，然后从后向前更新每个元素（除了第一个和最后一个，它们始终是1）。

[1, 2, 1]

更新过程：

• 原始列表：[1, 1]
• 插入新的第二元素（第一个元素 + 第二个元素）：[1, 2, 1]

第3行

4. 继续迭代更新为第3行。

[1, 3, 3, 1]

更新过程：

• 原始列表：[1, 2, 1]
• 插入新的第二元素（第一个元素 + 第二个元素）：[1, 3, 1]
• 插入新的第三元素（第二个元素 + 第三个元素）：[1, 3, 3, 1]

第4行

5. 最后迭代更新为第4行。

[1, 4, 6, 4, 1]

更新过程：

• 原始列表：[1, 3, 3, 1]
• 插入新的第二元素（第一个元素 + 第二个元素）：[1, 4, 3, 1]
• 插入新的第三元素（第二个元素 + 第三个元素）：[1, 4, 6, 1]
• 插入新的第四元素（第三个元素 + 第四个元素）：[1, 4, 6, 4, 1]

总结步骤

• 开始时列表只有一个元素1。
• 对于每一新行，从后向前更新列表中的每个元素，使得每个元素等于它自身加上前一个元素的值。
• 这个过程不断重复，直到达到所需的行。

通过这种方式，可以在不需要计算整个杨辉三角的情况下，直接生成所需行的元素，极大地优化了空间和时间效率。

方法二：使用公式（组合数）

解题步骤：

Python 代码示例

def getRow(rowIndex):
    row = [1] * (rowIndex + 1)
    for i in range(1, rowIndex // 2 + 1):
        row[i] = row[rowIndex - i] = row[i - 1] * (rowIndex - i + 1) // i
    return row

方法三：递归与缓存

解题步骤：

1. 使用递归函数通过前一行计算当前行。
2. 使用一个缓存（字典）来存储已计算过的行，避免重复计算。

Python 代码示例

from functools import lru_cache

@lru_cache(None)
def getRow(rowIndex):
    if rowIndex == 0:
        return [1]
    elif rowIndex == 1:
        return [1, 1]
    previous_row = getRow(rowIndex - 1)
    row = [1] + [previous_row[i] + previous_row[i + 1] for i in range(rowIndex - 1)] + [1]
    return row

算法分析

• 时间复杂度：
  • 方法一：(O(n^2))，其中 (n) 是行号。
  • 方法二：(O(n))，利用了数学公式直接计算，但每个计算涉及乘除操作。
  • 方法三：(O(n^2))，虽然有缓存，但每行的计算仍需之前所有行的数据。
• 空间复杂度：
  • 方法一和二：(O(n))，只存储需要的一行数据。
  • 方法三：由于缓存和递归的调用栈，空间复杂度较高。

不同算法的优劣势对比

• 线性迭代（方法一）简单高效，适合大多数实现场景。
• 使用公式（方法二）空间和时间效率高，但在实现时需注意数值运算的精度和效率。
• 递归与缓存（方法三）易于理解和实现，但空间复杂度较高，适用于对空间复杂度要求不高的场景。

应用示例

这些方法可以用在需要快速计算组合数的场景，例如统计学中的概率计