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\) 个 \(\texttt{V}\) 与 \(h\) 个 \(\texttt{H}\) 组成，字典序第 \(k\) 条不能把全部 \(\binom{h+v}{h}\) 条路径列出来。

最高位若取 \(\texttt{H}\)，以 \(\texttt{H}\) 开头的条数是 \(C_{h+v-1}^{h-1}\)。\(k\) 大于该数则最高位只能是 \(\texttt{V}\) 并扣掉这些方案，否则取 \(\texttt{H}\)。

从左到右逐位用组合数决策，直到 \(h\) 用尽则其余全为 \(\texttt{V}\)。

根据题目描述我们可以知道，最终的路径是由 \(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]\)。

Python3JavaC++Go

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)

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();
    }
}

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;
    }
};

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)
}

1643. 第 K 条最小指令

题目描述

解法

方法一：组合计数

评论