第 K 条最小指令
难度:
标签:
题目描述
Bob 站在单元格 (0, 0) ，想要前往目的地 destination ：(row, column) 。他只能向 右 或向 下 走。你可以为 Bob 提供导航 指令 来帮助他到达目的地 destination 。
指令 用字符串表示，其中每个字符：
'H'，意味着水平向右移动'V'，意味着竖直向下移动
能够为 Bob 导航到目的地 destination 的指令可以有多种，例如，如果目的地 destination 是 (2, 3)，"HHHVV" 和 "HVHVH" 都是有效 指令 。
然而，Bob 很挑剔。因为他的幸运数字是 k，他想要遵循 按字典序排列后的第 k 条最小指令 的导航前往目的地 destination 。k 的编号 从 1 开始 。
给你一个整数数组 destination 和一个整数 k ，请你返回可以为 Bob 提供前往目的地 destination 导航的 按字典序排列后的第 k 条最小指令 。
示例 1：
输入：destination = [2,3], k = 1 输出："HHHVV" 解释：能前往 (2, 3) 的所有导航指令 按字典序排列后 如下所示： ["HHHVV", "HHVHV", "HHVVH", "HVHHV", "HVHVH", "HVVHH", "VHHHV", "VHHVH", "VHVHH", "VVHHH"].
示例 2：
输入：destination = [2,3], k = 2 输出："HHVHV"
示例 3：
输入：destination = [2,3], k = 3 输出："HHVVH"
提示：
destination.length == 21 <= row, column <= 151 <= k <= nCr(row + column, row)，其中nCr(a, b)表示组合数，即从a个物品中选b个物品的不同方案数。
代码结果
运行时间: 28 ms, 内存: 0.0 MB
// 题目思路：
// 1. 使用 Java Stream 生成所有的可能路径，并按字典序排序。
// 2. 使用 combination 计算找到字典序第 k 小的序列。
// 注意：Java Stream 不适合生成大量组合的情况，容易导致内存不足。
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;
public class Solution {
public String kthSmallestPath(int[] destination, int k) {
int row = destination[0];
int column = destination[1];
String result = Stream.iterate("", s -> s.length() < row + column,
s -> s.length() < column ? s + "H" : s + "V")
.filter(s -> s.chars().filter(c -> c == 'H').count() == column)
.sorted()
.skip(k - 1)
.findFirst()
.orElse("");
return result;
}
}解释
方法:
这个题解使用数学组合的方法来确定第k个最小指令。通过计算在当前位置，选择向右移动（H）的不同方案数，可以判断第k个指令是选择H还是V。如果k大于向右移动的方案数，说明第k个指令肯定是V，否则就选择H。每次选择完一个指令，就更新剩余的k值以及剩余需要移动的水平和垂直步数，直到构建出完整的指令序列。
时间复杂度:
O(h+v)
空间复杂度:
O(h+v)
代码细节讲解
🦆
为什么选择使用数学组合方法来解决这个问题？有没有其他可能的算法？
▷🦆
在计算数学组合时，math.comb(h + v - 1, h - 1)的参数选择依据是什么？
▷🦆
当h为0时，代码直接添加了'V'并减少v值，这种处理方式是否考虑到了所有剩余步骤都必须向下移动的情况？
▷🦆
你如何确定每次决策点在字典序中的位置？即怎样判断k是否大于当前向右移动的方案数？
▷