本帖最后由 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秒）- /**
- * 这个接口用于定义规则的，用户可以在这个接口的实现类中自定义规则，如果一个item符合这个规则返回真，否则返回假
- */
- interface ItemFilter {
- boolean accept(String item);// 用于检测符合的情况
- boolean exclude(String item);// 用于检测不符合的情况，以避免无谓的遍历
- }
- // 用多线程去跑，可以大大减少运行时间
- private static final int MAX_DEEP = 6;// 最大遍历深度,这个值要适当，太小了反而会影响性能,测试是6最省时间
- private static ThreadPoolExecutor threadPool = new ThreadPoolExecutor(10, 20, 5, TimeUnit.SECONDS,
- new LinkedBlockingQueue<>());// 参数5为线程死亡等待时间，这个值要设置恰当，多线程在小任务量时优势不明显，任务量越大月明显
- public static void main(String[] args) throws Exception {
- String[] values = { "H", "E", "L", "L", "O", "H", "E", "I", "M", "A", "!" };
- SortedSet<String> result = Collections.synchronizedSortedSet(new TreeSet<>());
- threadPool.allowCoreThreadTimeOut(true);
- BufferedWriter out = new BufferedWriter(new FileWriter(new File("D:\\LongResult.txt")));
- // 这里我自定义的规则是:L后面跟A，H后面跟I，E和M相隔两个字符,O和!不相邻，不能有连续两个相同的字符(如LL
- // 或HH),O在I前面(不是I前面跟O而是O的位置在I前面，可以相邻可以不相邻)
- ItemFilter filter = new ItemFilter() {
- private Pattern pattern1 = Pattern.compile("(E.{2}M)|(M.{2}E)");// 匹配E和M相隔两个字符
- private Pattern pattern2 = Pattern.compile("(.)\\1");// 匹配不能有连续两个相同的字符(如LL或HH)
- private Pattern pattern3 = Pattern.compile("O.*I");// 匹配O在I前面(不是I前面跟O而是O的位置在I前面，可以相邻可以不相邻)
- private Pattern pattern4 = Pattern.compile("O!|!O");// 匹配O和!不相邻
- private Pattern pattern5 = Pattern.compile("LA");// 匹配L后面跟A
- private Pattern pattern6 = Pattern.compile("HI");// 匹配H后面跟I
- @Override
- public boolean accept(String item) {
- boolean rule1 = pattern1.matcher(item).find();
- boolean rule3 = pattern3.matcher(item).find();
- boolean rule5 = pattern5.matcher(item).find();
- boolean rule6 = pattern6.matcher(item).find();
- return rule1 && rule3 && rule5 && rule6;
- }
- @Override
- public boolean exclude(String item) {
- // 这里面的pattern任意一个匹配成功则以此head开始的组合都是不符合规则的，所以没必要继续递归下去了
- boolean rule2 = pattern2.matcher(item).find();// 这个匹配成功表示有连续两个相同的字符
- boolean rule4 = pattern4.matcher(item).find();// 这个匹配成功表示O和!相邻
- return rule2 || rule4;
- }
- };
-
- long start = System.currentTimeMillis();
- listAvailableItems(values, "", result, filter);
- while (true) {
- Thread.sleep(100);
- if (threadPool.getPoolSize() == 0) {
- out.write("共有" + result.size() + "组\r\n");
- for (String item : result) {
- out.write(item + "\r\n");
- }
- out.flush();
- out.close();
- long end = System.currentTimeMillis();
- System.out.println("共耗时:" + (end - start) / 1000 + "秒");
- break;
- }
- }
- }
- public static void listAvailableItems(final String[] values, final String head, SortedSet<String> result,
- ItemFilter filter) {
- for (int i = 0; i < values.length; i++) {
- String[] localV = Arrays.copyOf(values, values.length);
- String localH = new String(head);
- if (localV[i] == null) {// 这里过滤掉null元素，
- continue;
- }
- localH += localV[i];// 到这里说明找到一个可用元素，则把该元素追加到已排列组合的尾部
- localV[i] = null;// 将已取走的元素从values中去除
- if (filter.exclude(localH)) {// 这个匹配成功说明此head是不符合规则的，所以没必要以此head继续递归了
- continue;
- }
- if (localH.length() == values.length) {// 这是递归结束的条件，即一个组合已排列出来，未必是符合规则的组合
- if (filter.accept(localH)) {// 这里判断这个组合是否符合规则
- result.add(localH);
- }
- return;
- }
- if (localH.length() % MAX_DEEP == 0) {
- threadPool.execute(new ST(localV, localH, result, filter));
- continue;
- }
- listAvailableItems(localV, localH, result, filter);
- }
- }
- static class ST implements Runnable {
- private String[] values;
- private String head;
- private SortedSet<String> result;
- private ItemFilter filter;
- public ST(final String[] values, final String head, SortedSet<String> result, ItemFilter filter) {
- this.values = values;
- this.head = head;
- this.result = result;
- this.filter = filter;
- }
- @Override
- public void run() {
- listAvailableItems(values, head, result, filter);
- }
- }
|
|
收藏
淘帖
踩
下不了手
