题目描述
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 个物品的不同方案数。
解法
方法一：组合计数
根据题目描述我们可以知道，最终的路径是由 $destination[0]$ 个 'V' 和 $destination[1]$ 个 'H' 组成的，且按字典序排列后的第 $k$ 条最小指令。
我们首先考虑字典序的最高位，即最左边的字符。如果高位字符是 'V'，那么所有以 'H' 开头的路径的字典序都比它小，而以 'H' 开头的路径总数为 $x = C_{v+h-1}^{h-1}$。
如果 $k \lt x$，那么高位字符一定是 'V'，我们将 $k$ 减去 $x$，并将 $v$ 减 $1$，然后继续考虑下一位字符；否则，高位字符一定是 'H'，我们将 $h$ 减 $1$，然后继续考虑下一位字符。
注意，如果 $h = 0$，那么高位字符一定是 'V'，因为剩下的字符都是 'V'。
问题可以转换为求解 $C_{n}^{k}$，我们可以通过公式 $C_{n}^{k} = C_{n-1}^{k-1} + C_{n-1}^{k}$ 递推求解。
时间复杂度 $O((h + v) \times h)$，空间复杂度 $O((h + v) \times h)$。其中 $h$ 和 $v$ 分别为 $destination[1]$ 和 $destination[0]$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | class Solution:
def kthSmallestPath(self, destination: List[int], k: int) -> str:
v, h = destination
ans = []
for _ in range(h + v):
if h == 0:
ans.append("V")
else:
x = comb(h + v - 1, h - 1)
if k > x:
ans.append("V")
v -= 1
k -= x
else:
ans.append("H")
h -= 1
return "".join(ans)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 | class Solution {
public String kthSmallestPath(int[] destination, int k) {
int v = destination[0], h = destination[1];
int n = v + h;
int[][] c = new int[n + 1][h + 1];
c[0][0] = 1;
for (int i = 1; i <= n; ++i) {
c[i][0] = 1;
for (int j = 1; j <= h; ++j) {
c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}
}
StringBuilder ans = new StringBuilder();
for (int i = n; i > 0; --i) {
if (h == 0) {
ans.append('V');
} else {
int x = c[v + h - 1][h - 1];
if (k > x) {
ans.append('V');
k -= x;
--v;
} else {
ans.append('H');
--h;
}
}
}
return ans.toString();
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | class Solution {
public:
string kthSmallestPath(vector<int>& destination, int k) {
int v = destination[0], h = destination[1];
int n = v + h;
int c[n + 1][h + 1];
memset(c, 0, sizeof(c));
c[0][0] = 1;
for (int i = 1; i <= n; ++i) {
c[i][0] = 1;
for (int j = 1; j <= h; ++j) {
c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}
}
string ans;
for (int i = 0; i < n; ++i) {
if (h == 0) {
ans.push_back('V');
} else {
int x = c[v + h - 1][h - 1];
if (k > x) {
ans.push_back('V');
--v;
k -= x;
} else {
ans.push_back('H');
--h;
}
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 | func kthSmallestPath(destination []int, k int) string {
v, h := destination[0], destination[1]
n := v + h
c := make([][]int, n+1)
for i := range c {
c[i] = make([]int, h+1)
c[i][0] = 1
}
for i := 1; i <= n; i++ {
for j := 1; j <= h; j++ {
c[i][j] = c[i-1][j] + c[i-1][j-1]
}
}
ans := []byte{}
for i := 0; i < n; i++ {
if h == 0 {
ans = append(ans, 'V')
} else {
x := c[v+h-1][h-1]
if k > x {
ans = append(ans, 'V')
k -= x
v--
} else {
ans = append(ans, 'H')
h--
}
}
}
return string(ans)
}
|