当前位置: 代码迷 >> 综合 >> LeetCode---全排列(递归、next_permutation、康托展开)
  详细解决方案

LeetCode---全排列(递归、next_permutation、康托展开)

热度:48   发布时间:2024-01-22 01:30:32.0

目录

 

一、递归求全排列

二、next_permutation实现

三、康托展开


一、递归求全排列

46. 全排列

class Solution {vector<vector<int>> ans;public:vector<vector<int>> permute(vector<int>& nums) {perm(nums, 0, nums.size() - 1);return ans;}void perm(vector<int> nums, int left, int right) {if (left == right)ans.push_back(nums);else {for (int i = left; i <= right; i++) {swap(nums[left], nums[i]);perm(nums, left + 1, right);//swap(nums[left], nums[i]);//不是引用的话,不用换回来}}}
};

 

47. 全排列 II

class Solution {vector<vector<int>> ans;public:vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end());perm(nums, 0, nums.size() - 1);return ans;}void perm(vector<int> nums, int left, int right) {if (left == right)ans.push_back(nums);else {for (int i = left; i <= right; i++) {if (i != left && nums[left] == nums[i]) continue; swap(nums[left], nums[i]);perm(nums, left + 1, right);// swap(nums[left], nums[i]);}}}
};

 

二、next_permutation实现

递归总显得没有抓住这类问题的本质;next_permutation是求下一个全排列的库函数,我们要弄清它的原理。


class Solution {
public:template < typename T>bool Next_permutation(T first,T last){if(first == last)return false;//空区间T i = first;i++;if(i == last)return false;//1个元素i = last;i--;while(1){T ii = i;i--;//逆序找出第一个 *i<*ii;if(*i < *ii){T j = last;while(!(*i < *--j));//倒序找到第一个比*i大的元素iter_swap(i,j);//交换*i,*jreverse(ii,last);//ii之后的全部逆序return true;}if(i == first){//进行到最前面了,全部逆序返回falsereverse(first,last);return false;}}}vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(),nums.end());std::vector<std::vector<int> > ans;do{ans.push_back(nums);}while(Next_permutation(nums.begin(),nums.end()));return ans;}};

 

 

31. 下一个排列

class Solution {
public:template < typename T>bool Next_permutation(T first,T last){if(first == last)return false;//空区间T i = first;i++;if(i == last)return false;//1个元素i = last;i--;while(1){T ii = i;i--;//逆序找出第一个 *i<*ii;if(*i < *ii){T j = last;while(!(*i < *--j));//倒序找到第一个比*i大的元素iter_swap(i,j);//交换*i,*jreverse(ii,last);//ii之后的全部逆序return true;}if(i == first){//进行到最前面了,全部逆序返回falsereverse(first,last);return false;}}}void nextPermutation(vector<int>& nums) {Next_permutation(nums.begin(),nums.end());return;}
};

 

 

三、康托展开

 

60. 第k个排列

当然这道题,可以多次调用next_permutation;但是这道题本质是要我们了解 康托展开 的。

class Solution {
public:string getPermutation(int n, int k) {string s;string ans;for(int i = 1;i<=n;++i)s+=('0'+i);// if(k == 1)return s;int f[10];f[0] = 1;for(int i = 1;i<=9;++i)f[i] = f[i-1]*i;k--;for(int i = n;i>=1;--i){int r = k % f[i-1];int t = k / f[i-1];k = r;sort(s.begin(),s.end());ans.push_back(s[t]);s.erase(s.begin()+t);}	return ans;}};