LCP:60 排列序列[leetcode-4]

LCP:60 排列序列

给出集合 [1,2,3,...,n],其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下:

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

给定 nk,返回第 k 个排列。

示例 1:

输入:n = 3, k = 3
输出:"213"

示例 2:

输入:n = 4, k = 9
输出:"2314"

示例 3:

输入:n = 3, k = 1
输出:"123"

最近电脑坏了,去修理好久,所以最近没更leetcode啊,我的绿屏计划都没了🥲

关于0基数和1基数的思考

计算机中常常从0开始计数,而我们在表述中往往从1开始计数,对于问题的转换,我们推荐从问题的一开始就统一基数,如果不统一会给后面的代码带来不必要的麻烦。

比如这个问题,K=9是什么基数,显然来看,是1基数。我们在处理的时候,就要先一步来把K=9转化为0基数的K=8,因为后面我们基于数组的算法就是0基数,不在开头统一绝对让人迷惑。相信你也看出来了

(0基数计数)=(1基数计数)-1;
解题思考
  • 从上到下的排列,同一个开头的数字有几个?当然是余下的N-1个数字的全排列了,(N-1)!个嘛

  • 所以第K(1)的开头在哪里?那就是求K-1(0)的开头在哪里? 显然

    对于

    vector<char> vecc = { '1','2','3','4','5','6','7','8','9' };
    

    b e g i n n u m = v e c c [ k ( n − 1 ) ! ] beginnum=vecc[\frac{k}{(n-1)!}] beginnum=vecc[(n1)!k]

  • 下一步,每个数字只会出现一次,故出现完就要移除

  • 下一步是递归,算出来第一个数字,那接下来确定第二个数字,n变为n-1,k变为k%(n-1)! ,参与递归即可

  • 上面的索引是对次序而言的,如果第一位是3,那余下的数字是1246789,若算出k/(n-1)!=3,那实际上的数字是5(这点比较关键读者可以思考一下)

  • 在这里插入图片描述

代码
class Solution {
public:vector<int> tannum = { 1,1,2,6,24,120,720,5040,40320,362880 };vector<char> vecc = { '1','2','3','4','5','6','7','8','9' };//记得把ans设为对象内变量,这也递归调用的都是这个string ans;void getPermutation_T(int n, int k){if (n == 0) return;int tnum = k / tannum[n - 1];ans += vecc[tnum];//每个数字只会出现一次,故排上之后就应该删除vecc.erase(vecc.begin() + tnum);getPermutation_T(n - 1, k % tannum[n - 1]);}string getPermutation(int n, int k) {//预处理getPermutation_T(n, k - 1);return ans;}
};

效果

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/409027.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

09 复合查询

前面的查询都是对一张表进行查询&#xff0c;但这远远不够 基本查询回顾 查询工资高于500或岗位为MANAGER的雇员&#xff0c;同时还要满足他们的姓名首字母为大写的J select * from EMP where (sal>500 or job‘MANAGER’) and ename like ‘J%’; 按照部门号升序而雇员的…

【git】git进阶-blame/stash单个文件/rebase和merge/cherry-pick命令/reflog和log

文章目录 git blame查看单个文件修改历史git stash单个文件git rebase命令git rebase和git merge区别git cherry-pick命令git reflog和git log区别 git blame查看单个文件修改历史 git blame&#xff1a;查看文件中每行最后的修改作者 git blame your_filegit log和git show结合…

基本数据类型及命令

String String 是Redis最基本的类型&#xff0c;Redis所有的数据结构都是以唯一的key字符串作为名称&#xff0c;然后通过这个唯一的key值获取相应的value数据。不同的类型的数据结构差异就在于value的结构不同。 String类型是二进制安全的。意思是string可以包含任何数据&…

requests库

一、pycharm导入requests库 在终端下输入pip install requests 按回车即可导入。 如果使用pip list 可以查到requests库即导入成功。 二、requsets的get请求 url为我们要请求的网址&#xff0c;headers用于伪造请求头&#xff0c;有的网址拒绝爬虫访问。 # # GET # import r…

【JAVA基础】四则运算符

文章目录 四则运算结合运算符自增运算符关系和boolean运算符 四则运算 在java当中&#xff0c;使用运算符、-、*、/ 表示加减乘除&#xff0c;当参与 / 运算的两个操作数都是整数的时候&#xff0c;表示整数除法&#xff1b;否则表示浮点数。整数的求余操作用 % 表示。 Syste…

svn使用教程学习

如何撤销未提交的本地修改&#xff1f; 点击svn提交&#xff0c;双击文件&#xff0c;可以查看准备提交的修改内容。 如何撤销已经提交的内容&#xff1f; 选择‘复原此版本做出的修改’&#xff1a; 但是&#xff0c;这个只是复原在本地了&#xff0c;我们需要提交上去&…

【大模型理论篇】Mixture of Experts(混合专家模型, MOE)

1. MoE的特点及为什么会出现MoE 1.1 MoE特点 Mixture of Experts&#xff08;MoE&#xff0c;专家混合&#xff09;【1】架构是一种神经网络架构&#xff0c;旨在通过有效分配计算负载来扩展模型规模。MoE架构通过在推理和训练过程中仅使用部分“专家”&#xff08;子模型&am…

C语言 | Leetcode C语言题解之第355题设计推特

