A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 老二 中级黑马   /  2014-6-20 21:04  /  3547 人查看  /  14 人回复  /   1 人收藏 转载请遵从CC协议 禁止商业使用本文

原始字符串是"abc",打印得到下列所有组合情况:
                "a" "b" "c"
                "ab" "bc" "ca" "ba" "cb" "ac"
                "abc" "acb" "bac" "bca" "cab" "cba"
代码:
public static String str="abc";
         public static void show(int current_recur, String temp) {
                if (current_recur < str.length()) {
                    for (int i = 0; i < str.length(); i++) {
                        if (!(temp.contains(str.substring(i, i + 1)))) {
                            System.out.print(temp + str.substring(i, i + 1) + "    ");
                            show(current_recur + 1,
                                    new String(temp + str.substring(i, i + 1)));
                        }
                    }
                }
         }

14 个回复

倒序浏览
如果把字符串转换成字符数组,应该还有好的解法,更清晰。
回复 使用道具 举报
求大神,给思路
回复 使用道具 举报
看得很累!
回复 使用道具 举报

是啊,一些嵌套,几层for循环
回复 使用道具 举报
这个我觉得很难,我想了十个小时,尽然还没弄出来。发现用递归来组合,只要超过8个几乎要算很久。
回复 使用道具 举报
Aron 中级黑马 2014-6-21 00:02:58
7#
给你一个我的方法有注释 看你理解不 不懂得就问我
  1. //初始化一个字符串
  2.         private static String s="abcd";
  3.         //把这个字符串中每个字母放入一个数组中
  4.         public static void intoArr(String s,String[] array){
  5.                 for(int i=0;i<s.length();i++){
  6.                         array[i]=String.valueOf(s.charAt(i));
  7.                 }
  8.         }
  9.         private static String[] array =new String[s.length()]; //初始化一个数组
  10.         private static ArrayList<String> pp = new ArrayList<String>(); //定义一个集合用来放最后组合的字符数组
  11.         public static void main(String[] args)
  12.         {
  13.                 intoArr(s,array); //给array赋值
  14.                 execute(); //执行
  15.         }
  16.         //输出和递归调用
  17.         public static void execute()
  18.         {
  19.                 ArrayList<String> list = new ArrayList<String>();
  20.                 //创建包含字符串数组内容的list集合
  21.                 list.addAll(Arrays.asList(array));
  22.                 for (int len = 1; len <= array.length; len++)
  23.                 {       
  24.                         for(String a:pp){
  25.                                 System.out.print(a+" ");
  26.                         }
  27.                         if(len!=1){//第一次不换行
  28.                                 System.out.println();
  29.                         }
  30.                         pp.clear();
  31.                         digui(list, "", len);
  32.                 }
  33.                 for(String a:pp){
  34.                         System.out.print(a+" ");
  35.                 }
  36.         }
  37.         //递归得到组合
  38.         public static void digui(ArrayList<String> list, String result, int len)
  39.         {
  40.                 for (int i = 0; i < list.size(); i++)
  41.                 {
  42.                         String str = list.get(i);
  43.                         result += str;
  44.                         if (result.length() == len)
  45.                                 {
  46.                                         pp.add(result); //把组合放入pp中
  47.                                 }
  48.                         else
  49.                                 {
  50.                                         ArrayList<String> copylist = (ArrayList<String>) list.clone();//克隆一个一样的字符串数组
  51.                                         copylist.remove(str);//把这个复制的字符串数组中的str元素去掉
  52.                                         digui(copylist, result, len);//再次调用递归
  53.                                 }
  54.                         result = result.substring(0, result.length() - 1);//截取掉相对应的字符
  55.                 }
  56.         }
复制代码

这个方法只适合字符串少 如果太大 java会运行不了 所以如果想实现快速的方法 可能要换一种思想
回复 使用道具 举报
这么短?我写的是无限长度不重复字符串的全组合
回复 使用道具 举报
本帖最后由 黎志勇 于 2014-6-21 07:06 编辑

