杨辉三角 - LeetCode 热题 82

本文主要是介绍杨辉三角 - LeetCode 热题 82，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

大家好！我是曾续缘🤎

今天是《LeetCode 热题 100》系列

发车第 82 天

动态规划第 2 题

❤️点赞 👍 收藏 ⭐再看，养成习惯

杨辉三角
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows = 1
输出: [[1]]
提示:

1 <= numRows <= 30
难度：❤️

解题方法

杨辉三角是一种数学形式，也被称为帕斯卡三角形，它是一个由数字构成的三角形，最早出现在中国南宋杨辉的《详解九章算术》中。在这个三角形中，每个数等于它上方两数之和。

具体来说，每一行的第一个数字和最后一个数字都是1，而其他数字则是其正上方数字和左上方数字之和。

创建一个空列表 ans：这个列表将用于存储杨辉三角的所有行。
外层循环：我们需要生成 numRows 行的杨辉三角，因此我们使用一个外层循环来遍历每一行。循环的次数就是 numRows。
创建每一行的列表 row：对于每一行，我们首先创建一个空列表 row，然后在这个列表的开头添加数字1。这是因为每一行的第一个数字总是1。
内层循环：对于每一行（除了第一行），我们需要计算除了第一个和最后一个数字之外的数字。因此，我们使用一个内层循环来遍历这些数字。循环的次数比当前行数少1（因为第一个和最后一个数字已经确定是1）。
计算每个数字：在内层循环中，我们使用上一行的数字来计算当前行的数字。具体来说，我们将上一行的相邻两个数字相加，得到当前行的数字。
在每一行末尾添加数字1：对于每一行（除了第一行），我们在列表的末尾添加数字1，因为每一行的最后一个数字总是1。
将每一行添加到 ans 中：最后，我们将每一行添加到 ans 列表中。

经过以上步骤，我们就可以生成一个由数字组成的杨辉三角，并将其作为结果返回。

Code

class Solution {public List<List<Integer>> generate(int numRows) {// 创建一个列表 ans，用于存储杨辉三角的所有行List<List<Integer>> ans = new ArrayList<>();// 外层循环，遍历每一行for (int i = 0; i < numRows; i++) {// 创建当前行的列表 rowList<Integer> row = new ArrayList<>();// 在当前行的开头添加数字1row.add(1);// 内层循环，计算当前行的中间数字（除了第一个和最后一个数字）for (int j = 1; j < i; j++) {// 获取上一行的列表List<Integer> prevRow = ans.get(i - 1);// 计算当前行的数字，它是上一行相邻两个数字之和int num = prevRow.get(j - 1) + prevRow.get(j);// 将计算出的数字添加到当前行row.add(num);}// 如果当前行不是第一行，在末尾添加数字1if (i > 0) {row.add(1);}// 将当前行添加到 ans 列表中ans.add(row);}// 返回生成的杨辉三角return ans;}
}