下方是题目:

给定一个非负整数 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,从第3层开始,中间的数就有变化了,所以当numRows等于1或2时,直接返回结果。从第三层看,它是一个列表[1, 2, 1],2的索引为1,它是通过上一层索引0、1两个数相加而来的。第4层第一个3的索引为1,同样是上一层索引为0、1两个数相加而来的,第2个3的索引为2,它是上一层索引1、2相加而来的,即li[3][1] = li[2][0] + li[2][1],而从第3层开始,除去左右两端的1,需要新增的数的数量为1,2,3,4 ...

numRows的范围是1到30,数据量小,直接暴力解决。

所以代码如下:

class Solution(object):
    def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        if numRows == 1:       # 1、2两层列表直接返回
            return [[1]]
        elif numRows == 2:
            return [[1],[1,1]]
        
        li = [[1],[1,1]]       # 创建一个含有1、2两层的嵌套列表
        for i in range(3, numRows + 1): # 外循环为需要添加那几层
            li.append([1,1])         # 每一层的最左和最右的值都为1,所以直接添加一个[1,1]的列表

# 内循环为这一层要添加几个数,第一次外循环是三角的第3层,此时i等于3,需要添加1个数,所以i要减2
                for j in range(i - 2):   

# 如第3层的上一层为第2层,它的索引为1,而i为3,所以外列表的索引为i - 2
                num = li[i - 2][j] + li[i - 2][j + 1] 

# 通过insert方法将要添加的数添加到对应索引上,内层循环的j从0开始,而要添加的数的索引从1开始,故加1
                li[i - 1].insert(j + 1,num)

        return li

列表增加元素的insert方法:

        如列表为 li = [1, 3, 5, 6],想要添加元素2再1和3之间,添加后元素2的索引为1,使用insert方法就是: li.insert(1, 2),第一个参数为要添加到的索引,第二个参数为要添加的元素,添加后的列表为 li = [1, 2, 3, 5, 6],3,5,6这几个元素的索引都增加1。

Logo

Agent 垂直技术社区,欢迎活跃、内容共建。

更多推荐