-
LeetCode 全排列,下一个排列,第k个排列等问题(C++)
2020-09-17 20:44:08给定一个 没有重复 数字的序列,返回其所有可能的全排列。 示例: 输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 解题思路 代码实现 class Solution { public: void ...1、全排列
问题描述
给定一个没有重复数字的序列,返回其所有可能的全排列。
示例:
输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
解题思路
- 基本思路是递归加回溯。
- 这个问题转化为从左到右
n
个空行,n
个数,每个数每次都只能使用一次,依次放入到所有的不同的n
个空行中,返回所有的可能排列结果,即为全排列。使用函数递归和回溯法来解决这个问题。 - 随着递归的深入,直到元素序列只剩下最后两个时,将其交换。递归回退到上一层。随着循环,将在该层递归的前提下,序列从左到右依次与该层递归中的序列第一个元素交换,每交换一次后,再次进入递归将这这种情况下的所有可能结果随着递归排列完毕。在以该层递归的所有情况排列完毕后,递归函数回退到再上一层,再进行漫长地以该层递归为首的元素与其后面的所有元素交换再递归。以此类推,直到整个序列中的第一个元素与所有元素交换完毕并依次完成所有全排列后,算法结束,全排列完成。
- 下图是
LeetCode
中的官方题解中的动态图。
代码实现
class Solution { public: void backtrack(vector<vector<int>>& res, vector<int>& nums, int index, int len){ if (index == len) { res.push_back(nums); return; } for (int i = index; i < len; i++) { // 动态维护数组 swap(nums[i], nums[index]); // 继续递归填下一个数 backtrack(res, nums, index + 1, len); // 撤销操作 swap(nums[i], nums[index]); } } vector< vector<int> > permute(vector<int>& nums) { vector< vector<int> > res; int len = nums.size(); backtrack(res, nums, 0, len); return res; } }; //他如果输入的是{1, 2, 3}的话,打印结果是: /* 1 2 3 1 3 2 2 1 3 2 3 1 3 2 1 3 1 2 请按任意键继续. . . */
运行截图
在VS2013上的运行情况
#include<iostream> #include<vector> #include<algorithm> using namesapce std; void backtrack(vector< vector<int> > &res, vector<int> &nums, int index, int len){ if (index == len){ res.push_back(nums); return; } for (int i = index; i < len; i++){ swap(nums[i], nums[index]); backtrack(res, nums, index + 1, len); swap(nums[i], nums[index]); } } vector< vector<int> > permute(vector<int>& nums){ vector< vector<int> > res; int len = nums.size(); backtrack(res, nums, 0, len); return res; } void main() { vector< vector<int> > res; vector<int> nums = { 1, 2, 3, 4 }; res = permute(nums); for (int i = 0; i < res.size(); i++){ for (int j = 0; j < res[i].size(); j++){ cout << res[i][j] << " "; } cout << endl; } system("pause"); return; } /* 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 3 2 1 4 2 3 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 3 1 2 4 1 3 3 2 1 4 3 2 4 1 3 1 2 4 3 1 4 2 3 4 1 2 3 4 2 1 4 2 3 1 4 2 1 3 4 3 2 1 4 3 1 2 4 1 3 2 4 1 2 3 请按任意键继续. . . */
2、全排列 II
问题描述
给定一个可包含重复数字的序列,返回所有不重复的全排列。
示例:
输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]
解题思路
- 两种思路,提交结果时间复杂度都差不多。分别是在存储结束后去重和在存储的过程中使用集合来去重。???
-思路改天再缕缕。
代码实现(1)
class Solution { public: vector<vector<int>> ans; vector<vector<int>> permuteUnique(vector<int>& nums) { dfs(nums, 0); return ans; } void dfs(vector<int> nums, int idx) { int n = nums.size(); if (idx == n) ans.emplace_back(nums); unordered_set<int> s; for (int i = idx; i < n; ++i) { if (s.find(nums[i]) != s.end()) continue; //剪枝 s.insert(nums[i]); vector<int> tmp = nums; swap(tmp[idx], tmp[i]); dfs(tmp, idx + 1); } } };
运行截图
代码实现(2)
class Solution { public: void backtrack(vector< vector<int> >& res, vector<int> & nums, int index, int len){ if(index == len){ res.push_back(nums); return; } for(int i = index; i < len; i++){ if((i + 1) != len and nums[i] == nums[i + 1]) continue; swap(nums[i], nums[index]); backtrack(res, nums, index + 1, len); swap(nums[i], nums[index]); } } vector<vector<int>> permuteUnique(vector<int>& nums) { vector< vector<int> > res; sort(nums.begin(), nums.end()); int len = nums.size(); backtrack(res, nums, 0, len); sort(res.begin(), res.end()); vector< vector<int> >::iterator iter = res.begin(); iter = unique(res.begin(), res.end()); vector< vector<int> > ans(res.begin(), iter); return ans; } };
运行截图
3、第k个排列
问题描述
给出集合
[1,2,3,…,n]
,其所有元素共有n!
种排列。按大小顺序列出所有排列情况,并一一标记,当
n = 3
时, 所有排列如下:"123" "132" "213" "231" "312" "321" 给定 n 和 k,返回第 k 个排列。
说明:
给定 n 的范围是 [1, 9]。 给定 k 的范围是[1, n!]。
示例 1:
输入: n = 3, k = 3 输出: "213"
示例 2:
输入: n = 4, k = 9 输出: "2314"
解题思路
- 首先用
vector
容器存储1
到n
数字。 - 定义一个计算阶乘的函数,用于计算每位的阶乘数。
k
值对n-1
位的阶乘数取整,该整数就是第一位应该从vector
中所取数字的下标。- 将该作为下标的数字所对应的
vector
容器取出,存放到string
容器中,将该数字从vector
中移除。 (k-1)
值对n-1
位的阶乘数取余即为下一轮循环中的开始k
值,每次循环n
减1
,直到n
为0
为止。k-1
是边界的一个处理,比如n=4,k=6
时,输出的排列字符串应该是1
开头的排列的最后一个,如果用k/(n-1)!
的话,则会输出第一个字符为2
,所以,统一使用(k-1)/(n-1)!
。因为用的是闭区间[]
,不减1
的话边界统一不起来,会成为[)
。
代码实现
class Solution { public: int getnum(int n){ // 求阶乘函数 int ans = 1; for(int i = 1; i <= n; i++) ans *= i; return ans; } string getPermutation(int n, int k) { vector<int> v; for(int i = 1; i <= n; i++) v.push_back(i); string ans; while(n){ int t = (k - 1) / getnum(n - 1); ans += to_string(v[t]); v.erase(v.begin() + t); k -= (t * getnum(n - 1)); n--; } return ans; } };
运行截图
4、下一个排列
问题描述
实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须原地修改,只允许使用额外常数空间。
以下是一些例子,输入位于左侧列,其相应输出位于右侧列。
1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1
解题思路
- 这种全排列的规则就是最开始是完全正序的,然后从右向左依次逐一去逆序,这也满足递归思想,后面的
n
个数全部为逆置序列说明穷举了所有排列可能,此时将倒数第n+1
个数与后面的某一个进行交换,此时后面的n
个数又将呈现为正序排列情况,以此类推,循环,直到序列中所有元素均为逆序。 - 所以,求第
k
个排列的下一个排列,就是从右向左找到第一个出现逆序的元素,用下标i
来指向该元素,则说明i
后面的素所有元素已经全部逆序,再次从右向左找到第一个大于等于nums[i]
的元素,用下标j
来指向,将其两两交换,nums[j]
即为下一个需要跃进的元素。交换后,nums[j]
后面的元素两端由右向左,由左向右,两两交换,即可把后面的逆序转化为正序。
代码实现
class Solution { public: void reverse(vector<int>& nums, int start) { int i = start, j = nums.size() - 1; while (i < j) { swap(nums[i], nums[j]); i++; j--; } } void nextPermutation(vector<int>& nums) { int i = nums.size() - 2; while(i >= 0 and nums[i + 1] <= nums[i]) i--; if(i >= 0){ int j = nums.size() - 1; while(j >= 0 and nums[j] <= nums[i]) j--; swap(nums[i], nums[j]); } reverse(nums, i + 1); } };
运行截图
-
LeetCode题解-全排列的第k个数字(全排列变体)
2017-12-11 13:47:30* LeetCode60 n个数的排列组合找出第k个排列 * The set[1,2,3,…,n]contains a total of n! unique permutations. By listing and labeling all of the permutations in order, We get the following sequence ...题目
/** * LeetCode60 n个数的排列组合找出第k个排列 * The set[1,2,3,…,n]contains a total of n! unique permutations. By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3): "123" "132" "213" "231" "312" "321" Given n and k, return the k th permutation sequence. Note: Given n will be between 1 and 9 inclusive. 时间限制:1秒 */
分析
- 乍看是1~N这N个数字的全排列
- 变化是,每排好一个就计数,计数到k就输出当前排好的这个数
- 注意,如何控制数字按从小到大出现?在算法思维(递归)训练:输出字符串字符的全排列中无需考虑顺序,而且经过实验输出的数字并非完全按从小到大排列。所以需要微调swap函数
代码
public class PermutationSequence { int count; String result; public String getPermutation(int n, int k) { char[] arr = new char[n]; for (int i = 0; i < n; i++) arr[i] = (char) ('1' + i); permutation(arr, 0, k); return result; } private void permutation(char[] arr, int index, int cc) { //至于什么时候输出,要考虑清楚 //考虑:只有所有位置上的字符都确认即index到达末尾,才算是排好一种情况 if (index == arr.length) { count++; // System.out.println(String.valueOf(arr)); if (count == cc) result = String.valueOf(arr); } //现在index之前的字符都已就位,把之后的每个字符都交换到index这个位置 for (int k = index; k < arr.length; k++) { //尝试交换 swap1(arr, index, k); //交换之后index这个位置就定好了,接下来的事就是递归去解决index+1位置开始的全排列就好了 permutation(arr, index + 1, cc); // 前面我们尝试交换,把全排列求出来了,交换时只尝试了一个字符,因此for循环继续之前要换回来,继续尝试交换下一个字符 swap2(arr, index, k); } } private void swap1(char[] arr, int index, int k) { char tmp = arr[k]; //用插入法不改变后续元素的大小顺序 for (int i = k; i > index; i--) { arr[i] = arr[i - 1]; } // arr[k] = arr[index]; arr[index] = tmp; } private void swap2(char[] arr, int index, int k) { char tmp = arr[index]; //用插入法不改变后续元素的大小顺序 for (int i = index; i < k; i++) { arr[i] = arr[i + 1]; } arr[k] = tmp; } public static void main(String[] args) { Instant now = Instant.now(); //考虑极限情况消耗的时间:约19毫秒 System.out.println(new PermutationSequence().getPermutation(9,362880)); //结果应该是987654321,362880=9! System.out.println("毫秒:"+(Instant.now().toEpochMilli()-now.toEpochMilli())); } }
-
LeetCode 60. Permutation Sequence 全排列的第k个
2018-02-17 21:22:06求n位数的第k个全排列利用 n个数字的全排列为n!我们从第一个开始选假设n =3。k=5"123""132""213""231""312""321"我们要确定第一位数是什么。我们知道...求n位数的第k个全排列
利用 n个数字的全排列为n!
我们从第一个开始选
假设n =3。k=5
"123"
"132"
"213"
"231"
"312"
"321"
我们要确定第一位数是什么。
我们知道2的阶乘是 2
即每次跨越2个。
所以(5-1)/2=2
即我们跨越了2个 2
则所选数字为 第3个可选数字(用vis去查找可选数字)
注意最后一个数字要单独去找。
class Solution { public: string getPermutation(int n, int k) { int num[11], vis[11], i, j, index; memset(vis,0,sizeof(vis)); num[0] = 1; for(i = 1;i <= 9; i++){ num[i] = num[i-1] * i; } num[1] = 1; string ans; i = n-1; while(i > 0){ index = (k-1)/num[i]; k = k - index * num[i]; for(j = 1;j <= n;j++){ if(!vis[j]){ if(index == 0) break; index--; } } ans += j + '0'; vis[j] = 1; i--; } for(j = 1;j <= n;j++) if(!vis[j]) break; ans += j + '0'; return ans; } };
-
LeetCode—permutation-sequence(全排列的第k个)—java
2018-07-08 00:05:32先把1到n的每个数存入list中,然后后边写一个数字,就可以从里面删掉一个了。 n个数字有n!个排列方式,n-1就有(n-1)!个排列方式, 为了和下标保持一致,需要k--,k/(n-1)!是当前字符的下标(注意是从零开始啊,...题目描述:
The set[1,2,3,…,n]contains a total of n! unique permutations.
By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):- "123"
- "132"
- "213"
- "231"
- "312"
- "321"
Given n and k, return the k thpermutation sequence.
Note: Given n will be between 1 and 9 inclusive.
思路解析:
- 先把1到n的每个数存入list中,然后后边写一个数字,就可以从里面删掉一个了。
- n个数字有n!个排列方式,n-1就有(n-1)!个排列方式,
- 为了和下标保持一致,需要k--,k/(n-1)!是当前字符的下标(注意是从零开始啊,下标0对应的数字1)
- 下一次的k就可以更新为 k%(n-1)!,循环n次
- 需要一个times表示每次更新阶乘的除数。
代码:
import java.util.*; public class Solution { public String getPermutation(int n, int k) { k--; List<Integer> list = new ArrayList<Integer>();//注意存储1-n StringBuilder s = new StringBuilder(); int times = n-1; for(int i=1;i<=n;i++){ list.add(i); } int factorail = 1;//阶乘 for(int i=2;i<n;i++){//不要×n factorail*=i; } while(times>=0){ int indexList = k/factorail; s.append(list.get(indexList)); list.remove(indexList); k=k%factorail; if(times!=0){ factorail/=times; } times--; } return s.toString(); } }
-
LeetCode:60 第k个排列 全排列与康托展开
2020-03-01 15:44:28给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。 按大小顺序列出所有...给定 n 和 k,返回第 k 个排列。 说明: 给定 n 的范围是 [1, 9]。 给定 k 的范围是[1, n!]。 示例 1: 输入: n = 3, k = 3 输出: “213... -
leetcode 60 万恶的全排列+ 找第K个全排列
2019-04-26 11:50:04代码学习于 : ... 规律和 例子也在那篇博客... // 在其后的排列中,找第k个 res.push_back(nums[j]); nums.erase(j,1); } return res; } }; int main(){ Solution s; cout (3,3); return 0; } -
数据结构与算法[LeetCode]—Permutation Sequence 求n个数的全排列中第K个序列
2014-06-18 14:38:26思路1:可以借鉴并调用先前的Next Permutation的方法,求第K个序列,那么从第一个序列开始,调用K-1次Next Permutation。但是这显然不是题意想要的。 思路2:采用 “康托展开的方法” :全排列的编码与解码 ... -
LeetCode 60 n个数的第k个全排列;
2018-06-01 09:37:23思路:1、int index=k/dp[i];迭代找出它是属于nums数组中...是以index为开始的 第k个全排列;class Solution { public: string getPermutation(int n, int k) { string result=""; if(n<=0||k... -
Leetcode初学——第K个排列
2020-02-11 11:36:01这道题我第一个想到的方法是回溯法,因为我们之前做过一道全排列的题,这个题就只是取全排列中的第K个情况 为了方便减少时间的损耗,我还进行了剪枝,计算出第K个情况后就不再计算 class Solution { private ... -
leetcode-60 第k个排列
2019-12-18 17:41:32以前做全排列的题是用的递归但是递归的全排列的顺序是 123 132 213 231 321 312 它不是按大小排序的所以不太适合这道题 可能是我写的递归不适合 我看别人的题解有用递归的 这道题我是用的找规... -
Leetcode:The set[1,2,3,…,n]contains a total of n! unique permutations.不重复元素的全排列的第k个排列
2019-08-30 19:23:23集合[1,2,3,…,n]一共有n!...现在给出n和k,请返回第k个排列 注意:n在1到9之间 以下方法运行结果均正确无误,但是部分方法运行超时,仅仅提供思路参考 方法一:通过套用回溯法基本框架获取排列结... -
leetcode 60:第k个排列
2018-10-31 10:07:52=24 第一个元素应该为50/24+1 , 也就是3,代表的是没使用数组的第3个元素,也即为3,k=50%24=2 第二个元素(n-2)!=6 元素应该为2/6+1 ,也就是1 代表的是没使用的数组的第1个元素,也即1 ,k=2%... -
LeetCode | Permutation Sequence(找到全排列中的第k个排列)
2014-08-11 16:49:16假设有n个元素,第K个permutation是 a1, a2, a3, ..... ..., an 那么a1是哪一个数字呢? 那么这里,我们把a1去掉,那么剩下的permutation为 a2, a3, .... .... an, 共计n-1个元素。 n-1个元素共有(n-1)!... -
LeetCode 中级 - 第k个排列(60)
2019-03-29 21:33:00可以用数学的方法来解, 因为数字都是从1开始的连续自然数, 排列出现的次序可以推 算出来, 对于n=4, k=15 找到k=15排列的过程: 1 + 对2,3,4的全排列 (3!...个) 3, 1 + 对2,4的全排列(2!个) 3 +... -
leetcode_60. Permutation Sequence 找n的全排列中的第k个序列
2016-11-14 00:13:17def getPermutation(self, n, k): #找全排列中的第k个序列 """ :type n: int :type k: int :rtype: str """ res = '' #存储第k个序列 nums = [] for i in range(n) : #将... -
LeetCode60.第k个排列(Java)
2020-07-06 21:58:27给定 n 和 k,返回第 k 个排列。 说明: 给定n的范围是[1,9]. 给定k的范围是[1,n!]. 解题思路 这道题明显考察的是全排列,但是用递归暴力找出所有排序是比较不好写的,因为要返回字符串String, -
leetcode 60. 第k个排列 dfs剪枝 O(n^2)
2020-09-06 21:16:09第k个排列 给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。 按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下: "123" "132" "213" "231" "312" "321" 给定 n 和 k,返回第 k 个排列。 ... -
[回溯][康托展开法]leetcode60:第k个排列(medium)
2019-11-11 21:50:02康托展开是一个全排列到一个自然数的双射,常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序,因此是可逆的。 对于n=3,k=3,我们将k减1(k--)表示k之前有k-1个排列,... -
LeetCode60 第k个排列
2020-04-26 20:57:54* 使用力扣第46题:全排列,即使用回溯搜索思想,依次得到全排列,输出所求的第k个全排列 * 但事实上,我们不必求出所有全排列,基于以下几点考虑: * 1、我们知道所求排列一定在叶子结点处得到。事实上,进入每一个... -
leetcode 60 第k个排列
2019-04-16 08:14:00求按字典序生成的第k个排列。 思路一: 先生成所有全排列,然后按字典序排序,取第k个即可。事实证明完全不行,超时。 思路二: 康托展开的逆运算。关于康托展开的有关内容,参考这位兄弟的博客。(n年前... -
LeetCode每日一题 第k个排列 (排列的第三种类型)
2020-09-05 23:34:12一般而言,排列问题有三种情况,全排列,下一个排列,第 k 此排列 这三种情况,他要求将给定的数组按照一定的顺序排列完整,我们按照这个系列把三种方法依次简单介绍一下,做个总结,具体算法可以看之前的文章。... -
Leetcode 第K个排列
2020-01-06 19:48:47给出集合[1,2,3,…,n],其所有元素共有n! 种排列。 ...给定n 和k,返回第k个排列。 首先,我们先理解清楚全排列的过程。给定n=3,则123的全排列有{123,132,213,231,321,312}; 具体先固定住... -
leetcode-第k个排列-康托展开和康托逆展开
2020-04-06 17:08:11乍一眼看,这又是一个类似于全排列的回溯题,第一思路是又使用回溯法递归出全排列的所有情况列一个表,然后根据k来找到第k个排列。 很遗憾的是这种方法,百分之百超时,效率太低,即便是添加了一些到达k就返回的剪枝... -
LeetCode 力扣 60. 第k个排列
2020-02-07 10:23:09这道题的话,是给一个 n,不是输出它的全排列,而是把所有组合从从小到大排列后,输出第 k 个。 解法一 以 n = 4 为例,可以结合下图看一下。因为是从小到大排列,那么最高位一定是从 1 到 4。然后可以看成一组一组... -
leetcode60 第k个排列——康托变换与逆康托变换
2021-01-22 16:45:21leetcode60 第k个排列——康托变换与逆康托变换 康托变换: 给定从1到n的n个自然数,将这些自然数的全排列按字典序从小到大排列,如何写出第k大的那个排列? 自然,最开始的思路是直接按照字典序写出所有的排列,... -
LeetCode 60. 排列序列(全排列的应用)
2020-12-29 17:21:31给定两个数 n 和 k ,让我们求 1 ~ n 的第k个全排列。 首先,对于 n 个数的全排列来说,我们先来看第一个数确定之后,之后的全排列的个数: 以 1 开头的全排列的个数为: (n-1)! 以 2 开头的全排列的个数为: (n-1)!... -
leetcode:60. 第k个排列(回溯)
2021-01-07 15:34:15还是根据排列组合基本问题全排列 II中给的两种方法改编。 代码1(朴素直接修改原来的模板): int all=-1; int f(int nums,vector n,int c,int k,vector& v) {//该往c位置放了 if(c==n.size()-1){ all++; if(all=...
收藏数
82
精华内容
32
-
MySQL 四类管理日志(详解及高阶配置)
-
云开发后台+微信扫码点餐小程序+cms网页管理后台 含后厨端和用户端
-
FFmpeg4.3系列之16:WebRTC之小白入门与视频聊天的实战
-
基于Qt的LibVLC开发教程
-
TWDM-PON中具有ONU迁移的自适应注册
-
Docker安装MySQL并配置my.cnf
-
zjpdistribute.plist
-
VMware vSphere ESXi 7 精讲/VCSA/VSAN
-
在QT5以下版本中设置UTF-8编码正常显示中文
-
谈软件生命周期模型及其选择
-
input输入框聚焦时,输入框占位符内容以动画形式移动到左上角作为标题
-
MySQL 存储过程(创建海量数据实验环境)
-
mybatis核心配置文件约束,mapper文件约束,log4j.properties
-
4:Python编程入门,动手做个虚拟地球——吃透编程规则
-
QT编程思想【C++,基于QT 6】
-
FreeSWITCH-SIP拨号
-
MaxScale 实现 MySQL 读写分离与负载均衡
-
美化nwjs生成的桌面程序安装包
-
ERROR 1045 (28000): Access denied for user ‘root‘@‘localhost‘ (using password: YES)的解决
-
MySQL 事务和锁