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

力扣1643题:第K小字典序路径(附C++代码与解题思路)

2个月前 (07-13)

力扣1643题:第K小字典序路径(附C++代码与解题思路) 力扣题解 字典序 组合数学 贪心算法 动态规划 第1张

一、题目解读

本题要求生成从原点(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;
    }
};

五、总结

本题巧妙利用组合数预计算与贪心策略,将路径选择转化为组合数比较问题,避免了暴力枚举的指数级复杂度。关键在于理解路径字典序与组合数的对应关系,并通过预计算优化组合数获取效率。时间复杂度O(n^2)(预计算)+O(n)(路径生成),空间复杂度O(n^2)。

原创内容 转载请注明出处

分享给朋友:

相关文章

力扣1137题:动态规划解泰波那契数 高效求解第N项的秘密

力扣1137题:动态规划解泰波那契数 高效求解第N项的秘密

一:重新解读题目泰波那契数列是一个充满数学趣味的递推序列:从第3项开始,每个数均为前三个数的和(即Tₙ₊₃ = Tₙ + Tₙ₊₁ + Tₙ₊₂)。当给定整数n时,需要高效计算出第n项的值。面对此类递...

CSP-J 2019纪念品题解(洛谷P5662):动态规划+完全背包问题的实战应用

CSP-J 2019纪念品题解(洛谷P5662):动态规划+完全背包问题的实战应用

一、题目解读2019年CSP-J的“纪念品”问题(对应洛谷P5662)要求玩家在T天内通过买卖纪念品最大化金币收益。每天可交易N种商品,需计算最优策略下的最终金币数。题目强调动态规划思维与资源分配优化...

洛谷2181题解析:组合数学中顶点交点的计算与代码优化

洛谷2181题解析:组合数学中顶点交点的计算与代码优化

一、题目解读洛谷2181题要求计算n个顶点中任意选择4个顶点确定的交点数量。题目核心在于组合数学的应用,需通过排列组合公式推导结果,同时注意处理大数以避免溢出问题。理解题目中的“交点”定义(由4个顶点...

牛客13271题「删除K个数字的最小数」解题报告:贪心算法与栈的应用(附代码注释)

牛客13271题「删除K个数字的最小数」解题报告:贪心算法与栈的应用(附代码注释)

一、题目解读牛客13271题要求从给定的数字字符串中删除K个数字,使得剩余数字按原顺序排列后得到的最小数。题目核心在于如何在保持数字相对顺序的前提下,通过删除操作得到最优解。需注意结果字符串可能包含前...

2024蓝桥杯省赛B组“传送阵”题解(C++代码+图论算法优化)

2024蓝桥杯省赛B组“传送阵”题解(C++代码+图论算法优化)

一、题目解读2024年蓝桥杯省B组“传送阵”题目要求处理一个包含n个节点的图,节点间存在单向传输关系。每个节点i可传送至a[i]指定的节点,形成可能存在的环结构。题目需求解从任意节点出发能到达的最长路...

洛谷P4551题解题报告:图论与Trie树优化异或路径问题的实战解析

洛谷P4551题解题报告:图论与Trie树优化异或路径问题的实战解析

一、题目解读洛谷P4551题要求在一个无向图中,寻找任意两点路径权值异或后的最大值。题目输入为图的边信息(点数n和n-1条边),每条边包含起点、终点及权值。需输出所有路径中权值异或的最大值。问题核心在...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。