剑指offer之java篇之全排列(三)

题：全排列比如 abc 全排列为 abc acd bac bca cab cba 总共3！ n个字母则有n!种。

分析解法一：可以用字典序来完成全排列。一次排列过程为：

1) 按照以上所述需要以从小到大顺序输出，因为用的基本数据类型，很多函数要自己写，则需要先将abc排列一下就是sort一下。

2) 从后往前找到相邻中倒置的数。比如12543 其中相邻中倒置的是25。

3) 就着上述例子来，以2为i-1,从最后往找到i，直到找出一个比i-1里大的数。 12543中最后一个3就比2大此时停止查找。

4) swap i-1里的数，跟3)找出来的结果。 12543变成 13542

5) reverse i到最后13542变成13245。注意String里面是没有reverse方法的，stringbulider里面有reverse方法，为了用reverse方法把String转为StringBulider不划算，毕竟题目给的是ArrayList<String>类型。

6) 终止这次permutation_once函数，把结果作为下一次输出。

分析解法二：代码中执行语句里第二行对应一个for循环，第三行对应递归调用结果，第三行对应回溯之后第二行从左到右执行。

剑指offer之java篇之全排列(三)

代码：

解法一：上述算法描述的Permutation_Once函数:

public static void Permutation_Once(boolean flag,int length,char[] c, ArrayList<String> res){
int i;
for (i = length - 1; i > 0; i--) { //Once_Permutation
if (c[i] > c[i - 1]) {
//Permutation_Once();
for (int j = length - 1; j > i-1; j--) {
if (c[j] > c[i - 1]) {
flag=true;
swap(c,j, i - 1);
reverse(c,i);
res.add(String.valueOf(c));
break;
}
}
}
if(flag)
break;
}
}

总的代码描述:

public static ArrayList<String> Permutation(String str) {
ArrayList<String> res=new ArrayList<>();
if(str.length()==0)
return res;
char[] c = str.toCharArray();
Arrays.sort(c);
res.add(String.valueOf(c)); //valueOf是static方法返回String
int length=c.length;
int n=Hierarchy(length);
for(int k=n;k>0;k--) { //总共次数 n!
boolean flag=false;
Permutation_Once( flag,length,c,res);
}
return res;
}
public static void Permutation_Once(boolean flag,int length,char[] c, ArrayList<String> res){ //与c++不同形参传什么引用啊，传值调用传的只是副本啊，java这方面区别大
int i;
for (i = length - 1; i > 0; i--) { //Once_Permutation
if (c[i] > c[i - 1]) {
//Permutation_Once();
for (int j = length - 1; j > i-1; j--) {
if (c[j] > c[i - 1]) {
flag=true;
swap(c,j, i - 1);
reverse(c,i);
res.add(String.valueOf(c));
break;
}
}
}
if(flag)
break;
}
}
public static int Hierarchy(int length){
if(length==0||length==1)
return 1;
return length*Hierarchy(length-1);
}
public static void reverse(char[] seq, int start) {
int len;
if(seq == null || (len = seq.length) <= start)
return;
for (int i = 0; i < ((len - start) >> 1); i++) {
int p = start + i, q = len - 1 - i;
if (p != q)
swap(seq, p, q);
}
}

public static void swap(char[] cs, int i, int j) {
char temp = cs[i];
cs[i] = cs[j];
cs[j] = temp;
}

解法二：递归

public class Solution {
public ArrayList<String> Permutation(String str) {
ArrayList<String> res = new ArrayList<String>();
if (str != null && str.length() > 0) {
Permutation_Recursion(res,0,str.toCharArray());
Collections.sort(res);
}
return res;
}
public void Permutation_Recursion(ArrayList<String> alist,int i,char[] c){
if(i==c.length-1){ //退出条件
String val = String.valueOf(c);
if (!alist.contains(val))
alist.add(val);
}
//执行语句
int j;
for(j=i;j<c.length;j++){
swap(c,i,j);
Permutation_Recursion(alist,i+1,c);
swap(c,i,j); //回溯
}
}
public static void swap(char[] cs, int i, int j) {
char temp = cs[i];
cs[i] = cs[j];
cs[j] = temp;
}

剑指offer之java篇之全排列(三)

相关推荐