首页 > 其他 > 详细

递归递归!!!

时间:2019-06-19 23:41:11      阅读:58      评论:0      收藏:0      [点我收藏+]

标签:解决方案   ret   amp   solution   array   一个数   col   输出   void   

字符串的全排列

此处采用的方式将字符串分为两部分

    1. 固定一个字符,将之后的字符串全排列

    2. 将固定字符与之后的字符依次交换

盗图如下,产生的字符串顺序为最后一行从左到右~

技术分享图片

 

代码中有两种包含重复字符的解决方案

    1. 在将重排后的字符串输出时,判断是否重复过,若重复过,则不做处理

    2. 将字符与之后的字符交换时,对于重复的字符仅交换一次,这样避免了重复字符串的出现

首先是递归算法

方案1:

 1 import java.util.*;
 2 
 3 public class Solution_permutation {
 4     public static void main(String[] args) {
 5         String a = "abb";
 6         Solution_permutation x = new Solution_permutation();
 7         System.out.println(x.Permutation(a));
 8     }
 9     @SuppressWarnings("null")
10     public ArrayList<String> Permutation(String str) {
11        ArrayList<String> ans=new ArrayList<String>();//所有排列的可能都在这里
12         if(str!=null||str.length()>0){
13             help(0,str.toCharArray(),ans);
14             Collections.sort(ans);
15         }        
16         return ans;
17     }
18     public static void help(int i,char[] cha,ArrayList<String> ans){
19         if(i==cha.length-1){
20             String val = String.valueOf(cha);
21             if(!ans.contains(val)){
22                 ans.add(val);//避免重复
23             }
24         }else{
25             for(int j=i;j<cha.length;j++){
26                 swap(i,j,cha);//依次选一个数固定住
27                 help(i+1,cha,ans);//让后面的进行全排列
28                 swap(i,j,cha);//恢复原来的模样,回溯关键
29             }
30         }        
31     }
32     public static void swap(int i,int j,char[] cha){
33         char temp=cha[i];
34         cha[i]=cha[j];
35         cha[j]=temp;
36     }    
37 }

方案2

 1 import java.util.*;
 2 
 3 public class Solution_permutation {
 4     public static void main(String[] args) {
 5         String a = "abb";
 6         Solution_permutation x = new Solution_permutation();
 7         System.out.println(x.Permutation(a));
 8     }
 9     public ArrayList<String> Permutation(String str) {
10         ArrayList<String> list=new ArrayList<String>();
11         if(str!=null&&str.length()>0){
12             PermutationHelper(str.toCharArray(),0,list);
13             Collections.sort(list);
14         }
15         return list;
16     }
17     private void PermutationHelper(char[] chars,int i,ArrayList<String> list){
18         if(i == chars.length-1){
19             list.add(String.valueOf(chars));
20         }else{
21             Set<Character> charSet = new HashSet<Character>();
22             for(int j=i;j<chars.length;++j){
23                 if(j==i||!charSet.contains(chars[j])){//避免重复,即当将字符串进行交换时,若交换的字符之前交换过一次,则该次不再交换。
24                     charSet.add(chars[j]);
25                     swap(chars,i,j);
26                     PermutationHelper(chars,i+1,list);
27                     swap(chars,j,i);
28                 }
29             }
30         }
31     }
32     private void swap(char[] cs,int i,int j){
33         char temp = cs[i];
34         cs[i] = cs[j];
35         cs[j] = temp;
36     }
37 }

还是感觉有点混沌。之后需要再看递归递归~~~

递归递归!!!

标签:解决方案   ret   amp   solution   array   一个数   col   输出   void   

原文:https://www.cnblogs.com/10081-AA/p/11055215.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号