力扣算法题—060第K个排列

力扣算法题—060第K个排列

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

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

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

给定 n 和 k,返回第 k 个排列。

说明:

  • 给定 n 的范围是 [1, 9]。
  • 给定 的范围是[1,  n!]。

示例 1:

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

示例 2:

输入: n = 4, k = 9
输出: "2314"
 1 #include "_000库函数.h"  2  3 //一打眼看到题目描述,就想起用排列算法  4 //时间有点长588ms  5  6 class Solution {  7 public:  8 string getPermutation(int n, int k) {  9 vector<int>v; 10 for (int i = 1; i <= n; ++i) 11  v.push_back(i); 12 --k; 13 while (next_permutation(v.begin(), v.end()) && --k); 14 string s = ""; 15 for (auto a : v) 16 s += a + '0'; 17 return s; 18  } 19 }; 20 21 //用一下递归 22 class Solution { 23 public: 24 string getPermutation(int n, int k) { 25 vector<int>v; 26 for (int i = 1; i <= n; ++i) 27  v.push_back(i); 28 Combin(v, 1, 0); 29 string s = ""; 30 for (auto a : v) 31 s += a + '0'; 32 return s; 33  } 34 void Combin(vector<int>&v, int k, int s) { 35 if (!k)return; 36 if (s >= v.size())--k; 37 for (int i = s; i < v.size(); ++i) { 38  swap(v[i], v[s]); 39 Combin(v, k, s + 1); 40  swap(v[i], v[s]); 41  } 42  } 43 }; 44 45 //博客答案,没怎么看懂 46 //后期看懂再更新 47 //12ms 48 class Solution { 49 public: 50 string getPermutation(int n, int k) { 51 string res; 52 string num = "123456789"; 53 vector<int> f(n, 1); 54 for (int i = 1; i < n; ++i) f[i] = f[i - 1] * i; 55 --k; 56 for (int i = n; i >= 1; --i) { 57 int j = k / f[i - 1]; 58 k %= f[i - 1]; 59  res.push_back(num[j]); 60 num.erase(j, 1); 61  } 62 return res; 63  } 64 }; 65 66 67 void T060() { 68  Solution s; 69 cout << s.getPermutation(3, 3) << endl; 70 cout << s.getPermutation(4, 9) << endl; 71 }

 

转载于:https://www.cnblogs.com/zzw1024/p/10655043.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/101001.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Eclipse使用技巧–代码自动补全功能

    Eclipse使用技巧–代码自动补全功能1、在“触发代码提示”允许的范围之内,空格键和回车键就是快捷键。2、补全代码功能需设置“AutoActivationtriggersforjava”。3、“AutoActivationtriggersforjava”这个选项就是指触发代码提示的的选项,把“.”改成“.abcdefghijklmnopqrstuvwxyz(”的意思,就是指遇到26个字母和“.与(”这些符号就触发代码提示功能了。4、代码提示选项补充完整后,输入关键字即可得到提示功能,得到提示功能后,回车键与空格键就是

  • idea激活码20213月最新在线激活「建议收藏」

    idea激活码20213月最新在线激活,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • 一行脚本实现远程开机

    一行脚本实现远程开机出差在外,想远程家里的电脑,却关机了,怎么办?

  • 时间序列大数据平台建设经验谈

    时间序列大数据平台建设经验谈版权声明:本文由本人撰写并发表于2018年1月刊的《程序员》杂志,本文版权归《程序员》杂志所有,未经许可不得转载。引言在大数据的生态系统里,时间序列数据(TimeSeriesData,简称TSD)是很常见也是所占比例最大的一类数据,几乎出现在科学和工程的各个领域,一些常见的时间序列数据有:描述服务器运行状况的Metrics数据、各种IoT系统的终端数据、脑电图、汇率、股价、气象和天

  • python贪吃蛇游戏代码详解外加中文_Python贪吃蛇代码

    python贪吃蛇游戏代码详解外加中文_Python贪吃蛇代码#!/usr/bin/envpythonimportpygame,sys,time,randomfrompygame.localsimport*#定义颜色变量redColour=pygame.Color(255,0,0)blackColour=pygame.Color(0,0,0)whiteColour=pygame.Color(255,255,255)greyColour…

  • ubuntu安装中文输入法搜狗_中文输入法怎么调出来

    ubuntu安装中文输入法搜狗_中文输入法怎么调出来请注意命令中不应该的空格可能导致命令不合法!一、检查fctix框架首先,要安装中文输入法,必须要保证系统上有fctix。fctix是一个以GPL方式发布的输入法框架,安装fctix后可以为操作系统的桌面环境提供一个灵活的输入方案,解决在GNU/Linux环境下安装中文输入法的问题。win+a打开所有应用程序,找到Language…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号