【LeetCode 热题 100】118. 杨辉三角

Problem: 118. 杨辉三角

整体思路

这段代码旨在解决一个经典的数学与编程问题：生成杨辉三角 (Pascal’s Triangle)。问题要求根据给定的行数 numRows，生成一个表示杨辉三角的嵌套列表。

该算法采用了一种 逐行模拟（或称动态规划） 的方法。它利用了杨辉三角的一个核心性质：每一行的每个数（除了两边的1）都等于它正上方和左上方两个数之和。算法的逻辑是，通过迭代，一行一行地构建出整个三角形。

其核心逻辑步骤如下：

1. 初始化：

   • 创建一个嵌套列表 ans 作为最终的结果容器。
   • 处理 基础情况 (Base Case)：杨辉三角的第一行总是 [1]。算法首先将这一行硬编码并添加到 ans 中。如果 numRows 为1，后续的循环就不会执行，直接返回这个基础结果。

2. 逐行生成：

   • 算法使用一个 for 循环，从第二行（索引 r = 1）开始，一直迭代到 numRows - 1，以生成后续的每一行。
   • 在每次循环中，它都会创建一个新的列表 curRow 来表示当前正在构建的行。

3. 构建当前行 (curRow)：

   • 两边的 ‘1’：根据杨辉三角的定义，每一行的第一个和最后一个元素永远是 1。算法首先在 curRow 的开头添加一个 1。
   • 计算中间元素：接着，一个内层 for 循环负责计算位于两个 ‘1’ 之间的所有元素。
     • 这个循环利用了前一行（即 ans.get(r - 1)）已经计算好的结果。
     • 对于当前行 (r) 的第 i 个位置，其值等于上一行 (r-1) 的第 i-1 个位置和第 i 个位置的元素之和。即 curRow[i] = prevRow[i-1] + prevRow[i]。
   • 在计算完所有中间元素后，算法在 curRow 的末尾再添加一个 1。

4. 添加到结果集：

   • 当 curRow 被完整构建后，它就被添加到最终的结果列表 ans 中。
   • 外层循环继续，直到所有 numRows 行都被生成。

5. 返回结果：

   • 最后，返回包含整个杨辉三角的嵌套列表 ans。

完整代码

import java.util.ArrayList;
import java.util.List;class Solution {/*** 生成杨辉三角的前 numRows 行。* @param numRows 要生成的行数* @return 一个表示杨辉三角的嵌套列表*/public List<List<Integer>> generate(int numRows) {// ans: 用于存储最终的杨辉三角结果，是一个嵌套列表。List<List<Integer>> ans = new ArrayList<>();// 如果行数为0，直接返回空列表if (numRows == 0) {return ans;}// 基础情况：杨辉三角的第一行总是 [1]。// 使用 List.of() 创建一个不可变的列表。ans.add(List.of(1));// 从第二行 (r=1) 开始，逐行生成，直到 numRows。for (int r = 1; r < numRows; r++) {// 为当前要生成的行创建一个新的列表。// r+1 是该行的元素个数，可以用于初始化容量，有微小的性能提升。List<Integer> curRow = new ArrayList<>(r + 1);// 每一行的第一个元素总是 1。curRow.add(1);// 遍历计算当前行的中间元素。// 循环从 i=1 开始，到 r-1 结束。for (int i = 1; i < r; i++) {// 核心计算逻辑：当前行的第 i 个元素等于上一行 (ans.get(r - 1))// 的第 i-1 和第 i 个元素的和。curRow.add(ans.get(r - 1).get(i - 1) + ans.get(r - 1).get(i));}// 每一行的最后一个元素总是 1。curRow.add(1);// 将完整生成的新行添加到最终结果中。ans.add(curRow);}// 返回构建好的杨辉三角。return ans;}
}

时空复杂度

时间复杂度：O(numRows^2)

1. 循环结构：算法使用了嵌套循环。
   • 外层 for 循环从 r = 1 运行到 numRows - 1，执行了 numRows - 1 次。
   • 内层 for 循环从 i = 1 运行到 r - 1，执行了 r - 1 次。
2. 计算依据：
   • 总的操作次数（主要是加法和添加操作）与生成的杨辉三角的总元素个数成正比。
   • 第 r 行有 r+1 个元素。
   • 总元素个数大约是 1 + 2 + 3 + ... + numRows，这是一个等差数列求和，结果为 numRows * (numRows + 1) / 2。
   • 因此，总的操作次数与 numRows^2 成正比。

综合分析：
算法的时间复杂度为 O(numRows^2)。

空间复杂度：O(numRows^2)

1. 主要存储开销：算法的主要空间开销来自于存储整个杨辉三角的 ans 列表。
2. 计算依据：
   • 与时间复杂度分析类似，ans 列表需要存储的总元素个数为 numRows * (numRows + 1) / 2。
   • 因此，存储结果所需的空间与 numRows^2 成正比。
3. 其他变量：curRow 列表在每次外层循环中被创建，其最大长度为 numRows，但这部分空间可以被看作是构建最终 O(numRows^2) 结果的一部分，不会改变整体的复杂度量级。

综合分析：
由于需要存储并返回整个三角形，算法的空间复杂度为 O(numRows^2)。