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

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© yanzhendong 高级黑马   /  2016-5-13 22:47  /  1734 人查看  /  23 人回复  /   2 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 yanzhendong 于 2016-5-16 08:46 编辑

题目如下:用 "H", "E", "L", "L", "O", "H", "E", "I", "M", "A", "!" 这十一个字符,用java写一个函数,打印出所有不同的排列,如:HELLOHEIMA! ,HEIMAHELLO!等,要求:L后面跟A,H后面跟I,E和M相隔两个字符,O和!不相邻,不能有连续两个相同的字符(如LL或HH),O在I前面(不是I前面跟O而是O的位置在I前面,可以相邻可以不相邻)

代码如下:(昨晚又优化了一下,用多线程去跑,运行时间降低到了36秒)
  1.         /**
  2.          * 这个接口用于定义规则的,用户可以在这个接口的实现类中自定义规则,如果一个item符合这个规则返回真,否则返回假
  3.          */
  4.         interface ItemFilter {
  5.                 boolean accept(String item);// 用于检测符合的情况

  6.                 boolean exclude(String item);// 用于检测不符合的情况,以避免无谓的遍历
  7.         }

  8.         // 用多线程去跑,可以大大减少运行时间
  9.         private static final int MAX_DEEP = 6;// 最大遍历深度,这个值要适当,太小了反而会影响性能,测试是6最省时间
  10.         private static ThreadPoolExecutor threadPool = new ThreadPoolExecutor(10, 20, 5, TimeUnit.SECONDS,
  11.                         new LinkedBlockingQueue<>());// 参数5为线程死亡等待时间,这个值要设置恰当,多线程在小任务量时优势不明显,任务量越大月明显

  12.         public static void main(String[] args) throws Exception {
  13.                 String[] values = { "H", "E", "L", "L", "O", "H", "E", "I", "M", "A", "!" };

  14.                 SortedSet<String> result = Collections.synchronizedSortedSet(new TreeSet<>());
  15.                 threadPool.allowCoreThreadTimeOut(true);
  16.                 BufferedWriter out = new BufferedWriter(new FileWriter(new File("D:\\LongResult.txt")));
  17.                 // 这里我自定义的规则是:L后面跟A,H后面跟I,E和M相隔两个字符,O和!不相邻,不能有连续两个相同的字符(如LL
  18.                 // 或HH),O在I前面(不是I前面跟O而是O的位置在I前面,可以相邻可以不相邻)
  19.                 ItemFilter filter = new ItemFilter() {
  20.                         private Pattern pattern1 = Pattern.compile("(E.{2}M)|(M.{2}E)");// 匹配E和M相隔两个字符
  21.                         private Pattern pattern2 = Pattern.compile("(.)\\1");// 匹配不能有连续两个相同的字符(如LL或HH)
  22.                         private Pattern pattern3 = Pattern.compile("O.*I");// 匹配O在I前面(不是I前面跟O而是O的位置在I前面,可以相邻可以不相邻)
  23.                         private Pattern pattern4 = Pattern.compile("O!|!O");// 匹配O和!不相邻
  24.                         private Pattern pattern5 = Pattern.compile("LA");// 匹配L后面跟A
  25.                         private Pattern pattern6 = Pattern.compile("HI");// 匹配H后面跟I

  26.                         @Override
  27.                         public boolean accept(String item) {
  28.                                 boolean rule1 = pattern1.matcher(item).find();
  29.                                 boolean rule3 = pattern3.matcher(item).find();
  30.                                 boolean rule5 = pattern5.matcher(item).find();
  31.                                 boolean rule6 = pattern6.matcher(item).find();
  32.                                 return rule1 && rule3 && rule5 && rule6;
  33.                         }

  34.                         @Override
  35.                         public boolean exclude(String item) {
  36.                                 // 这里面的pattern任意一个匹配成功则以此head开始的组合都是不符合规则的,所以没必要继续递归下去了
  37.                                 boolean rule2 = pattern2.matcher(item).find();// 这个匹配成功表示有连续两个相同的字符
  38.                                 boolean rule4 = pattern4.matcher(item).find();// 这个匹配成功表示O和!相邻
  39.                                 return rule2 || rule4;
  40.                         }
  41.                 };
  42.                
  43.                 long start = System.currentTimeMillis();
  44.                 listAvailableItems(values, "", result, filter);

  45.                 while (true) {
  46.                         Thread.sleep(100);
  47.                         if (threadPool.getPoolSize() == 0) {
  48.                                 out.write("共有" + result.size() + "组\r\n");
  49.                                 for (String item : result) {
  50.                                         out.write(item + "\r\n");
  51.                                 }
  52.                                 out.flush();
  53.                                 out.close();
  54.                                 long end = System.currentTimeMillis();
  55.                                 System.out.println("共耗时:" + (end - start) / 1000 + "秒");
  56.                                 break;
  57.                         }
  58.                 }

  59.         }

  60.         public static void listAvailableItems(final String[] values, final String head, SortedSet<String> result,
  61.                         ItemFilter filter) {
  62.                 for (int i = 0; i < values.length; i++) {
  63.                         String[] localV = Arrays.copyOf(values, values.length);
  64.                         String localH = new String(head);
  65.                         if (localV[i] == null) {// 这里过滤掉null元素,
  66.                                 continue;
  67.                         }

  68.                         localH += localV[i];// 到这里说明找到一个可用元素,则把该元素追加到已排列组合的尾部
  69.                         localV[i] = null;// 将已取走的元素从values中去除

  70.                         if (filter.exclude(localH)) {// 这个匹配成功说明此head是不符合规则的,所以没必要以此head继续递归了
  71.                                 continue;
  72.                         }

  73.                         if (localH.length() == values.length) {// 这是递归结束的条件,即一个组合已排列出来,未必是符合规则的组合
  74.                                 if (filter.accept(localH)) {// 这里判断这个组合是否符合规则
  75.                                         result.add(localH);
  76.                                 }
  77.                                 return;
  78.                         }

  79.                         if (localH.length() % MAX_DEEP == 0) {
  80.                                 threadPool.execute(new ST(localV, localH, result, filter));
  81.                                 continue;
  82.                         }
  83.                         listAvailableItems(localV, localH, result, filter);
  84.                 }
  85.         }

  86.         static class ST implements Runnable {
  87.                 private String[] values;
  88.                 private String head;
  89.                 private SortedSet<String> result;
  90.                 private ItemFilter filter;

  91.                 public ST(final String[] values, final String head, SortedSet<String> result, ItemFilter filter) {
  92.                         this.values = values;
  93.                         this.head = head;
  94.                         this.result = result;
  95.                         this.filter = filter;
  96.                 }

  97.                 @Override
  98.                 public void run() {
  99.                         listAvailableItems(values, head, result, filter);
  100.                 }
  101.         }
