【数学 排列组合】1643. 第 K 条最小指令

ops/2024/9/23 16:05:08/

本文涉及知识点

数学 排列组合

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是返回值
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++**实现。


http://www.ppmy.cn/ops/30688.html

相关文章

QT httpServer多线程后台服务器的例子实现

1.需求 1.1 用户需要其他平台&#xff08;web端&#xff09;调用Qt平台的接口&#xff0c;获取想要的数据并实时显示在网页里&#xff0c;比如实时的温湿度&#xff0c;用户数据等 1.2 用户需要在其他平台&#xff08;web端&#xff09;调用Qt平台的接口&#xff0c;下发数据…

《MySQL对数据库中表的结构的操作》

文章目录 一、建表二、查看表结构所有能查看到数据库&#xff0c;表的操作痕迹的本质都是服务器保存下来了这些操作记录。 三、修改表1.改表名字2.添加表记录3.添加表的更多字段4.修改表的字段5. 删除表的字段 总结 以下的数据库表的操作全是基于user_db这个数据库操作的&#…

LangChain 入门6 magic不同格式文件的读取

概述&#xff1a; 除了原始文本数据&#xff0c;可能还希望从其他文件类型&#xff08;如PowerPoint演示文稿或PDF&#xff09;中提取信息。 可以使用LangChain文档加载程序将文件解析为可以输入LLM的文本格式。 基于MIME类型的解析 数据加载 import requestsresponse req…

数据结构之“合并两个有序链表”

一、后插法 1、定义&#xff1a; 通过将新节点逐个插入到链表的尾部来创建链表。 2、特点&#xff1a; &#xff08;1&#xff09;每次申请一个新节点&#xff0c;读入相应的数据元素值 &#xff08;2&#xff09;为了使新节点能够插入到表尾&#xff0c;需要增加一个尾指针 r…

Linux硬盘挂载操作记录

文章目录 1.前置概念2.挂载步骤2.1查看盘信息2.2挂载整个盘到指定目录2.3将盘划分为多个分区并挂载到不同目录2.3.1创建分区2.3.2指定文件系统2.3.3挂载目录 3.删除分区 1.前置概念 分区&#xff1a;分区就是将硬盘划分为多个区域&#xff0c;每个区域都有自己的文件系统&…

JS实现瀑布流布局

瀑布流布局是一种常见的网页布局方式&#xff0c;可以实现页面内容的动态排列&#xff0c;使页面看起来更加美观。下面是一个简单的JS实现瀑布流布局的示例&#xff1a; <!DOCTYPE html> <html lang"en"> <head> <meta charset"UTF-8&quo…

使用Gradio搭建聊天UI实现质谱AI智能问答

使用Gradio搭建聊天UI实现质谱AI智能问答 一、调用智谱 AI API二、使用Gradio搭建聊天UI三、将流式处理添加到交互式聊天机器人 一、调用智谱 AI API 1、获取api_key 智谱AI开放平台网址&#xff1a; https://open.bigmodel.cn/overview 2、安装库pip install zhipuai 3、执…

JAVA顺序表相关习题1

1.笔试题:cvte str1 :welcome to cvte str2:come 描述:删除第一个字符串当中出现的所有的第二个字符串的字符!结果:wlt vt 要求 用ArrayList完成! public class Test {public static List<Character> findSameWords(String u1, String u2){List<Character> listn…