1643. 第 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 == 2

1 <= row, column <= 15

1 <= k <= nCr(row + column, row)，其中 nCr(a, b) 表示组合数，即从 a 个物品中选 b 个物品的不同方案数。

解题思路#

无论怎么走，到达目的地都需要 v = destination[0] 个字符 "V" 以及 h = destination[1] 个字符 "H"，且 "H" 的字典序比 "V" 小。

首先我们考虑第一个位置是放 "H" 还是放 "V"。

如果当前位置放 "H"，则后面最多有 \(M=C_{v+h-1}^{v}\)（组合数，表示从 \(v+h-1\) 个数里面选择 \(v\) 个数）种可能走法，从字典序最小的 \(\underbrace{H\cdots H}_{h-1个\textbf{H}}\underbrace{V\cdots V}_{v个\textbf{V}}\) 到字典序最大的 \(\underbrace{V\cdots V}_{v个\textbf{V}}\underbrace{H\cdots H}_{h-1个\textbf{H}}\)。

用 \(S_H\) 表示字符串 \(H\underbrace{V\cdots V}_{v个\textbf{V}}\underbrace{H\cdots H}_{h-1个\textbf{H}}\)，表示以 "H" 开头的 最大字典序。

用 \(S_V\) 表示字符串 \(V\underbrace{H\cdots H}_{h个\textbf{H}}\underbrace{V\cdots V}_{v-1个\textbf{V}}\)，表示以 "V" 开头的 最小字典序。

如果：

\(M \gt k\)，则当前位置显然要放置 "H"，因为 \(M\) 代表字符串 \(S_H\) 按照字典序排列的位置，之后的字符无论如何排列，都会 小于等于 \(M\)。如果放置 "V" 的话，\(S_V\) 的字典序位置为 \(M+1\)，无论之后的字符如何排列，都会 大于等于 \(M+1\)。
\(M \lt k\)，则当前位置显然放置 "V"，如果放置 "H" 的话，无论后面的的字符如何排列，也都到不了第 \(k\) 个字典序位置。此时放置完 "V" 之后，要将 \(k\) 减去 \(M\)，因为之后的字符串 \(\underbrace{H\cdots H}_{h个\textbf{H}}\underbrace{V\cdots V}_{v-1个\textbf{V}}\) 排列是从 \(M+1\) 开始的。减去 \(M\) 后，问题变为了在包含 \(v-1\) 个 "V" 和 \(h\) 个 "H" 中的字符串排列中寻找第 \(k-M\) 个字典序排列。
如果 \(M=k\)，则直接输出 \(S_H\) 即可。

之后每一步讨论重复以上过程。

from typing import List
from math import comb


class Solution:
    def kthSmallestPath(self, destination: List[int], k: int) -> str:
        v, h = destination
        steps = v + h
        path = [""] * steps

        for step in range(steps):
            M = comb(v + h - 1, v)  # 放置 H

            if M > k:
                path[step] = "H"
                h -= 1

            elif M < k:
                path[step] = "V"
                v -= 1
                k -= M

            else:  # M == k:
                break
        return "".join(path[:step]) + "H" + "V" * v + "H" * (h - 1)

1643. 第 K 条最小指令#

问题描述#

解题思路#

1643. 第 K 条最小指令 #