LeetCode 题解工作台
杨辉三角 II
给定一个非负索引 rowIndex ，返回「杨辉三角」的第 rowIndex 行。 在「杨辉三角」中，每个数是它左上方和右上方的数的和。 示例 1: 输入: rowIndex = 3 输出: [1,3,3,1] 示例 2: 输入: rowIndex = 0 输出: [1] 示例 3: 输入: row…
2
题型
7
代码语言
3
相关题
当前训练重点
简单 · 状态·转移·动态规划
答案摘要
我们创建一个长度为 $rowIndex + 1$ 的数组 ，初始时所有元素均为 。 接下来，我们从第 行开始，从后往前计算当前行的第 个元素的值 $f[j] = f[j] + f[j - 1]$，其中 $j \in [1, i - 1]$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: rowIndex = 3 输出: [1,3,3,1]
示例 2:
输入: rowIndex = 0 输出: [1]
示例 3:
输入: rowIndex = 1 输出: [1,1]
提示:
0 <= rowIndex <= 33
进阶：
你可以优化你的算法到 O(rowIndex) 空间复杂度吗？
解题思路
方法一：递推
我们创建一个长度为 的数组 ，初始时所有元素均为 。
接下来，我们从第 行开始，从后往前计算当前行的第 个元素的值 ，其中 。
最后返回 即可。
时间复杂度 ，空间复杂度 。其中 是给定的行数。
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
f = [1] * (rowIndex + 1)
for i in range(2, rowIndex + 1):
for j in range(i - 1, 0, -1):
f[j] += f[j - 1]
return f
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(rowIndex^2) due to nested iteration to update each element, and space complexity is O(rowIndex) because only a single row array is maintained. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if you can compute only the requested row without building the full triangle.
- question_mark
Expect discussion on in-place updates and avoiding overwriting previous row values.
- question_mark
Consider edge cases like rowIndex = 0 or rowIndex = 1 to confirm correct base cases.
常见陷阱
外企场景- error
Overwriting elements from left to right, which corrupts intermediate sums.
- error
Attempting to build the full Pascal's Triangle when only one row is needed.
- error
Ignoring base cases, leading to index out-of-bounds errors or incorrect first row values.
进阶变体
外企场景- arrow_right_alt
Return the triangle up to rowIndex instead of only one row.
- arrow_right_alt
Compute a specific element in rowIndex-th row using combinatorial formula.
- arrow_right_alt
Modify the algorithm to handle large rowIndex values efficiently with BigInteger types.