【leetcode】排列序列
给出集合 [1,2,3,...,n],其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下:
"123""132""213""231""312""321"
给定 n 和 k,返回第 k 个排列。
示例 1:
输入:n = 3, k = 3 输出:"213"
示例 2:
输入:n = 4, k = 9 输出:"2314"
示例 3:
输入:n = 3, k = 1 输出:"123"
提示:
1 <= n <= 91 <= k <= n!
解题思路:
例如: n = 4, k = 9
可以知道全排列有:4*3*2*1 = 24种,如下:红色框住的为第9个

从上图可知,以1开头的全排列 (4-1)! = 6 共6种 ;
9 / 6 = 1······3,也就是该数位于2开头的第三个。
同理,第一位2确定后,剩下三位 1 3 4,接下来需要确定第二位;

由上面的图片可知, 1 3 4全排列每一列分别有两个数(3-1)!,3 / 2 = 1······1,可知位于第二列开头的第一个
然后确定第三位 ,第三位则还剩下2个数:1和4;
1和4的全排列:

1 4排列,每类(2-1)! = 1,1 / 1 = 1·····0,可知位于1开头的第一个
最后一位数,只有一种情况: (1-1)! = 1
具体算法如下:
1、定义一个逆康托数组,记录n位数字对应每个数字开头序列的个数,例如4位数prenum[1, 1, 2, 6]
将k值-1,再进行计算,这里-1是为了 9 % 6 = 3,而数组下标从0开始,-1后方便计算。
2、定义一个valid数组[0.....n];记录还没有被使用的数字, 已经使用的需要移除
3、(k -1 ) / prenum[n - i - 1] + 1就是分别计算每一位数字位于那一列;例如 (9 -1)/ 6 + 1= 2,说明第一个数字为2,ans累加vali[2] ,2被使用后erase掉,valid中剩余[0,1,3,4]
然后k记录剩余未计算的数 8 % 6 = 2
k = 2再重复计算,可得到 2/2 + 1 = 2; 再取走valid中的第2个
同理依次取完。
完整代码如下:
class Solution {
public:string getPermutation(int n, int k) {//prenum = {0!, 1!, 2!, 3!, .....(n-1)!}vector<int> pernum(n);pernum[0] = 1;for(int i= 1; i < n; i++) {pernum[i] = pernum[i-1] * i;}//k-- 方便取余后计算k--;string ans;vector<int> valid(n+1);//生成[0,1,2....n]的数组iota(valid.begin(), valid.end(), 0);for(int i = 0; i < n; i++) {int order = k / pernum[n-i-1] + 1;ans += (valid[order] + '0');//用了就从数组中删除valid.erase(valid.begin() + order);k %= pernum[n-i-1];}return ans;}
};
拓展:康托展开,也就是在全排列中,给定一个序列,求该序列位于第几个。
#include <iostream>
#include <string>
using namespace std;class Solution {public://求阶乘int fact(int x) {int ret = 1;for(int i = 2; i <= x; i++) {ret *= i;}return ret;}int getStringId(string str) {int len = str.size();int ans = 0;for(int i = 0; i < len; i++) {int cnt = 0;//记录后面的数有几个比当前的数小;//例如2314 314中只有1个数比第一位小,说明该数位于第二列。for(int j = i + 1 ; j < len; j++) {if(str[j] < str[i]) {cnt ++;}}ans += cnt*fact(len- i -1);}return ans+1;}
};
int main()
{string s;cin >> s;Solution sol;cout << "位于序列第:" << sol.getStringId(s) << " 位" << endl;return 0;
}

相关文章:
【leetcode】排列序列
给出集合 [1,2,3,...,n],其所有元素共有 n! 种排列。 按大小顺序列出所有排列情况,并一一标记,当 n 3 时, 所有排列如下: "123""132""213""231""312""321" 给定…...
【Cesium开发实战】视频融合功能的实现,可自定义位置和视频路径
Cesium有很多很强大的功能,可以在地球上实现很多炫酷的3D效果。今天给大家分享一个视频融合功能。 1.话不多说,先展示 视频融合 2.设计思路 点击绘制开始在地图上绘制视频融合的点位,形成视频播放的区域,双击弹框输入名称和要播放视频的路径,即可对应区域播放对应视频,…...
【秋招笔试题】小明的美食
解析:思维题。由于需要互不相同,每次操作取重复的值与最大值相加即可,这样即可保证相加后不会新增重复的值。因此统计重复值即可。 #include <iostream> #include <algorithm>using namespace std; const int maxn 1e5 5; int…...
基于OpenLCA、GREET、R语言的生命周期评价方法、模型构建及典型案例应用
生命周期分析 (Life Cycle Analysis, LCA) 是评价一个产品系统生命周期整个阶段——从原材料的提取和加工,到产品生产、包装、市场营销、使用、再使用和产品维护,直至再循环和最终废物处置——的环境影响的工具。这种方法被认为是一种“从摇篮到坟墓”的…...
Linux操作系统 -socket网络通信
同一台主机之间的进程 1.古老的通信方式 无名管道 有名管道 信号 2、IPC对象通信 system v 消息队列 共享内存 信号量集 由于不同主机间进程通信 3.socket网络通信 国际网络体系结构: 七层OSI模型(理论…...
【苍穹】完美解决由于nginx更换端口号导致无法使用Websocket
一、报错信息 进行到websocket开发的过程中,遇到了前端报错,无法连接的提示: 经过F12排查很明显是服务端和客户端并没有连接成功。这里就涉及到之前的坑,现在需要填上了。 二、报错原因和推导 应该还记得刚开苍穹的第一天配置前…...
Qt中在pro中实现一些宏定义
在pro文件中利用 DEFINES 定义一些宏定义供工程整体使用。(和在cpp/h文件文件中定义使用有点类似)可以利用pro的中的宏定义实现一些全局的判断 pro中实现 #自定义一个变量 DEFINES "PI\"3.1415926\"" #自定义宏 DEFINES "T…...
bash XXX.sh文件和直接运行XXX.sh的区别
区别: bash XXX.sh 明确说明使用bash作为脚本的解释器不需要文件有执行权限 XXX.sh 需要指定相关解释器。如果第一行是#!/bin/bash则使用bash,如果是#!/bin/sh,则使用sh作为解释器需要有执行权限:通过chmod x 文件名指定 注意: #!是特殊标…...
【Python机器学习】k-近邻算法简单实践——改进约会网站的配对效果
需求背景: XX一直使用约会网站寻找适合自己的约会对象,ta会把人分为3种类型: 不喜欢、魅力一般、非常有魅力 对人分类轴,发现了对象样本的以下3种特征: 1、每年获得的飞行里程数 2、玩视频游戏所耗时间百分比 3、…...
vue3前端开发-小兔鲜项目-登录组件的开发表单验证
vue3前端开发-小兔鲜项目-登录组件的开发表单验证!现在开始写登录页面的内容。首先这一次完成基础的首页按钮点击跳转,以及初始化一些简单的表单的输入验证。后期还会继续完善内容。 1:首先还是准备好login页面的组件代码内容。 <script …...
Winform上位机TCP客户端/服务端、串口通信
Winform上位机TCP客户端/服务端、串口通信 背景 日常练习,着急换工作,心态都快乱了。 工具 串口调试助手 网络调试助手 代码 客户端 using Microsoft.VisualBasic.Logging; using System.Net.Sockets; using System.Text;namespace TcpClientDem…...
Linux基础复习(二)
前言 本文介绍了一下Linux命令行基本操作及网络配置 一、 命令行提示含义 [当前用户主机名 工作目录]$ 若当前用户是root,则最后一个字符为# 否则,最后一个字符为$ 二、常用Linux命令及其解释 修改主机名 一般在创建一台主机后会使用hostname相关命…...
nginx漏洞修复 ngx_http_mp4_module漏洞(CVE-2022-41742)【低可信】 nginx版本升级
风险描述: Nginx 是一款轻量级的Web服务器、反向代理服务器。 Nginx 的受影响版本中的ngx _http_mp4_module模块存在内存越界写入漏洞,当在配置中使用 mp4 directive时,攻击者可利用此漏洞使用使用ngx_http_mp4_module模块处理特制的音频或视…...
网格布局 HTML CSS grid layout demo
文章目录 页面效果代码 (HTML CSS)参考 页面效果 代码 (HTML CSS) <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"…...
Java算法之递归算法-如何计算阶乘的值
上一篇学了递归之后,练习一下递归算法。 题目:使用递归算法计算阶乘的值,也就是5!5*4*3*2*1,直接使用循环是非常简单的,这边练习一下递归算法。 先写一下两个条件 基线条件:等于1的时候返回1…...
python爬虫入门小案例
python爬虫 以下内容仅供学习交流,请勿用作其他用途,若涉及隐私和版权问题,请及时联系我删除 闲来无事,学了学爬虫小知识,适合入门,文笔拙劣,还望见谅 爬虫是什么: 爬取网页上的文字,图片,视频,音频 自动化操作浏览器,比如填写表单,打卡,提高工作效率爬虫的注意事项: 爬虫…...
【昇腾AI创新大赛集训营南京站学习笔记】-Ascend算子开发课程
昇腾AI创新大赛训练营 14:00-14:30 基础知识-理论课 一、CANN 、达芬奇架构和算子 1.AI Core逻辑架构 达芬奇架构包含三部分: 1)计算类:矩阵计算单元(两个矩阵扔进去相乘)、向量计算单元、标量计算单元 2)控…...
系统架构设计师教程 第4章 信息安全技术基础知识-4.5 密钥管理技术4.6 访问控制及数字签名技术-解读
系统架构设计师教程 第4章 信息安全技术基础知识-4.5 密钥管理技术&4.6 访问控制及数字签名技术 4.5 密钥管理技术4.5.1 对称密钥的分配与管理4.5.1.1 密钥的使用控制4.5.1.1.1 密钥标签4.5.1.1.2 控制矢量4.5.1.2 密钥的分配4.5.1.2.1物理方式14.5.1.2.2 物理方式24.5.1…...
C语言日常练习Day13
目录 一、设半径r1.5,圆柱高h3,求圆周长、圆面积、圆球表面积、圆球体积、圆柱体积 二、编写程序,用getchar函数读入两个字符给c1,c2,然后分别用putchar函数和printf函数输出这两个字符 三、输入4个整数,要求按由小…...
map、foreach、filter这些方法你还不知道什么时候该用哪个吗?那就看过来
forEach:主要用于遍历数组并对每个元素执行某种操作,通常用于改变当前数组里的值。它不会返回新数组,而是直接在原数组上进行操作。forEach方法不支持return、break、continue等语句,因为这些语句在forEach中不会…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...
SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信
文章目录 Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket(服务端和客户端都要)2. 绑定本地地址和端口&#x…...
RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill
视觉语言模型(Vision-Language Models, VLMs),为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展,机器人仍难以胜任复杂的长时程任务(如家具装配),主要受限于人…...
并发编程 - go版
1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程,系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...
Qemu arm操作系统开发环境
使用qemu虚拟arm硬件比较合适。 步骤如下: 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载,下载地址:https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...
【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验
Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...