题目&#xff1a; 题解&#xff1a; typedef struct {int tweetId;int userId; } Tweet;typedef struct {int* dict[501];Tweet* tweetList;int tweetListLen; } Twitter;Twitter* twitterCreate() {Twitter* obj malloc(sizeof(Twitter));for (int i 0; i < 501; i) {ob…

在vscode上便捷运行php文件

目录 前言 1. 准备工作 2. 创建文件 3. 下载插件 4.设置访问配置文件 5. 配置默认浏览器 6. 进行验证 前言 对于学习安全的我们来说,部署环境,靶场,和配置环境都是习以为常的一件事情,平时访问靶场都是通过小皮来,今天突想着最近需要对一些漏洞的原理进行研究,所以需要能够…

iOS 17.6.1版本重发,修复高级数据保护错误

今日&#xff0c;苹果没有带来iOS 17.6.2的更新&#xff0c;而是重新发布了iOS 17.6.1版本&#xff0c;本次升级版本号为21G101&#xff0c;高于第一版的21G93。距离初版发布相隔一周半时间。 在 iOS / iPadOS 17.6.1 的更新日志&#xff0c;苹果公司写道&#xff1a;“此更新包…

【生日视频制作】一排美女在越野车上跳舞拉横幅条幅AE模板修改文字软件生成器教程特效素材【AE模板】

一排美女在越野车上跳舞拉条横幅生日视频制作教程AE模板改字 怎么如何做的【生日视频制作】一排美女在越野车上跳舞拉横幅条幅AE模板修改文字软件生成器教程特效素材【AE模板】 生日视频制作步骤&#xff1a; 安装AE软件下载AE模板把AE模板导入AE软件修改图片或文字渲染出视频…

怎样更改电脑的MAC地址?

怎样更改电脑的MAC地址&#xff1f; 电脑的机器码是可以修改的。 操作步骤&#xff1a; 1、通过按WINR键&#xff0c;调来电脑的接运行窗口&#xff0c;打开CMD命令来查看机器码。 2、命令提示符窗口里输入ipconfig /all&#xff0c;回车&#xff0c;即可显示出当前电脑的网…

Linux内核定时器、阻塞_非阻塞IO

一.内核时间管理 Linux 内核中有大量的函数需要时间管理,比如周期性的调度程序、延时程序、对于我们驱动编写者来说最常用的定时器。硬件定时器提供时钟源,时钟源的频率可以设置, 设置好以后就周期性的产生定时中断,系统使用定时中断来计时。中断周期性产生的频率就是系统频率…

Bootstrap 滚动监听(Scrollspy)插件

滚动监听&#xff08;Scrollspy&#xff09;插件&#xff0c;即自动更新导航插件&#xff0c;会根据滚动条的位置自动更新对应的导航目标。其基本的实现是随着您的滚动&#xff0c;基于滚动条的位置向导航栏添加 .active class。 如果您想要单独引用该插件的功能&#xff0c;那…

【前端】文件上传框架plupload使用(前后端交互)

这个框架是用来给前端设置文件上传的按钮的。 首先要明白&#xff0c;前端向后端发送请求的方式有get和post&#xff0c;两者的区别在于&#xff0c;前者只能在网址中携带参数&#xff0c;后者是在请求体body中携带参数。 Plupload向后端发送请求是post请求方式&#xff0c;发送…

【Python】从基础到进阶(六):深入理解Python中的面向对象编程(OOP)

&#x1f525; 个人主页&#xff1a;空白诗 文章目录 一、引言二、面向对象编程概述1. 什么是面向对象编程&#xff1f;面向对象的三大基本特性 2. 类和对象3. 类的属性与方法 三、继承与多态1. 继承2. 多态 四、封装与数据隐藏1. 封装2. 数据隐藏 五、案例&#xff1a;员工管理…

华为自研仓颉编程语言测试版上线,计划持续到10月21号

现如今&#xff0c;编程语言作为构建软件世界的基石&#xff0c;其重要性不言而喻。 而华为&#xff0c;作为全球领先的信息与通信技术&#xff08;ICT&#xff09;解决方案提供商&#xff0c;其在技术创新上的每一步都备受瞩目。最近&#xff0c;华为再次成为焦点&#xff0c…

USB3.0硬件简单概述

关于USB2.0&#xff0c;小白在之前的文章简单的描述过。关于USB3.0&#xff0c;今天小白也简单的介绍下。 相比较于USB2.0&#xff0c;USB3.0有了很大的变化。信号端USB3.0除了包含USB2.0的四根信号&#xff0c;还新增了2对差分信号SSRXN SSRXP SSTXN SSTXP以及GND_DRAIN(信号…

Flask返回Json格式字符,中文导致unicode乱码问题

一.问题描述 或者直接返回json格式的字符串 从上图可以看出&#xff0c;当flask实现的接口响应中存在中文时&#xff0c;接口返回json字串的中文为unicode乱码。 二.问题解决 百度搜索了很多&#xff0c;原来在创建flask app时使用json格式的字符串&#xff0c;默认是ascii编…

金融科技 API 接口:提升金融服务效率的关键

金融科技是应用技术手段和创新理念来提升金融服务效率的重要途径。而其中的API接口则是实现金融科技的关键。API接口的简单定义是提供计算机程序之间通信的规范和工具&#xff0c;提供一种方法和数据的交互形式&#xff0c;以便开发人员能够利用现有的软件来创建新的应用和服务…