睡前看到这题,睡觉时一直在想,老感觉不舒坦,就起床熬夜写出来了,不写完总睡不着,终于可以安心去睡觉了。
  1. /*思路:
  2. *1.题中所有组合,其实就是带顺序的“3选1”、“3选2”、“3选3”的所有组合;
  3. *2.可以想象abc为三个球,有两个管子,一个用来存已选择的,一个用来存未选择的;
  4. *3.所以可以定义两个字符数组,一个是已被选择的数组selected,一个是待选择的数组toSelect,只要操作这两个数组就OK了;
  5. *4.一开始没选择,已选择数组长度为0,待选择数组长度为3;
  6. *5.选一个字符放进已选择数组,这时已选择数组长度为1,待选择数组长度为2;
  7. *6.每选择一次,打印已选择数组的序列;
  8. *7.重复5、6步,直到未选择数组长度为0;
  9. *
  10. */

  11. public class Demo {
  12.         
  13.         public static void main(String[] args) {
  14.                 show("abc");
  15.         }
  16.         
  17.         //把“选择”操作封装,使满足打印任意非重复字符串组合
  18.         public static void show(String str){
  19.                 selectChar(new char[0],str.toCharArray());
  20.         }
  21.         
  22.         //这个方法是对“选择”这个动作的抽象,对俩数组进行操作
  23.         private static void selectChar(char[] selected,char[] toSelect){
  24.                 if(toSelect.length==0){//如果待选择数组长度为0,则退出选择操作
  25.                         return;
  26.                 }
  27.                 //定义一个新的临时数组,作为新的“已选择数组”,注意新的数组比旧的长度增加1
  28.                 char[] tempSelected = updateSelectedCharArray(selected);//
  29.                 char[] tempToSelect;//新的待选择数组
  30.                 for(int i=0;i<toSelect.length;i++){
  31.                         tempSelected[tempSelected.length-1]=toSelect[i];//把选择的字符放进新“已选择数组”最后 一位
  32.                         tempToSelect=updateToSelecteCharArray(toSelect, i);//更新“待选择数组”
  33.                         System.out.println(String.valueOf(tempSelected));//打印“已选择数组”
  34.                         selectChar(tempSelected, tempToSelect);//重复选择操作
  35.                 }
  36.                
  37.         }
  38.         
  39.         //这个方法用来更新选择一个字符时,“已选择数组”的内容
  40.         private static char[] updateSelectedCharArray(char[] array){
  41.                 char[] temp = new char[array.length+1];
  42.                 for(int i =0;i<array.length;i++){
  43.                         temp[i]=array[i];
  44.                 }
  45.                 return temp;
  46.         }
  47.         //这个方法用来更新选择一个字符后,“待选择数组”的内容
  48.         private static char[] updateToSelecteCharArray(char[] array,int index){
  49.                 char[] temp = new char[array.length-1];
  50.                 for(int i =0,j=0;i<array.length;i++){
  51.                         if(i!=index){
  52.                                 temp[j++]=array[i];
  53.                         }
  54.                 }
  55.                 return temp;
  56.         }
  57.         
  58. }
复制代码



回复 使用道具 举报
黎志勇 发表于 2014-6-21 06:59
睡前看到这题,睡觉时一直在想,老感觉不舒坦,就起床熬夜写出来了,不写完总睡不着,终于可以安心去睡觉了 ...

嗯嗯,向你学习
回复 使用道具 举报
老二 发表于 2014-6-21 11:53
嗯嗯,向你学习

不过没有这个的输出顺序不像题目标的那样,先输出一个的,再输出两个的,最后三个的,不知道有没有要求输出顺序一定要字符个数要从小到大了。
回复 使用道具 举报
下面的是我的思路,代码和楼主一样

  1. /*
  2. * 思路:
  3. * 题目相当于要求一个字符串的所有子集(元素位置不相同视为不同子集),
  4. * 此时想到了字符串的substring方法,首先要对怎么取子集进行思考。
  5. * 可以先固定其中一个字符,此字符必然是其中一种组合,
  6. * 然后取原字符串的任意一个字符,如果这两个字符不相同,那么这两个字符形成一个字符,也必然是原字符串的子集
  7. * 然后固定这两个字符形成的字符串,再取原字符串的任意一个字符,如果与这两个字符仍然不同,
  8. * 那么固定这两个字符再加上此字符仍然是所求的,继续固定这三个字符,之后继续循环,
  9. * 如果字符长度等于题目所给字符串长度则停止,返回上一层循环。
  10. * 步骤:
  11. * 通过思路可以看出,该程序需要用到循环和递归的方法。
  12. *
  13. */
  14. public class Text7 {
  15.         public static String str = "abc";//定义一个静态的,可供调用的需要打印子集的原始字符串
  16.        
  17.         public static void show(int length,String fixedStr){   //定义接收两个变量的功能函数
  18.                  //固定的字符串的长度需要小于原始字符串的长度,如果大于,则此循环或者递归中的循环结束,初始固定的字符串视为空
  19.                 if(length<str.length()){  
  20.                         for(int x = 0;x < str.length();x++){   //x为原字符串一个子集的起始角标位
  21.                                 if(!fixedStr.contains(str.substring(x, x+1))){//如果固定的字符串不含有原字符串的其中一个单元素子集的元素
  22.                                         System.out.println(fixedStr+str.substring(x,x+1));//把固定的字符串加上原字符串的第x个元素合在一起打印
  23.                                         show(length+1,new String(fixedStr+str.substring(x,x+1)));//再把打印的这个元素和它的长度作为变量进行递归操作
  24.                                 }
  25.                         }
  26.                 }
  27.                
  28.         }
  29.         public static void main(String[] args){
  30.                 show(0,new String());//可以视为传入一个空字符串,字符串为0长度的参数调用函数打印原始字符串的全字符组合。
  31.         }
  32.        
  33. }
