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