本文涉及知识点
数学 排列组合
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++**实现。