复制代码
回复 使用道具 举报
crazystraw 发表于 2014-6-21 13:22
下面的是我的思路,代码和楼主一样

你的注释多,不错
回复 使用道具 举报
今天写的可以参考下
  1. import java.util.HashMap;
  2. import java.util.Iterator;
  3. import java.util.Map;
  4. import java.util.Set;
  5. import java.util.TreeSet;
  6. class ForTest3 {
  7.         public static void main(String[] args) {
  8.                 StringBuffer str = new StringBuffer("abc");
  9.                 Set<String> set = new TreeSet<String>();
  10.                 char[] ch = str.toString().toCharArray();
  11.                 print(ch, new StringBuffer(), set, 0);

  12.                 System.out.println();
  13.                 System.out.println("----------------");

  14.                 Set<String> set2 =quChongFu(set);
  15.                 Iterator<String> it2 = set2.iterator();
  16.                 while (it2.hasNext()) {
  17.                         System.out.print(it2.next() + ",");
  18.                 }
  19.         }
  20.         //去掉集合中重复的元素
  21.         /*
  22.          * set:需要除去重复字符元素的集合
  23.          */
  24.         public static Set<String> quChongFu(Set<String> set) {
  25.                 Set<String> set2 = new TreeSet<String>();
  26.                 Map<Character, Integer> map = null;
  27.                 Iterator<String> it2 = set.iterator();
  28.                 int count;
  29.                 while (it2.hasNext()) {
  30.                         map = new HashMap<Character, Integer>();
  31.                         count = 1;
  32.                         boolean flag = false;
  33.                         String str = it2.next();
  34.                         char[] ch = str.toCharArray();
  35.                         for (int i = 0; i < ch.length; i++) {
  36.                                 if (!map.containsKey(ch[i])) {
  37.                                         count = 1;
  38.                                         map.put(ch[i], count);
  39.                                 }
  40.                                 if (map.containsKey(ch[i])) {
  41.                                         map.put(ch[i], count);
  42.                                         count++;
  43.                                 }
  44.                        
  45.                         }
  46.                 //        System.out.println(map);
  47.                         for(int j=0;j<ch.length;j++){
  48.                                 if(map.get(ch[j])>1){
  49.                                         flag=false;
  50.                                         //System.out.println("r");
  51.                                         break;
  52.                                 }else
  53.                                        
  54.                                 flag=true;
  55.                         }
  56.                         if(flag){
  57.                         //        System.out.println("s");
  58.                                 set2.add(str);
  59.                                
  60.                         }
  61.                 }
  62.                 //System.out.println(set2);
  63.                 return set2;
  64.         }
  65.        
  66.         //利用递归打印所有组合
  67.         /*
  68.          * ch:需要打印在组合的字符数组
  69.          * str:子字符串缓存,每个组合临时保存的变量
  70.          * set:最后存入的集合
  71.          * cout:递归的层数,和ch参数的(长度)相等
  72.          */
  73.         public static void print(char[] ch, StringBuffer str, Set<String> set,
  74.                         int count) {
  75.                 //递归一层自加一次
  76.                 count++;
  77.                 //当递归层数大于字符数组长度时退出
  78.                 if (count > ch.length) {
  79.                         return;
  80.                 }
  81.                 for (int i = 0; i < ch.length; i++) {
  82.                         //当前字符添加到缓存变量中
  83.                         str.append(ch[i]);
  84.                         //打印所有组合,包括重复的
  85.                         System.out.print(str.toString() + ",");
  86.                         //将缓存变量中的数据转换成字符串存入集合中
  87.                         set.add(str.toString());
  88.                         //进入下一层,也就是字符数组的下一个字符
  89.                         print(ch, str, set, count);
  90.                         //删除上次保存的最后一个字符,避免了字符重复
  91.                         str.deleteCharAt(str.length() - 1);
  92.                 }

  93.         }
  94. }
复制代码
回复 使用道具 举报
好高深的赶脚。。
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马