复制代码









23 个回复

倒序浏览
明天会把我写好的函数贴上来
回复 使用道具 举报
完全没有头绪  哭瞎。。。看来还有很长的路要走。。。。
回复 使用道具 举报
看一看。。。。。。
回复 使用道具 举报
inzaghi9247 来自手机 初级黑马 2016-5-13 23:27:44
报纸
卧槽,这尼玛真的是人写出来的来自: iPhone客户端
回复 使用道具 举报
把要求再改变态一点:L后面跟A,H后面跟I,E和M相隔两个字符,O和!不相邻,不能有连续两个相同的字符(如LL 或HH),O在I前面(不是I前面跟O而是O的位置在I前面,可以相邻可以不相邻),有人会吗?可以通过正则表达式来解决
回复 使用道具 举报
下不了手
回复 使用道具 举报
yaolv7 中级黑马 2016-5-14 20:36:26
8#
我就想问下
前面说   如:HELLOHEIMA! ,HEIMAHELLO!等
后面又说  不能有连续两个相同的字符?
这是几个意思??

先把所有的排出来,再用正则去掉或保留,这么蛋疼的题肯定是你闲得蛋疼乱来的吧??

回复 使用道具 举报
先mark,等我写好弄上来
回复 使用道具 举报
学习学习
回复 使用道具 举报
太烧脑,不敢想
回复 使用道具 举报
看一下~~~~
回复 使用道具 举报
看一下结果咯~
回复 使用道具 举报
正则表达式还没学,用个笨办法:

