当前位置：首页 > 力扣 > 力扣1643题：第K小字典序路径（附C++代码与解题思路）

力扣1643题：第K小字典序路径（附C++代码与解题思路）

6小时前

一、题目解读

本题要求生成从原点(0, 0)到目标坐标(destination[0], destination[1])的路径中，字典序第K小的路径。路径仅由向下字符'V'（代表垂直移动）和向右字符'H'（代表水平移动）组成，需确保路径长度与目标坐标距离一致。难点在于高效计算路径顺序并找到第K小的字典序组合。

二、解题思路

采用组合数计算+贪心选择策略：

1. 核心原理：通过预计算组合数，动态判断当前可选路径数是否满足K的限制，从而确定下一步方向。

2. 关键逻辑：

○ 计算总步数n=水平+垂直步数，路径本质为n步中选垂直步数v（或水平步数h）的组合问题。

○ 利用组合数公式C(n, k)=C(n-1, k-1)+C(n-1, k)，预存C(n, k)避免重复计算。

○ 贪心决策：若当前选择'H'的路径数≤K，则必选'H'；否则选择'V'并更新K=K-可选路径数。

三、解题步骤

1. 初始化变量：v=垂直步数，h=水平步数，res=结果路径。

2. 预计算组合数：生成二维数组comb，按杨辉三角递推公式计算C(n, k)，边界条件comb[i][0]=1。

3. 贪心生成路径：

循环直至h或v为0：

计算当前选'H'的路径数C(h+v-1, h-1)。

若K≤该路径数，则选'H'并减h；否则选'V'、减v且K更新为剩余路径数。

处理剩余步数：直接追加'H'或'V'至res。

4. 返回字典序路径：res即为第K小路径。

四、代码与注释

class Solution {
public:
    string kthSmallestPath(vector<int>& destination, int k) {
        int v = destination[0]; // 需要向下走的次数
        int h = destination[1]; // 需要向右走的次数
        string res;
        
        // 预计算组合数C(n,k)
        vector<vector<int>> comb(h + v, vector<int>(h + v, 0));
        for (int i = 0; i < h + v; ++i) {
            comb[i][0] = 1;
            for (int j = 1; j <= i; ++j) {
                comb[i][j] = comb[i-1][j-1] + comb[i-1][j];
            }
        }
        
        while (h > 0 && v > 0) {
            // 如果选择'H'，后面有C(h+v-1, h-1)种可能
            int c = comb[h + v - 1][h - 1];
            if (k <= c) {
                res += 'H';
                h--;
            } else {
                res += 'V';
                k -= c;
                v--;
            }
        }
        // 处理剩余全部'H'或'V'的情况
        res += string(h, 'H');
        res += string(v, 'V');
        return res;
    }
};