LeetCode 118. 杨辉三角

约 4 分钟
文章信息 13 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 10-20 LeetCode 热题 100 腾讯 字节 亚马逊 美团 百度 快手 虾皮
标签
数组 动态规划

题目描述

✅ 118. 杨辉三角

image-20260928215906037

image-20260928215906038

题意分析

返回杨辉三角的前 numRows 行，每行都要保留。第 row 行从 0 开始编号，共有 row + 1 个数；两端是 1，内部位置等于上一行左上方与右上方两个数之和。

解法：按定义逐行递推

核心思路

[!blue]

设当前要填第 row 行、第 col 列。两端 col == 0 和 col == row 直接填 1；内部位置的两个来源，恰好是上一行的 col - 1 和 col，因此填入 answer[row - 1][col - 1] + answer[row - 1][col]。

按行从上往下构造时，所需的上一行一定已经完整保存在 answer 中。首行只有一个端点，直接得到 [1]；之后每行的端点与内部位置都满足定义，所以逐行生成的就是整个杨辉三角。

题目要求返回所有行，可以直接把答案当作递推所需的数据，不必另建状态表。每一行新建容器，填好后加入答案，避免后续修改覆盖历史行。

解题步骤

  1. 建立答案列表，依次处理 row = 0 到 numRows - 1。
  2. 为当前行创建独立容器，生成 row + 1 个元素。
  3. 两端填 1；只有 0 < col < row 的内部位置才读取上一行并相加。
  4. 当前行全部填好后加入答案，作为下一行的依据。
  5. 行数达到 numRows 时返回答案。第 0、1 行都没有内部位置，不会读取越界下标。

Java 在逐项追加时判断是否为端点；Go 先设置两端，再只遍历内部位置。两种写法使用的是同一条递推规则。

代码实现

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> answer = new ArrayList<>(numRows);

        for (int row = 0; row < numRows; row++) {
            List<Integer> current = new ArrayList<>(row + 1);

            for (int col = 0; col <= row; col++) {
                // 两端直接设一，只有内部位置需要读取上一行。
                if (col == 0 || col == row) {
                    current.add(1);
                } else {
                    List<Integer> previous = answer.get(row - 1);

                    current.add(previous.get(col - 1) + previous.get(col));
                }
            }

            answer.add(current);
        }

        return answer;
    }
}

func generate(numRows int) [][]int {
    answer := make([][]int, 0, numRows)

    for row := 0; row < numRows; row++ {
        current := make([]int, row+1)
        current[0] = 1
        current[row] = 1

        // 两端已经设一，只为内部位置累加上一行相邻两项。
        for col := 1; col < row; col++ {
            current[col] = answer[row-1][col-1] + answer[row-1][col]
        }
        answer = append(answer, current)
    }
    return answer
}

复杂度分析

  • 时间复杂度：$O(n^2)$，其中 $n$ 是 numRows；共生成 $n(n+1)/2$ 个元素。
  • 空间复杂度：$O(n^2)$，用于返回全部元素；若不计返回值，额外空间为 $O(1)$。

关键点总结

[!green]

  • 行号从 0 开始，第 row 行长度是 row + 1，左右端点下标分别为 0 和 row。
  • 从上往下构造保证上一行已经完成，内部两项之和直接来自题目定义。
  • 答案保留了所有前序行，本身就能承担递推存储。

易错点总结

[!yellow]

  • Java 逐项追加整行，循环必须包含 col == row；Go 已设置两端，内部循环只需 col < row。
  • 必须先区分端点与内部位置，否则首行会读取不存在的上一行，右端也会访问上一行越界。
  • 每行需要独立容器。反复修改同一列表再加入答案，会使多行引用同一份数据。
  • 递推读取上一行，不能读取当前行尚未填好的位置。

相似题目

题目 难度 关联与区别
119. 杨辉三角 II 简单 递推相同，原题只返回一行，可用逆序更新压缩空间，本题需保留全部行。
62. 不同路径 中等 杨辉三角的相邻两项相加与网格路径的两前驱计数对应，都产生组合数。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/01053064
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！