出一道题，看有没有人会 - 黑马程序员技术交流社区

/**
* 这个接口用于定义规则的，用户可以在这个接口的实现类中自定义规则，如果一个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);
}
}

复制代码

/**
* 这个接口用于定义规则的，用户可以在这个接口的实现类中自定义规则，如果一个item符合这个规则返回真，否则返回假
*/
interface ItemFilter {
boolean accept(String item);// 用于检测符合的情况
boolean exclude(String item);// 用于检测不符合的情况，以避免无谓的遍历
}
public static void main(String[] args) throws Exception {
String[] values = { "H", "E", "L", "L", "O", "H", "E", "I", "M", "A", "!" };
TreeSet<String> result = new TreeSet<>();
BufferedWriter out = new BufferedWriter(new FileWriter(new File("D:\\LResult.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();
// boolean rule2 = !pattern2.matcher(item).find();//
// 这个要匹配失败才表示没有连续两个相同的字符
//boolean rule4 = !pattern4.matcher(item).find();//
// 这个要匹配失败才表示O和!不相邻
return rule1 && rule3 && rule5 && rule6 ;//&&rule2&&rule4;
}
@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);
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 + "秒");
}
public static void listAvailableItems(final String[] values, final String head, TreeSet<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)) {//这里避免不必要的遍历
continue;
}
if (localH.toCharArray().length == values.length) {// 这是递归结束的条件，即一个组合已排列出来，未必是符合规则的组合
if (filter.accept(localH)) {// 这里判断这个组合是否符合规则
result.add(localH);
}
return;
}
listAvailableItems(localV, localH, result, filter);// 到这里说明还没有排列完成一个组合，则继续递归
}
}

复制代码