1643. 第 K 小的字典序指令

Hard

题目描述

Bob 站在单元格 (0, 0)，想要到达目的地：(row, column)。他只能向右和向下移动。你将通过为他提供到达目的地的指令来帮助 Bob。

指令用字符串表示，其中每个字符是：

‘H’，表示水平移动（向右）
‘V’，表示垂直移动（向下）

多个指令将引导 Bob 到达目的地。例如，如果目的地是 (2, 3)，那么 “HHHVV” 和 “HVHVH” 都是有效的指令。

然而，Bob 很挑剔。Bob 有一个幸运数字 k，他想要第 k 小的字典序指令来引导他到达目的地。k 是从 1 开始索引的。

给定一个整数数组 destination 和一个整数 k，返回第 k 小的字典序指令，该指令将带 Bob 到达目的地。

示例 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 <= C(row + column, row)，其中 C(a, b) 表示组合数 a 选 b

提示：

有 C(row + column, row) 种可能的指令到达 (row, column)
尝试逐步构建指令。有多少指令以 “H” 开头，这与 k 如何比较？

解题思路

这道题的核心思想是利用组合数学来逐位确定结果字符串。

问题分析： 要到达 (row, column)，我们需要向下走 row 步，向右走 column 步，总共 row + column 步。这相当于在 row + column 个位置中选择 row 个位置放置 ‘V’，其余放置 ‘H’。

解题思路：

使用贪心策略逐位构建答案：对于每个位置，我们优先选择字典序较小的字符 ‘H’
关键问题：在当前位置选择 ‘H’ 时，剩余有多少种排列方式？
如果以 ‘H’ 开头的排列数量 ≥ k，说明第 k 小的字符串以 ‘H’ 开头
否则，第 k 小的字符串以 ‘V’ 开头，更新 k 值

算法步骤：

预计算组合数 C(n,r) = n! / (r! × (n-r)!)
从左到右构建答案字符串：
- 计算剩余需要的 ‘H’ 和 ‘V’ 数量
- 计算以 ‘H’ 开头的排列数量：C(h+v-1, v)
- 如果该数量 ≥ k，选择 ‘H’；否则选择 ‘V’ 并更新 k
重复直到构建完整个字符串

推荐解法： 使用组合数计算的贪心算法，时间复杂度最优。

代码实现

class Solution {
public:
    string kthSmallestPath(vector<int>& destination, int k) {
        int row = destination[0], col = destination[1];
        int total = row + col;
        
        // 预计算组合数
        vector<vector<int>> C(total + 1, vector<int>(total + 1, 1));
        for (int i = 2; i <= total; i++) {
            for (int j = 1; j < i; j++) {
                C[i][j] = C[i-1][j-1] + C[i-1][j];
            }
        }
        
        string result = "";
        int h = col, v = row; // 剩余需要的H和V数量
        
        for (int i = 0; i < total; i++) {
            if (h == 0) {
                result += 'V';
                v--;
            } else if (v == 0) {
                result += 'H';
                h--;
            } else {
                // 计算以H开头的排列数
                int pathsWithH = C[h + v - 1][v];
                if (k <= pathsWithH) {
                    result += 'H';
                    h--;
                } else {
                    result += 'V';
                    k -= pathsWithH;
                    v--;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def kthSmallestPath(self, destination: List[int], k: int) -> str:
        row, col = destination[0], destination[1]
        total = row + col
        
        # 预计算组合数
        C = [[1] * (total + 1) for _ in range(total + 1)]
        for i in range(2, total + 1):
            for j in range(1, i):
                C[i][j] = C[i-1][j-1] + C[i-1][j]
        
        result = []
        h, v = col, row  # 剩余需要的H和V数量
        
        for _ in range(total):
            if h == 0:
                result.append('V')
                v -= 1
            elif v == 0:
                result.append('H')
                h -= 1
            else:
                # 计算以H开头的排列数
                paths_with_h = C[h + v - 1][v]
                if k <= paths_with_h:
                    result.append('H')
                    h -= 1
                else:
                    result.append('V')
                    k -= paths_with_h
                    v -= 1
        
        return ''.join(result)

public class Solution {
    public string KthSmallestPath(int[] destination, int k) {
        int row = destination[0], col = destination[1];
        int total = row + col;
        
        // 预计算组合数
        int[,] C = new int[total + 1, total + 1];
        for (int i = 0; i <= total; i++) {
            C[i, 0] = 1;
            if (i <= total) C[i, i] = 1;
        }
        for (int i = 2; i <= total; i++) {
            for (int j = 1; j < i; j++) {
                C[i, j] = C[i-1, j-1] + C[i-1, j];
            }
        }
        
        StringBuilder result = new StringBuilder();
        int h = col, v = row; // 剩余需要的H和V数量
        
        for (int i = 0; i < total; i++) {
            if (h == 0) {
                result.Append('V');
                v--;
            } else if (v == 0) {
                result.Append('H');
                h--;
            } else {
                // 计算以H开头的排列数
                int pathsWithH = C[h + v - 1, v];
                if (k <= pathsWithH) {
                    result.Append('H');
                    h--;
                } else {
                    result.Append('V');
                    k -= pathsWithH;
                    v--;
                }
            }
        }
        
        return result.ToString();
    }
}

var kthSmallestPath = function(destination, k) {
    const [row, col] = destination;
    const result = [];
    
    // Precompute combinations using Pascal's triangle
    const C = Array(row + col + 1).fill().map(() => Array(row + col + 1).fill(0));
    for (let i = 0; i <= row + col; i++) {
        C[i][0] = 1;
        for (let j = 1; j <= i; j++) {
            C[i][j] = C[i-1][j-1] + C[i-1][j];
        }
    }
    
    let remainingH = col;
    let remainingV = row;
    let remainingK = k;
    
    while (remainingH > 0 || remainingV > 0) {
        if (remainingH === 0) {
            result.push('V');
            remainingV--;
        } else if (remainingV === 0) {
            result.push('H');
            remainingH--;
        } else {
            // Count paths starting with 'H'
            const pathsWithH = C[remainingH + remainingV - 1][remainingV];
            
            if (remainingK <= pathsWithH) {
                result.push('H');
                remainingH--;
            } else {
                result.push('V');
                remainingV--;
                remainingK -= pathsWithH;
            }
        }
    }
    
    return result.join('');
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	大小	说明
时间复杂度	O((row + column)²)	预计算组合数需要 O(n²)，构建答案需要 O(n)
空间复杂度	O((row + column)²)	存储组合数表需要 O(n²) 空间

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析