打卡力扣题目五

简介: 打卡力扣题目五

关于 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)。相比于第一种方法,这种方法更加高效,因为它只需要存储当前层的所有元素,而不需要存储整个三角形的所有元素。


相关文章
|
2月前
|
程序员 C语言
【C语言】LeetCode(力扣)上经典题目
【C语言】LeetCode(力扣)上经典题目
|
3月前
|
SQL Oracle 关系型数据库
CASE WHEN 语句的语法及示例,LeetCode 题目 “确认率” 练习
本文介绍了SQL中CASE语句的两种形式和语法,并通过LeetCode题目“确认率”的SQL查询示例展示了CASE语句在实际问题中的应用,解释了如何使用CASE语句计算特定条件的比率。
|
4月前
|
算法
LeetCode第12题目整数转罗马数字
该文章介绍了 LeetCode 第 12 题整数转罗马数字的解法,通过使用 TreeMap 按照整数从大到小排序,先使用大的罗马数字表示整数,再用小的,核心是先表示完大的罗马数字,想通此点该题较简单。
LeetCode第12题目整数转罗马数字
|
4月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
52 6
|
4月前
|
算法
LeetCode第13题目罗马数字转整数
该文章介绍了 LeetCode 第 13 题罗马数字转整数的解法,通过从大到小解析罗马数字,根据罗马数字的特点,按照从大到小的顺序匹配罗马数字和整数的关系,从而解决该问题,同时强调要注意观察题目考查的知识点特征。
|
6月前
|
C语言
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
36 1
|
6月前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
5月前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
6月前
|
容器
【LeetCode刷题】栈和队列题目练习~
【LeetCode刷题】栈和队列题目练习~