题目链接
60. 第k个排列
题目描述
解题思路
1.普普通通回溯法
直接看代码即可。
2.回溯+减枝
使用该方法相当于在一大堆答案中,直接找到唯一的可行,所以是不需要回溯的
基于以下几点考虑:
- 所求排列 一定在叶子结点处得到,进入每一个分支,可以根据已经选定的数的个数,进而计算还未选定的数的个数,然后计算阶乘,就知道这一个分支的 叶子结点 的个数:
- 如果 k大于这一个分支将要产生的叶子结点数,直接跳过这个分支,这个操作叫「剪枝」;
- 如果 k小于等于这一个分支将要产生的叶子结点数,那说明所求的全排列一定在这一个分支将要产生的叶子结点里,需要递归求解。
AC代码
1.普普通通回溯法
//1.超时版本
//代码涉及到字符串的增加删除、链表的get、add函数,开销大,可以优化
class Solution {
ArrayList<String> ans = new ArrayList<>();
StringBuffer sb = new StringBuffer();
void dfs(int level, int n, int[] vis){
if(level == n){
ans.add(sb.toString());
}
for(int i = 1; i <= n; i++){
if(vis[i]==0){
vis[i]=1;
sb.append(i);
dfs(level+1,n,vis);
sb.deleteCharAt(sb.length()-1);
vis[i]=0;
}
}
}
public String getPermutation(int n, int k) {
if(n == 0) return "";
int[] vis = new int[n+1];
dfs(0,n,vis);
return ans.get(k-1);
}
}
//2.刚好卡着时间过
//没必要把每个全排列字符串都记录在动态数组中,利用cnt变量,只需要记录cnt==k那一个全排列的字符串
class Solution {
StringBuffer sb = new StringBuffer();
String ans="";
int cnt = 0;
void dfs(int level, int n, int[] vis,int k){
if(level == n){
cnt++;
if(cnt == k) ans = sb.toString();
}
for(int i = 1; i <= n; i++){
if(vis[i]==0){
vis[i]=1;
sb.append(i);
dfs(level+1,n,vis,k);
sb.deleteCharAt(sb.length()-1);
vis[i]=0;
}
}
}
public String getPermutation(int n, int k) {
if(n == 0) return "";
int[] vis = new int[n+1];
dfs(0,n,vis,k);
return ans;
}
}
//优化3.利用数组记录全排列答案,可以省去字符串的增加和删除操作,time:676ms
class Solution {
int[] ans = new int[100];
int[] vis = new int[100];
int cnt = 0;
StringBuffer sb = new StringBuffer();
void dfs(int level,int n,int k){
if(level == n){
cnt++;
if(cnt == k){
for(int i = 0; i < ans.length; i++){
if(ans[i]==0) break;
else sb.append(ans[i]);
}
}
}
for(int i = 1; i <= n; i++){
if(sb.length()!=0) break;
if(vis[i]==0){
vis[i]=1;
//利用数组可以不需要回溯,但需要注意数组的下标是递归的层数level!!!!
ans[level]=i;
dfs(level+1,n,k);
vis[i]=0;
}
}
}
public String getPermutation(int n, int k) {
if(n==0) return "";
dfs(0,n,k);
return sb.toString();
}
}
2.回溯+减枝
class Solution {
int[] fanit;//计算阶乘数组,根据阶乘数组进行剪枝
int[] vis;
StringBuffer sb = new StringBuffer();
void cal_fanit(int[] fanit,int n){
fanit[0] = 1;
for(int i = 1; i <= n; i++){
fanit[i] = fanit[i-1]*i;
}
}
void dfs(int level,int n,int k){
if(level == n) return;
int cnt = fanit[n-1-level];
for(int i = 1; i <= n; i++){
if(vis[i] == 1) continue;
//利用阶乘数组进行剪枝,寻找目标全排列的具体位置,所以不需要回溯
if(cnt < k){
k -= cnt;
continue;
}
vis[i] = 1;
sb.append(i);
dfs(level+1,n,k);
}
}
public String getPermutation(int n, int k) {
if(n==0) return "";
fanit = new int[n+1];
vis = new int[n+1];
cal_fanit(fanit,n);
dfs(0,n,k);
return sb.toString();
}
}