/*
* 题目如下:用 "H", "E", "L", "L", "O", "H", "E", "I", "M", "A", "!"
* 这十一个字符,用java写一个函数,打印出所有不同的排列,如:HELLOHEIMA! ,HEIMAHELLO!等,
* 要求:L后面跟A,H后面跟I,E和M相隔两个字符,O和!不相邻,不能有连续两个相同的字符
* (如LL或HH),O在I前面(不是I前面跟O而是O的位置在I前面,可以相邻可以不相邻)
* */
public class Text3 {       
        public static void main(String[] args) {
                //把这些字母定义成一个数组,用满足条件的索引来打印
                String[] arr = {"H","E","L","L","O","H","E","I","M","A","!"};

                //用16进制数获取所有由1~b组成的数,如123456789ab,因为LL不相邻
                //所以从123546789ab开始,
                mark:for (long x = 0x123546789abL; x <= 0xba987654321L; x++) {
                        for (long y = x;y%0x10 != 0;y /= 0x10 ) {
                                if (y%0x10 == 0xc || y%0x10 == 0xd || y%0x10 == 0xe || y%0x10 == 0xf ) {
                                        continue mark;
                                }
                        }
                        int i = 0;
                        for (long m = x; m % 0x10 != 0; m /= 0x10) {
                                for (long n = m / 0x10; m % 0x10 != n % 0x10 && n % 0x10 != 0; n /= 0x10) {
                                        i++;
                                        if (i == 55) {
                                                //根据得到的11位数,把每一个11位数分解成一个数组
                                                //如{1,2,3,4,5,6,7,8,9,a,b};这些元素满足后面的条件
                                                //后,自身减一则可以作为字符串组arr的索引;
                                                int[] sinple = new int[11];       
                                                sinple[10] = (int) (x%0x10);
                                                sinple[9] = (int) (x/0x10%0x10);
                                                sinple[8] = (int) (x/0x10/0x10%0x10);
                                                sinple[7] = (int) (x/0x10/0x10/0x10%0x10);
                                                sinple[6] = (int) (x/0x10/0x10/0x10/0x10%0x10);
                                                sinple[5] = (int) (x/0x10/0x10/0x10/0x10/0x10%0x10);
                                                sinple[4] = (int) (x/0x10/0x10/0x10/0x10/0x10/0x10%0x10);
                                                sinple[3] = (int) (x/0x10/0x10/0x10/0x10/0x10/0x10/0x10%0x10);
                                                sinple[2] = (int) (x/0x10/0x10/0x10/0x10/0x10/0x10/0x10/0x10%0x10);
                                                sinple[1] = (int) (x/0x10/0x10/0x10/0x10/0x10/0x10/0x10/0x10/0x10%0x10);
                                                sinple[0] = (int) (x/0x10/0x10/0x10/0x10/0x10/0x10/0x10/0x10/0x10/0x10%0x10);
                                               
                                                //O和!不相邻,即5和11不相邻
                                                for (int index1 = 0 ; index1<0xb ; index1++) {
                                                        if (sinple[index1] == 5) {
                                                                if (index1 == 0) {
                                                                        if (sinple[1] == 0xb) {
                                                                                continue mark;
                                                                        }
                                                                }else if (index1 == 0xa) {
                                                                        if (sinple[9] == 0xb) {
                                                                                continue mark;
                                                                        }
                                                                }else {
                                                                        if (sinple[index1+1] == 0xb ||sinple[index1-1] == 0xb) {
                                                                                continue mark;
                                                                        }
                                                                }
                                                        }
                                                }
                                               
                                                //不能有连续两个相同的字符,如HH,即1和6不相邻
                                                for (int index1 = 0 ; index1<0xb ; index1++) {
                                                        if (sinple[index1] == 1) {
                                                                if (index1 == 0) {
                                                                        if (sinple[1] == 6) {
                                                                                continue mark;
                                                                        }
                                                                }else if (index1 == 0xa) {
                                                                        if (sinple[9] == 6) {
                                                                                continue mark;
                                                                        }
                                                                }else {
                                                                        if (sinple[index1+1] == 6 ||sinple[index1-1] == 6) {
                                                                                continue mark;
                                                                        }
                                                                }
                                                        }
                                                }
                                       
                                                //不能有连续两个相同的字符,如LL,即3和4不相邻
                                                for (int index1 = 0 ; index1<0xb ; index1++) {
                                                        if (sinple[index1] == 3) {
                                                                if (index1 == 0) {
                                                                        if (sinple[1] == 4) {
                                                                                continue mark;
                                                                        }
                                                                }else if (index1 == 0xa) {
                                                                        if (sinple[9] == 4) {
                                                                                continue mark;
                                                                        }
                                                                }else {
                                                                        if (sinple[index1+1] == 4 ||sinple[index1-1] == 4) {
                                                                                continue mark;
                                                                        }
                                                                }
                                                        }
                                                }
                                                                                       
                                                //不能有连续两个相同的字符,如EE,即2和7不相邻
                                                for (int index1 = 0 ; index1<0xb ; index1++) {
                                                        if (sinple[index1] == 2) {
                                                                if (index1 == 0) {
                                                                        if (sinple[1] == 7) {
                                                                                continue mark;
                                                                        }
                                                                }else if (index1 == 0xa) {
                                                                        if (sinple[9] == 7) {
                                                                                continue mark;
                                                                        }
                                                                }else {
                                                                        if (sinple[index1+1] == 7 ||sinple[index1-1] == 7) {
                                                                                continue mark;
                                                                        }
                                                                }
                                                        }
                                                }
                                               
                                                //E和M相隔两个字符,即2和7与9都相隔两个字符,即E--M--E
                                                for (int index1 = 0 ; index1<0xb ; index1++) {
                                                        if (sinple[index1] == 9) {
                                                                if ((index1+3) > 0xa) {
                                                                        continue mark;
                                                                }else if ((index1-3) < 0) {
                                                                        continue mark;
                                                                }else {
                                                                        if ((sinple[index1-3] != 2 || sinple[index1+3] != 7) && (sinple[index1-3] != 7 || sinple[index1+3] != 2)) {
                                                                                continue mark;
                                                                        }
                                                                }
                                                        }
                                                }
                                               
                                                //H后面跟I,即1或6后面是8,即18或68
                                                for (int index1 = 0 ; index1<0xb ; index1++) {
                                                        if (sinple[index1] == 8) {
                                                                if (index1 == 0) {
                                                                        continue mark;
                                                                }else {
                                                                        if (sinple[index1-1] != 1 && sinple[index1-1] != 6) {
                                                                                continue mark;
                                                                        }
                                                                }
                                                        }
                                                }
                                               
                                                //L后面跟A,即3或4后面是10,即3a或4a
                                                for (int index1 = 0 ; index1<0xb ; index1++) {
                                                        if (sinple[index1] == 0xa) {
                                                                if (index1 == 0) {
                                                                        continue mark;
                                                                }else {
                                                                        if (sinple[index1-1] != 3 && sinple[index1-1] != 4) {
                                                                                continue mark;
                                                                        }
                                                                }
                                                        }
                                                }
                                               
                                                //O在I前面,即5在8前面,如8--5       
                                                for (int index1 = 0 ; index1<0xb ; index1++) {
                                                        if (sinple[index1] == 8) {
                                                                if (index1 == 0xa) {
                                                                        continue mark;
                                                                }else {
                                                                        int k = index1;
                                                                        int m1 = 0;
                                                                        while (++k <= 0xa) {
                                                                                if (sinple[index1] != 5) {
                                                                                        m1++;
                                                                                }
                                                                        }
                                                                        if (m1 == 0xa-index1) {
                                                                                continue mark;
                                                                        }
                                                                }
                                                        }
                                                }
                                               
                                                //打印结果
                                                for (int k = 0;k<11;k++) {
                                                        System.out.print(arr[sinple[k]-1]);
                                                }
                                                System.out.println("");
                                               
                                        }
                                }
                        }
                }
                //程序结束
                System.out.println("over");
        }
}

