打卡力扣题目五

目录

 一、问题

 二、解题方法一

三、解题方法二

四、两种方法的区别

 关于 ARTS 的释义 —— 每周完成一个 ARTS：
● Algorithm: 每周至少做一个 LeetCode 的算法题
● Review: 阅读并点评至少一篇英文技术文章
● Tips: 学习至少一个技术技巧
● Share: 分享一篇有观点和思考的技术文章

希望通过此次活动能聚集一波热爱技术的人，延续好奇、探索、实践、分享的精神。
 

 一、问题
今天是杨辉三角的题目

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

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

示例 1:

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

示例 2:

输入: numRows = 1
输出: [[1]]

 二、解题方法一
def generate(numRows):
    res = []
    for i in range(numRows):
        row = [1]
        if res:
            last_row = res[-1]
            row.extend([sum(pair) for pair in zip(last_row, last_row[1:])])
            row.append(1)
        res.append(row)
    return res
这段代码实现了一个名为 `generate` 的函数，用于生成杨辉三角的前 numRows 行。

首先，我们定义了一个空列表 `res`,用于存储每一行的结果。然后，使用一个 for 循环遍历每一行，对于第 i 行，我们先将第一个元素设为 1,表示该行的第一个数是 1。

接着，如果 `res` 不为空，则说明已经生成了前几行，我们可以从上一行中获取到当前行需要用到的数据。具体来说，我们使用 zip 函数将当前行和上一行进行配对，得到一个由元组组成的列表。每个元组包含两个相邻的元素，例如 [(1, 2), (2, 3), (3, 5)] 表示第三行的前两个数是 1、2,第三个数是 1+2=3、2+3=5。然后，我们使用列表推导式将这些元组中的元素两两相加，得到一个新的列表，其中包含了当前行的所有数。最后，我们将最后一个元素设为 1,表示当前行的最后一个数也是 1。

将当前行的结果添加到 `res` 中后，继续循环生成下一行。当所有行都生成完毕后，返回 `res` 作为结果。

需要注意的是，在 Python 中，列表是可变对象，因此在函数内部修改 `res` 不会影响到外部的变量。但是在函数内部直接修改 `res[-1]` 是不可取的，因为这样会改变列表的长度，导致后面的元素被覆盖。正确的做法是使用 `append` 方法向列表末尾添加新元素。

三、解题方法二
另一种解题方法是使用动态规划的思想，从底部开始逐层生成杨辉三角。具体来说，我们可以定义一个二维数组 `dp`,其中 dp[i][j] 表示第 i 行、第 j 列的元素值。然后，我们使用两个嵌套的循环遍历每一行和每一列，根据题目中的规则计算出每个元素的值，并将其保存到 `dp` 中。最后，将 `dp` 转置得到最终的结果。

这种方法的时间复杂度为 O(n^2),空间复杂度也为 O(n^2)。相比于直接生成所有元素的方法，这种方法更加高效。

class Solution:
    def generate(self, numRows):
        if numRows == 0:
            return []
        
        dp = [[1] * numRows for _ in range(numRows)]
        for i in range(2, numRows):
            for j in range(1, i):
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
        
        return list(map(list, zip(*dp)))
这段代码定义了一个名为 Solution 的类，其中包含了一个名为 generate 的方法。这个方法接受一个非负整数 numRows 作为参数，返回杨辉三角的前 numRows 行。

在方法内部，我们首先判断 numRows 是否为 0,如果是则直接返回空列表。然后，我们定义一个二维数组 dp,用于存储每个元素的值。接下来，我们使用两个嵌套的循环遍历每一行和每一列，根据题目中的规则计算出每个元素的值，并将其保存到 dp 中。最后，我们使用 zip 函数将 dp 转置得到最终的结果，并将其转换为列表返回。

四、两种方法的区别
两种方法的主要区别在于实现思路和时间/空间复杂度。

第一种方法是直接生成所有元素的方法，它的核心思想是使用一个循环遍历每一行和每一列，根据题目中的规则计算出每个元素的值，并将其添加到结果列表中。这种方法的时间复杂度为 O(n^2),因为需要遍历所有的元素。同时，由于需要存储所有的元素，因此空间复杂度也为 O(n^2)。

第二种方法是使用动态规划的思想，从底部开始逐层生成杨辉三角。它的核心思想是使用一个二维数组 `dp` 来存储每个元素的值，然后使用两个嵌套的循环遍历每一行和每一列，根据题目中的规则计算出每个元素的值，并将其保存到 `dp` 中。最后，我们将 `dp` 转置得到最终的结果。这种方法的时间复杂度为 O(n^2),空间复杂度也为 O(n^2)。相比于第一种方法，这种方法更加高效，因为它只需要存储当前层的所有元素，而不需要存储整个三角形的所有元素。