LeetCode排列组合系列算法题整理
面试题 08.07. 无重复字符串的排列组合
无重复字符串的排列组合。编写一种方法,计算某字符串的所有排列组合,字符串每个字符均不相同。
示例:
输入:S = “qwe”
输出:[“qwe”, “qew”, “wqe”, “weq”, “ewq”, “eqw”]
提示:
- 字符都是英文字母。
- 字符串长度在[1, 9]之间。
解法:
这题比较特殊,是字符串,而且没有重复,可以不用回溯,直接插入字母实现全排列,经过观察我们可以发现以下规律。
将每个字母插入到前面字符串所有可能的情况:
例如:“qwe”
第一轮:q
第二轮:将w插入q,有两种情况:wq, qw
第三轮:将e插入wq, qw中去 即:ewq,weq,wqe;eqw,qew,qwe六种情况
代码:
class Solution {
private:
vector res;
public:
void dfs(string& t, string& s, int k){
if(t.length()==s.length()){
res.push_back(t);
return;
}
for(int i=0; i<=t.size(); i++){
string tmp = t.substr(0,i) + s[k] + t.substr(i);
dfs(tmp,s,k+1);
}
}
vector permutation(string s) {
if(s.empty()) return {};
string t = "";
t += s[0];
dfs(t, s, 1);
return res;
}
};
46. 全排列
上一题比较tricky,没有用到真正的排列组合算法,由于情况太特殊了,如果换成数字就没法实现了,所以我们还是看一下正常的题目和解法。
给定一个 没有重复 数字的序列,返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
解法:
和上题一样都是全排列,但是变成了一串数字。处理方法和上一题就不一样了,因为字符串插入很简单,但是数组插入的话就会很费时间,所以就不能投机了,这里用最经典的回溯思路来进行数字的全排列。
算法用dfs,用used数组记录当前数字是否选过,然后一直选到不能选为止,记得要恢复状态。(附件有详细图解)
代码:
class Solution {
private:
vector<vector> res;
public:
void dfs(vector& tmp, vector& used, vector& nums){
if(tmp.size()==used.size()){
res.push_back(tmp);
return;
}
for(int i=0; i<used.size(); i++){="" if(used[i]="=false){" used[i]="true;" tmp.push_back(nums[i]);="" dfs(tmp,used,nums);="" tmp.pop_back();="" }="" vector<vector<int="">> permute(vector& nums) {
res.clear();
if(nums.empty()) return res;
vector tmp;
vector used(nums.size(),false);
dfs(tmp,used,nums);
return res;
}
};
</used.size();></vector
77. 组合
给定两个整数 n 和 k,返回 1 … n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
解法:
组合和排列本来就是分不开的,所以思路和代码和上一题差别不大,判断条件上面有些改变,个数到k就可以插入,然后因为是组合不是排列,所以要判重,这里因为是1~n,所以只要一直递增就行了。(附件有详细图解)
代码:
class Solution {
private:
vector<vector<int>> res;
public:
void dfs(vector<int>& tmp, vector<bool>& used, int k){
if(tmp.size()==k){
res.push_back(tmp);
return;
}
int p = (tmp.empty())?1:tmp.back()+1;
for(int i=p; i<used.size(); i++){
if(used[i]==false){
tmp.push_back(i);
used[i] = true;
dfs(tmp,used,k);
tmp.pop_back();
used[i] = false;
}
}
}
vector<vector<int>> combine(int n, int k) {
vector<bool> used(n+1,false);
vector<int> tmp;
dfs(tmp,used,k);
return res;
}
};
47. 全排列 II
给定一个可包含重复数字的序列,返回所有不重复的全排列。
示例:
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
解法:
和全排列代码类似,但是要考虑重复的情况,每一层dfs的时候,剪掉重复的元素就行了,不重复搜。(附件有详细图解)
代码:
class Solution {
private:
vector<vector<int>> res;
public:
void dfs(vector<int>& tmp, vector<bool>& used, vector<int>& nums){
if(tmp.size()==used.size()){
res.push_back(tmp);
return;
}
for(int i=0; i<used.size(); i++){
if(i>0 && nums[i]==nums[i-1] && !used[i-1])
continue;
if(!used[i]){
used[i] = true;
tmp.push_back(nums[i]);
dfs(tmp,used,nums);
used[i] = false;
tmp.pop_back();
}
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
res.clear();
if(nums.empty()) return res;
sort(nums.begin(),nums.end());
vector<int> tmp;
vector<bool> used(nums.size(),false);
dfs(tmp,used,nums);
return res;
}
};
31. 下一个排列
实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须原地修改,只允许使用额外常数空间。
以下是一些例子,输入位于左侧列,其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
解法:
求字典序选排列的下一个,这里先找数学规律。
首先可以观察到,如果序列是降序的,说明已经是最后一个的排列了,这时候下一个就是第一个有序的数列。
然后如果不是降序的,这时候从后往前找第一个上升的位置,a[i-1]<a[i]的位置,然后再寻找i-1后面比a[i-1]大的最小的那个数的位置j(有点拗口,细品一下不难理解),交换a[i-1],a[j],然后把a[i-1]后面的数从小到大排序。
代码:
class Solution {
public:
void nextPermutation(vector<int>& a) {
if(a.empty() || a.size()<=1) return;
int p = a.size()-1;
while(p-1>=0 && a[p]<=a[p-1])//寻找升序位置
p--;
if(p>0){//判断是不是降序
int q = p;
for(int j = p+1; j<a.size(); j++)
if(a[j]>a[p-1] && a[j]<a[q]){//寻找第二个位置
q = j;
}
int t = a[q];
a[q] = a[p-1];
a[p-1] = t;
}
sort(a.begin()+p,a.end());//排序
}
};
60. 第k个排列
给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下:
“123”
“132”
“213”
“231”
“312”
“321”
给定 n 和 k,返回第 k 个排列。
说明:
- 给定 n 的范围是 [1, 9]。
- 给定 k 的范围是[1, n!]。
示例 :
输入: n = 3, k = 3
输出: “213”
解法:
康拓编码是本题的标准解法,这里不多赘述了,因为一下子讲不清,这里po一个很详细的题解。
https://leetcode-cn.com/problems/permutation-sequence/solution/di-k-ge-pai-lie-by-leetcode/
代码:
class Solution {
public:
string getPermutation(int n, int k) {
vector<int> fac = {0,1,2,6,24,120,720,5040,40320,362880,3628800};
string res;
res.clear();
string s = string("123456789").substr(0,n);
--k;
while(k>0){
int i = k/fac[n-1];
res += s[i];
s.erase(s.begin()+i);
k %= fac[n-1];
--n;
}
return res+s;
}
};
- 点赞
- 收藏
- 关注作者
评论(0)