)
我来帮你解决 LeetCode 1643. 第 K 条最小指令 这道题。
题目分析
- 从 `(0, 0)` 走到 `(row, col)`，只能向右走 `'H'` (Horizontal) 或向下走 `'V'` (Vertical)
- 需要找字典序第 `k` 小的路径
- 字典序规则：`'H' < 'V'`，所以优先放 `'H'` 能得到更小的字典序
解题思路
这是一个组合数学问题。假设需要 `h` 个 `'H'` 和 `v` 个 `'V'`：
1. 关键观察：当前位置选择 `'H'` 后，后面可以形成的不同路径数为 `C(h+v-1, h-1)`（从剩余位置中选 `'H'` 的位置）
2. 决策过程：
- 如果 `k <= C(h+v-1, h-1)`：说明第 k 小的路径以 `'H'` 开头，选 `'H'`
- 否则：说明第 k 小的路径以 `'V'` 开头，选 `'V'`，同时 `k -= C(h+v-1, h-1)`
3. 组合数计算：使用杨辉三角或动态规划预处理，注意数值范围（`k` 最大为 `10^9`）
代码实现
```java
class Solution {
public String kthSmallestPath(int[] destination, int k) {
int v = destination[0]; // 需要向下走的次数 (Vertical)
int h = destination[1]; // 需要向右走的次数 (Horizontal)
// 预处理组合数 C[n][m] = C(n,m)
// 最大需要 C(30,15) 左右，因为 h+v <= 30
long[][] C = new long[h + v + 1][h + v + 1];
for (int i = 0; i <= h + v; i++) {
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; j++) {
// 防止溢出，但 k <= 1e9，所以超过的直接设为 k+1
C[i][j] = Math.min(C[i-1][j-1] + C[i-1][j], (long)k + 1);
}
}
StringBuilder sb = new StringBuilder();
while (h > 0 && v > 0) {
// 如果当前选 'H'，后面还有 h+v-1 个位置，需要选 h-1 个 'H'
long countH = C[h + v - 1][h - 1];
if (k <= countH) {
// 第 k 个在 'H' 开头的序列中
sb.append('H');
h--; // 还需要 h-1 个 'H'
} else {
// 第 k 个在 'V' 开头的序列中
sb.append('V');
k -= countH; // 跳过所有 'H' 开头的序列
v--; // 还需要 v-1 个 'V'
}
}
// 剩余的全是 'H' 或全是 'V'
while (h-- > 0) sb.append('H');
while (v-- > 0) sb.append('V');
return sb.toString();
}
}
```
复杂度分析
- 时间复杂度：O((h+v)²)，预处理组合数 + 构造答案
- 空间复杂度：O((h+v)²)，存储组合数
关键点说明
要点 说明
字典序 `'H' < 'V'`，所以优先尝试 `'H'`
组合数上限 用 `min(..., k+1)` 防止溢出，因为只需要和 `k` 比较
贪心策略 每一步确定当前位，缩小问题规模
示例验证
以 `destination = [2,3], k = 1` 为例：
- 需要 3 个 `'H'`，2 个 `'V'`
- 所有路径按字典序排列，第 1 个是 `"HHHVV"`
- 算法：每次优先选 `'H'`，k=1 始终 <= C(4,2)=6，所以一直选 `'H'` 直到用完
以 `destination = [2,3], k = 3` 为例：
- 第 1,2 个是 `"HHHVV"`, `"HHVHV"`
- 第 3 个是 `"HHVVH"` ✓
