0119. Pascal's Triangle II¶
题目信息¶
- 题号:
杨辉三角 II
- 难度:
Easy
- 主题:
数组、动态规划、逆序更新、组合数
- 原题:
- 重点:
从保存全部历史行压缩为原地滚动数组,再利用目标行的组合数结构删除前面各行的构造
题目重述¶
给定非负整数 rowIndex,返回杨辉三角中零基编号为 rowIndex 的一整行。第 0 行是 [1];
第 rowIndex 行共有 rowIndex + 1 个元素,首尾为 1,内部元素由上一行相邻两项之和得到。
约束为 0 <= rowIndex <= 33。题目只要求目标行,不需要返回或保留之前各行。
自建示例¶
rowIndex = 6时返回[1,6,15,20,15,6,1];rowIndex = 2时返回[1,2,1];rowIndex = 1时返回[1,1];rowIndex = 0时返回[1],不需要执行任何转移。
C++ 实现¶
#include <utility>
#include <vector>
class Solution {
private:
std::vector<int> buildFullTriangle(int rowIndex) {
std::vector<std::vector<int>> triangle;
for (int row = 0; row <= rowIndex; ++row) {
std::vector<int> current(row + 1, 1);
if (row > 0) {
for (int column = 1; column < row; ++column) {
current[column] = triangle.back()[column - 1] + triangle.back()[column];
}
}
triangle.push_back(std::move(current));
}
return triangle.back();
}
std::vector<int> rollingRow(int rowIndex) {
std::vector<int> row(rowIndex + 1);
row[0] = 1;
for (int currentRow = 1; currentRow <= rowIndex; ++currentRow) {
for (int column = currentRow; column >= 1; --column) {
row[column] += row[column - 1];
}
}
return row;
}
std::vector<int> combinationRow(int rowIndex) {
std::vector<int> row(rowIndex + 1);
long long value = 1;
for (int column = 0; column <= rowIndex; ++column) {
row[column] = static_cast<int>(value);
if (column < rowIndex) {
value = value * (rowIndex - column) / (column + 1);
}
}
return row;
}
public:
std::vector<int> getRow(int rowIndex) {
return combinationRow(rowIndex);
}
};
题解¶
完整三角形基线¶
最直接的正确方案是从第 0 行开始,按“首尾为 1、内部等于上一行相邻父项之和”依次构造到目标行。
buildFullTriangle 保存每一行,最终返回最后一行。依赖顺序自上而下,所有父项在读取前都已正确计算。
但历史行只服务于下一行,完成目标后全部被丢弃。保存三角形需要 1 + 2 + ... + (rowIndex + 1) 个整数,
而返回值只有 rowIndex + 1 个。首先应删除的是不属于输出的历史行。
一维逆序滚动¶
上一行与当前行的关系为:
new[column] = old[column] + old[column - 1]
预先分配长度 rowIndex + 1 的数组,令 row[0] = 1,其余位置为 0。每轮只更新当前行会使用的
前缀,数组便可同时表示旧行和新行。
更新必须从右向左。计算 row[column] 时,右侧当前位置仍保存 old[column],左邻位置也还没有在本轮
修改,因而能读取 old[column - 1]。若从左向右,左邻已经变成 new[column - 1],同一轮的新值会
被再次使用,递推关系被改变。
尾部的 1 也无需单独赋值:进入第 currentRow 轮前,row[currentRow] 仍为 0;本轮第一个
逆序更新把它加上上一行末尾的 1,自然得到新行尾。
完成行号 |
工作数组有效前缀 |
|---|---|
0 |
|
1 |
|
2 |
|
3 |
|
4 |
|
rollingRow 把空间从完整三角形的 O(rowIndex²) 压缩到返回数组本身,但仍要构造从第 0 行到目标
行的全部中间状态,总更新次数为 O(rowIndex²)。
只构造目标行¶
杨辉三角第 rowIndex 行第 column 项也是组合数 C(rowIndex, column)。相邻项满足:
C(rowIndex, 0) = 1
C(rowIndex, column + 1) =
C(rowIndex, column) * (rowIndex - column) / (column + 1)
因此已知当前 value 后,可以在常数时间得到下一列,不再构造任何前置行。组合数关系保证每步整除;代码
先乘后除,并用 long long 保存中间乘积,避免虽然最终元素适合 int,乘法过程却超出 32 位。
对 rowIndex = 6,状态依次为:
1
1 * 6 / 1 = 6
6 * 5 / 2 = 15
15 * 4 / 3 = 20
20 * 3 / 4 = 15
15 * 2 / 5 = 6
6 * 1 / 6 = 1
这直接得到 [1,6,15,20,15,6,1]。首尾和对称性都由同一递推自然产生,不需要特殊列分支。
主解与复杂度¶
公开入口采用组合数递推,因为它把一维 DP 中仍然存在的全部前置行更新删除,时间从 O(rowIndex²) 降为
O(rowIndex)。代价是依赖组合数恒等式和较宽中间类型;若题目只提供局部父项关系,逆序滚动 DP 更通用。
完整三角形时间、空间均为 O(rowIndex²);滚动 DP 时间 O(rowIndex²)、返回数组空间
O(rowIndex);组合数主解时间 O(rowIndex),除返回数组外只用常数状态。返回数组本身需要
O(rowIndex) 空间,无法再减少。