我估计要把结果打印出来,可能要几天的时间。。

回复 使用道具 举报
我有上将潘凤 发表于 2016-5-15 15:17
正则表达式还没学,用个笨办法:

/*

呵呵,可以啊,但是很麻烦,很难懂
回复 使用道具 举报
yanzhendong 发表于 2016-5-15 16:35
呵呵,可以啊,但是很麻烦,很难懂

恩恩,遍历的时间太长了,输出结果等得太久。
我也问你一个问题;设计一个程序,根据输入的初始值,把数独的结果打印出来。。。
回复 使用道具 举报
yanzhendong 发表于 2016-5-15 16:35
呵呵,可以啊,但是很麻烦,很难懂

如果字符是:TODAYISSUNDAYTOMORROWISMONDAY 要求是:必须有DAY但不能超过三个
必须有连续的O但不能超过四个,IS和TO要么不出现要么同时出现,N后面不能跟D
N前面不能跟M,你这个方法还行的通吗?
回复 使用道具 举报
class Play2 {
        public static void main(String[] args) {
                int[] a = {7,4,11,11,14,7,4,8,12,-32,0};
                int[] y =new int[11];

        L:        for (int q=0 ;q<=9 ;q++ ) {
                        if (q==7) {
                                continue;
                        }
                        y[0]= a[q];
                        int[] a1= delete(a,y[0]);
                        for (int w=0;w<=9 ;w++ ) {
                                y[1]=a1[w];
                                int[] a2=delete(a1,y[1]);
                                for (int e =0;e<=8 ;e++ ) {
                                        y[2]=a2[e];
                                        int[] a3 =delete(a2,y[2]);
                                        for (int r=0;r<=7 ;r++ ) {
                                                y[3]=a3[r];
                                                int[] a4= delete(a3,y[3]);
                                                for (int t =0;t<=6 ;t++ ) {
                                                        y[4]=a4[t];
                                                        int[] a5=delete(a4,y[4]);
                                                        for (int u=0;u<=5 ;u++ ) {
                                                                y[5]=a5[u];
                                                                int[] a6 = delete(a5,y[5]);
                                                                for (int m=0;m<=4 ; m++) {
                                                                        y[6]=a6[m];
                                                                        int[] a7 =delete(a6,y[6]);
                                                                        for (int p=0;p<=3 ;p++ ) {
                                                                                y[7]= a7[p];
                                                                                int[] a8= delete(a7,y[7]);
                                                                                for (int s =0;s<=2 ;s++ ) {
                                                                                        y[8]=a8[s];
                                                                                        int[] a9=delete(a8,y[8]);
                                                                                a:        for (int c=0;c<=1 ;c++ ) {
                                                                                                y[9]=a9[c];
                                                                                                int[] a10=delete(a9,y[9]);
                                                                                                y[10]=a10[0];
                                                                                       
                                                                                       
                                                                                        for (int i =0;i<=10 ;i++ ) {           //对当前数组分析是否满足限制条件,,, 不满足则继续下一个遍历循环,
                                                                       
                                                                                if (y[i]==0&&y[i-1]!=11) {
                                                                                                continue a;
                                                                                        }
                                                                                if (y[i]==8&&y[i-1]!=7) {                                                                                       
                                                                                                continue a;                                                                                       
                                                                                }
                                                                                if (i<=2&&y[i]==12&& y[i+3]!=4) {
                                                                                        continue a;
                                                                                }
                                                                                if (i>=8&& y[i]==12&&y[i-3]!=4) {
                                                                                        continue a;
                                                                                }
                                                                                if (i>2&&i<8&&y[i]==12&&y[i-3]!=4&&y[i+3]!=4) {
                                                                                        continue a;
                                                                                }
                                                                                if (i<=9&&y[i]==y[i+1]) {
                                                                                        continue a;
                                                                                }
                                                                                if (i<=9&&((y[i]==14&&y[i+1]==-32)||(y[i]==-32&&y[i+1]==14))) {
                                                                                        continue a;
                                                                                }
                                                                               
                                                                                if (y[i]==14) {
                                                                                        for (int j =0;j<i ;j++ ) {
                                                                                                if (y[j]==8) {
                                                                                                        continue a;
                                                                                                }
                                                                                        }
                                                                                }
                                                                        }                                                                                                                                                                                                                                                               
                                                                                        char[] ch = new char[11];
                                                                        for (int v =0;v<=10 ;v++ ) {
                                                                                System.out.print(ch[v]=(char)(y[v]+65));
                                                                        }
                                                                        System.out.println();
                                                                                        }
                                                                                }
                                                                        }
                                                                }
                                                        }
                                                }
                                        }
                                }
                        }

                }
        }
public static int[] delete(int[] arr, int c){
int i =0;
for (i =0;i<arr.length ;i++ ) {
        if (arr[i]==c) {
                break;
        }
}
int[] a= new int[arr.length-1];
for (int j =0;j<arr.length-1 ;j++ ) {
        if (j<i) {
                a[j]=arr[j];
        }
                if (j>=i) {
                        a[j]=arr[j+1];
                }
}
return a;
        }
}
回复 使用道具 举报
http://bbs.itheima.com/forum.php?mod=attachment&aid=MTA5ODc4fGFhZTliOTEyZjQ3YmY5NTM0NTk2YWE1OWQ2NDQ0NDM3fDE3MzE1MjQ5NjU%3D&request=yes&_f=.png

%_F38S1PT380C6C8V{B6[X2.png (10.27 KB, 下载次数: 66)

%_F38S1PT380C6C8V{B6[X2.png
回复 使用道具 举报
想了两天没想出来,主要是这所有的排列怎么弄出来啊
回复 使用道具 举报
12下一页
您需要登录后才可以回帖 登录 | 加入黑马