本文主要是介绍【数学 排列组合】1643. 第 K 条最小指令，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
本文涉及知识点
数学 排列组合
LeetCode1643. 第 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 个物品的不同方案数。
排列组合
由于只能右移，不能左移，所以一定有col个H。同理有row个V。
本题实质是组合问题：从row+col个位置选择col个位置放H，其它位置放V。
可以先通过帕斯卡法则，余下处理好15以内的组合。
strRet是返回值
代码
核心代码
template<class Result >
class CCombination
{
public:CCombination(){m_v.assign(1, vector<Result>(1,1));}Result Get(int sel, int total){assert(sel <= total);while (m_v.size() <= total){int iSize = m_v.size();m_v.emplace_back(iSize + 1, 1);for (int i = 1; i < iSize; i++){m_v[iSize][i] = m_v[iSize - 1][i] + m_v[iSize - 1][i - 1];}}return m_v[total][sel];}
protected:vector<vector<Result>> m_v;
};class Solution {
public:string kthSmallestPath(vector<int>& destination, int k) {CCombination<long long> com; int r = destination[0], c = destination[1];string strRet;while (r + c) {if (0 == r) {strRet += string(c, 'H');break;}if (0 == c) {strRet += string(r, 'V');break;}const long long iHas = com.Get(c - 1, r + c - 1);if (k <= iHas) {strRet += 'H';c--;}else {strRet += 'V';r--;k -= iHas;}}return strRet;}
};
测试用例
template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){Assert(v1[i], v2[i]);}}int main()
{vector<int> destination;int k;{Solution sln;destination = { 1, 1 }, k = 2;auto res = sln.kthSmallestPath(destination, k);Assert(string("VH"), res);}{Solution sln;destination = { 1, 1 }, k = 1;auto res = sln.kthSmallestPath(destination, k);Assert(string("HV"), res);}{Solution sln;destination = { 2, 3 }, k = 1;auto res = sln.kthSmallestPath(destination, k);Assert(string("HHHVV"), res);}{Solution sln;destination = { 2, 3 }, k = 2;auto res = sln.kthSmallestPath(destination, k);Assert(string("HHVHV"), res);}{Solution sln;destination = { 2, 3 }, k = 3;auto res = sln.kthSmallestPath(destination, k);Assert(string("HHVVH"), res);}
}
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
|---|
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
这篇关于【数学 排列组合】1643. 第 K 条最小指令的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
