LeetCode 119. 杨辉三角 II
题目描述
题意分析
返回杨辉三角中零基编号为
rowIndex的那一行，而不是前若干行。第零行只有一个1，所以第k行恰好有k + 1个数，两端都是1。内部每项等于上一行相邻两项之和。题目只需要一行，并给出
0 <= rowIndex <= 33的范围；不必把完整三角形存下来，可以直接生成目标行的各项。
解法：组合数递推
核心思路
[!blue]
杨辉三角第 $k$ 行第 $j$ 项就是组合数 $C(k,j)$，表示从 $k$ 个位置中选择 $j$ 个的方法数。按最后一个位置选或不选分类，得到 $C(k,j)=C(k-1,j-1)+C(k-1,j)$，这恰好与杨辉三角的相邻两项相加规则一致；两端的组合数也都是一。
不必分别用阶乘计算各项。相邻组合数约去相同因子后满足：$C(k,j+1)=C(k,j)\times(k-j)/(j+1)$。从 $C(k,0)=1$ 出发，只保存当前组合数，就能从左到右依次生成整行。
循环开始时，
value表示当前列的C(rowIndex, j)。先把它写入结果，再乘以rowIndex - j、除以j + 1，准备下一列。最后一列写完后已经完成答案，代码随后算出的零不再被使用；第零行也由同一循环自然处理。必须先乘后除，因为整体乘积能被分母整除，并不代表当前系数本身能被分母整除。先做整数除法会提前截断，丢掉正确结果。题目范围内最终系数能存入 32 位整数，但中间乘积可能更大，因此用
long或int64维护value，只在写入最终系数时转换。
解题步骤
- 创建容量或长度为
rowIndex + 1的结果容器，令宽整数value = 1。- 从
j = 0到rowIndex逐列生成，先写入当前value。- 按
value * (rowIndex - j) / (j + 1)计算下一列，保持先乘后除。- 全部列生成后返回这一行。
代码实现
class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> row = new ArrayList<>(rowIndex + 1);
long value = 1;
for (int j = 0; j <= rowIndex; j++) {
// 此时保存的是当前列的组合数，先写入再推下一列。
row.add((int) value);
// 宽整数先乘后除，避免中间乘积溢出或整数除法过早截断。
value = value * (rowIndex - j) / (j + 1);
}
return row;
}
}
func getRow(rowIndex int) []int {
row := make([]int, rowIndex+1)
value := int64(1)
for j := 0; j <= rowIndex; j++ {
// 此时保存的是当前列的组合数，先写入再推下一列。
row[j] = int(value)
// 宽整数先乘后除，避免中间乘积溢出或整数除法过早截断。
value = value * int64(rowIndex-j) / int64(j+1)
}
return row
}
复杂度分析
设 $k=rowIndex$。
- 时间复杂度：$O(k+1)$，每个结果元素只需一次常数时间的组合数递推。
- 辅助空间复杂度：$O(1)$，只保存当前系数和列号；返回结果本身占 $O(k+1)$，满足题目空间要求。
关键点总结
[!green]
- 组合数与杨辉三角满足相同边界和递推关系，因此能够直接生成目标行。
- 相邻系数通过一个乘除式相连，无需阶乘，也无需构造先前各行。
- 宽整数保存中间乘积，先乘后除保持计算精确。
易错点总结
[!yellow]
- 行号从零开始，结果长度必须为
rowIndex + 1，不能少生成右端的一。- 分别求阶乘不仅重复计算，还会在系数仍合法时提前溢出。
- 中间乘积不能用 32 位保存，必须从宽整数
value开始参与乘法。- 把表达式改成先除后乘会发生整数截断，即使最终数学结果是整数也无法弥补。
- 先推进系数再写入会错过当前列，循环应保持“先写当前项，再算下一项”的顺序。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 118. 杨辉三角 | 简单 | 本题只需某一行，可复用一维数组，原题需保存整个三角形。 |
| 62. 不同路径 | 中等 | 同样通过组合数或滚动DP计数；原地更新方向必须与旧状态依赖配套。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！