【数学排列组合】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

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