leetcode hot100【LeetCode 118. 杨辉三角】java实现

LeetCode 118. 杨辉三角

题目描述

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

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

示例：

输入: 5
输出:
[[1],[1, 1],[1, 2, 1],[1, 3, 3, 1],[1, 4, 6, 4, 1]
]

Java 实现代码

class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> res = new ArrayList<>();for (int i = 0; i < numRows; i++) {List<Integer> row = new ArrayList<>(); //用于存储每一行的元素for (int j = 0; j <= i; j++) {if (j == 0 || j == i) { // 每一行的第一个和最后一个元素都是1。row.add(1); } else {row.add(res.get(i - 1).get(j - 1) + res.get(i - 1).get(j)); //其他元素的值是上一行相邻两个元素的和。}}res.add(row);}return res;}
}

解题思路

杨辉三角的构建规则如下：

1. 每一行的第一个和最后一个元素都是1。
2. 其他元素的值是上一行相邻两个元素的和。

基于这个规则，我们可以通过以下步骤生成杨辉三角：

1. 创建一个空的列表 res 用于存储杨辉三角的所有行。
2. 使用第一个循环遍历从0到numRows-1也就是<numRows，生成每一行：
   -创建一个新的列表 row 来存储当前行的元素。
3. 使用第二个循环遍历从0到i也就是<=i
   • 如果当前元素是每一行的第一个和最后一个元素,则将该元素设置为1。
   • 如果当前元素不是第一个且不是最后一个，则设置当前元素的值为上一行相邻两个元素的和。
   • 将当前行添加到 res 中。
4. 返回生成的 res。

复杂度分析

• 时间复杂度：O(numRows^2)，因为我们需要逐行构建三角形，每行最多有 numRows 个元素。
• 空间复杂度：O(1)，不考虑返回值的空间占用。

注：题目来源leetcode网站