难度: Easy
给定一个非负整数 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
难度: Easy
给定一个非负整数 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
运行时间: 15 ms
内存: 15.9 MB
class Solution: def generate(self, numRows: int) -> List[List[int]]: ans = [[1]] if numRows == 1: return ans for i in range(2, numRows+1): row = [] for j in range(i): if j == 0 or j == i - 1: row.append(1) else: row.append(ans[i-2][j-1] + ans[i-2][j]) ans.append(row) return ans
这个题解采用了动态规划的思路。从第二行开始,每一行的数字都等于上一行相邻两个数字之和。具体来说,从第二行开始,每行的第一个和最后一个数字都是1,中间的每个数字等于上一行它左右两个数字之和。在编码实现时,用一个二维列表 ans 来保存结果,其中 ans[i] 表示第 i 行的数字。从第二行开始,每次遍历当前行的每个位置,如果是第一个或最后一个位置,直接添加1;如果是中间位置,将上一行左右两个位置的数字相加得到当前位置的数字。
时间复杂度: O(numRows^2)
空间复杂度: O(numRows^2)
class Solution: def generate(self, numRows: int) -> List[List[int]]: ans = [[1]] # 初始化结果列表,第一行为 [1] if numRows == 1: return ans # 如果只有一行,直接返回结果 for i in range(2, numRows+1): # 从第二行开始遍历 row = [] # 当前行的数字 for j in range(i): # 遍历当前行的每个位置 if j == 0 or j == i - 1: # 如果是第一个或最后一个位置 row.append(1) # 直接添加 1 else: # 如果是中间位置 row.append(ans[i-2][j-1] + ans[i-2][j]) # 将上一行左右两个位置的数字相加 ans.append(row) # 将当前行添加到结果列表中 return ans # 返回结果列表
杨辉三角中,每行的第一个和最后一个数字代表的是组合数学中的组合系数,具体是从n个不同元素中选取0个元素和n个元素的组合方式,这两种情况都只有一种方法,因此这两个位置的数字总是1。
在题解中实现的动态规划方法中不会出现数组访问越界的问题。这是因为代码中已经明确了访问的边界,即只有当索引j在1到i-2之间(即非首尾)时,才会尝试访问上一行的元素。首尾元素直接赋值为1,因此不存在访问上一行不存在的元素的情况。
题解中确实考虑了numRows为1的情况。在代码开始部分,如果numRows的值为1,就直接返回初始化时包含单个元素[1]的列表。这样处理确保了当只需要一行时,程序能够正确返回结果,不会进入后续的行遍历逻辑。