黑马程序员技术交流社区

标题: 这道题想了好久没做出来 [打印本页]
作者: 丑小子799    时间: 2014-11-22 07:45
标题: 这道题想了好久没做出来
第5题：原始字符串是"abc"，打印得到下列所有组合情况：
"a" "b" "c"
"ab" "bc" "ca" "ba" "cb" "ac"
"abc" "acb" "bac" "bca" "cab" "cba"
作者: cczheng    时间: 2014-11-22 10:07
这题我去某公司笔试遇到过

static char[] chars="abc".toCharArray();
    public static void main(String[] args) {
        for(int i=0;i<chars.length;i++){
            //取得每一个字符
            List<Integer> list=new ArrayList<Integer>();
            list.add(i);
            play(list);
        }
    }
    //使用递归，每次加上列表中不存在的一个字符
    private static void play(List<Integer> list){
        print(list);
        for(int i=0;i<chars.length;i++){
            if(!list.contains(i)){
                List<Integer> temp=new ArrayList<Integer>(list);
                temp.add(i);
                play(temp);
            }
        }
    }
    //打印列表内容
    private static void print(List<Integer> list){
        for(Integer i:list)
            System.out.print(chars[i]+"");
        System.out.println();
    }
作者: LOVE你的ME    时间: 2014-11-22 10:13
一样啊 当时我这道题没做就交了，我得仔细看看楼上的
作者: 苑桥别馆    时间: 2014-11-22 10:17
一楼写的不错  研究一下
作者: SpiderManZZH    时间: 2014-11-22 10:26
还没到list，回去接着奋斗
作者: kerner    时间: 2014-11-22 17:21
以前学习C语言做过穷举的题目，比如
abc
a,b,c,
ab,bc,ac,ba,cb,ca,aa,bb,cc,
和这个题目有不同的地方，这个题目没有重复字母。我这个字符串太长，效率就会很低。。。

  1. package myfirsttest;

  3. public class ExhaustionClass {

  5.         private int Num ;
  6.         int count=0;
  7.         public ExhaustionClass(int num) {
  8.                 super();
  9.                 Num = num;
  10.         }

  12.         public static void main(String[] args) {

  14.                 ExhaustionClass test = new ExhaustionClass(3);
  15.                
  16.             long startTime = System.currentTimeMillis();
  17.             
  18.             test.Method();
  19.             
  20.         long endTime = System.currentTimeMillis();
  21.         
  22.         System.out.println("一共有:"+test.count+"个组合");
  23.         System.out.println("运行时间：" + (endTime - startTime) + "毫秒");
  24.                
  25.         }

  27.         public void Method() {
  28.                 for (int i = 0; i < Num;)
  29.                         CreateString("", ++i); //穷举所有的
  30.         }

  32.         private void CreateString(String s, int end) {
  33.                 if (s.length() < end)                                 // 字母长度是否达到要求
  34.                         for (char c = 'a'; c < 'a'+ Num; c++) {
  35.                                
  36.                                 CreateString(s + c, end);         // 递归调用下一位原始字符串增加一个字母
  37.                         }
  38.                 else
  39.                         FilterPrint(s);                                //去掉重复字符后的字符串，如果字符串太长了，效率就不是很高

  41. //                        System.out.println(s);                 //没有去掉重复字母所有的穷举组合。

  43. //                        if(!s.matches("regex")){        //可用正则去掉重复字符，效率应该会高一点，目前还不会写。
  44. //                                System.out.println(s);
  45. //                        }

  47.         }

  49.         private  void FilterPrint(String s) {
  50.                
  51.                 boolean[] flags = new boolean[26];
  52.                
  53.                 char[] buf = s.toCharArray();
  54.                 for (char x : buf) {
  55.                         boolean flag = flags[x - 'a'];
  56.                         if (!flag)
  57.                                 flags[x - 'a'] = !flag;
  58.                         else
  59.                                 return;
  60.                 }
  61.                 count++;
  62.                 System.out.println(s);
  63.                
  64.         }

  66. }
复制代码


作者: 地瓜君    时间: 2014-11-22 22:04
mark 学了list在研究
作者: taany    时间: 2014-11-22 22:11
感觉我还差好远！
作者: qq8921310    时间: 2014-11-22 22:24
cczheng 发表于 2014-11-22 10:07
这题我去某公司笔试遇到过

static char[] chars="abc".toCharArray();

应该是list.contain（chars【i】）把
作者: xingkong123    时间: 2014-11-22 23:22
感觉我还差的太远，好好努力。。。



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2