探讨一道JAVA题，希望用最好的算法解

Question

把整数1-9填入算式 ABCD/EFGHI中，每个数字只能用1次，且EFGHI是ABCD的2倍（整除）。输出所有可能的情况。这是很久以前我做过的一道题，当时的算法并不好，至少是O（N^2)。现在看看有没有更好的解法，请大家一起探讨。

Answer 1

E的取值是多少，我看只能是1吧？ 好像 2 + 都不行。否则EFGHI的一半一定是个五位数了。
I的取值呢？因为2倍的关系，I的取值只能是偶数。那么E的取值是1了，那么A的取值基本也固定了基本是5了

Answer 2

ABCD EFGHI
5BCD 1FGH(偶数)2 4 6 8中取 C41为I，然后剩下的就是P66。简单组合计算一下，量大概是1000次之内的计算。

Answer 3

这只是第1问，下面要求出EFGHI是ABCD的k[2,9]倍（整除）的情况，不会每次都这么分析把。

Answer 4

真的存在这样的结果吗？a = 5 #
e = 1 #
arr = [2, 3, 4, 6, 7, 8, 9]for item in arr.permutation(7)
b, c, d, f, g, h, i = *item
if i % 2 == 0
m = 10000 + f * 1000 + g *100 + h * 10 + i
n = 5000 + b * 100 + c * 10 + d
if m / n * 2 == m
p item
end
end
end我哪里出错了？ 看了一会儿。。没看出来k[2, 9]是什么意思？

Answer 5

嗯，这应该就对了：---------- Ruby ----------
[2, 3, 9, 4, 6, 7, 5, 8]
[2, 9, 4, 3, 7, 6, 5, 8]
[3, 9, 4, 2, 5, 7, 6, 8]
[4, 3, 9, 2, 7, 5, 6, 8]
[5, 8, 3, 2, 7, 4, 9, 6]
[6, 7, 2, 9, 3, 4, 5, 8]
[6, 7, 9, 2, 3, 5, 8, 4]
[6, 9, 2, 7, 3, 8, 5, 4]
[7, 2, 6, 9, 4, 5, 3, 8]
[7, 2, 9, 3, 4, 5, 8, 6]
[7, 3, 2, 9, 4, 6, 5, 8]
[7, 6, 9, 2, 5, 3, 8, 4]
[7, 9, 2, 3, 5, 8, 4, 6]
[7, 9, 3, 2, 5, 8, 6, 4]
[9, 2, 6, 7, 8, 5, 3, 4]
[9, 2, 7, 3, 8, 5, 4, 6]
[9, 3, 2, 7, 8, 6, 5, 4]
对应的是 abcd fghi
Output completed (0 sec consumed) - Normal Termination

Answer 6

[2,9]是EFGHI是ABCD 2倍-9倍
就是说要输出 ABCD/EFGHI = 1/2 ，ABCD/EFGHI = 1/3 ...... ABCD/EFGHI = 1/9等8种情况的结果
刚才写了下，ABCD/EFGHI = 1/2有12种结果
6729 13458 k = 2
6792 13584 k = 2
6927 13854 k = 2
7269 14538 k = 2
7293 14586 k = 2
7329 14658 k = 2
7692 15384 k = 2
7923 15846 k = 2
7932 15864 k = 2
9267 18534 k = 2
9273 18546 k = 2
9327 18654 k = 2
count = 12

Answer 7

写了一个，O（4！），可检测任何倍数
核心思想是对于所有可能的ABCD，乘以倍数后检验是否ABCDEFGHI刚好出现了1～9
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;public class trick1 { // 参数：  n ---- EFGHI = n * ABCD
// 返回：  含ABCD的List
public static List<Integer> find(int n) {
List<Integer> list = new ArrayList<Integer>();
int i,j,k,l;
int x;
for (i=1; i<=9; i++) {
for (j=1; j<=9; j++) {
if (j==i) continue;
for (k=1; k<=9; k++) {
if (k==i||k==j) continue;
for (l=1; l<=9; l++) {
if (l==i||l==j||l==k) continue;
x = i*1000+j*100+k*10+l;
if (validate(x,n)) list.add(x);
}
}
}
}
return list;
}

public static boolean validate(int x, int n) {
int x2 = x*n, mod;
if (x2<10000 || x2>99999) return false;
String s = ""+x+x2;
if (s.indexOf("0")>=0) return false;
HashMap map = new HashMap();
for (int i=0; i<s.length(); i++) 
map.put(s.charAt(i), null);
return map.size()==s.length();
} //测试 （2倍，3倍）
public static void main(String[] args) {
int n;
List<Integer> result;

n = 2;
System.out.println("n=" + n);
result = find(n);
for (int i=0; i<result.size(); i++) 
System.out.println(result.get(i) + " " + result.get(i)*n);
System.out.println(); n = 3;
System.out.println("n=" + n);
result = find(n);
for (int i=0; i<result.size(); i++) 
System.out.println(result.get(i) + " " + result.get(i)*n);
System.out.println();

}}

Answer 8

现在要考虑程序运行的效率，不能无脑写for循环把。应该是可以优化的，我现在还是O(N^2)

Answer 9

for循环=无脑？是你的条件给的不好吧你这个题目应该这样描述：
1～n个数 填入 X1,X2,...Xn， 给定m, 令 Xm+1...Xn刚好是X1X2...Xm的整数倍不然读者很难知道你的意图到底是需要哪些参数可变

Answer 10

其实我那种先排练的，再去计算的，速度很快。
排列组合的速度其实是很快的，因为有固定的算法。
而for的，要解决是不是重复的问题。

Answer 11

不管用什么算法排列，都要解决重复问题吧，只是api帮你实现了还是自己实现的区别，执行效率应该是一个数量级

Answer 12

从1234到100000/k循环找一遍就可以了。public void test() {
    int k = 2; //[2, 9]
    String s1, s2;
    int i, j, t;
    boolean dup;
    for (i=1234; i<100000/k; i++) {
        s1 = String.valueOf(i);
        j = i;
        dup = false;
        while (j > 0) {
            if (s1.length()-s1.replaceAll(""+(j%10), "").length() > 1) {
                dup = true;
                break;
            }
            j /= 10;
        }
        if (dup) {continue;}
        j = i * k;
        s2 = String.valueOf(k);
        t = j;
        dup = false;
        while (t > 0) {
            if (s2.length()-s2.replaceAll(""+(t%10), "").length() > 1 ||
                s1.contains(""+(t%10))) {
                dup = true;
                break;
            } 
            t /= 10;
        }
        if (dup) {continue;}
        System.out.printf("%d/%d,k=%d\n", i, j, k);
    }
}

Answer 13

这种题目标准写法都是for的，我用Ruby有讨巧的地方。我小时学GWBasic的时候都这么干。

Answer 14

排列其实是个很简单的过程http://topic.csdn.net/u/20110629/10/80643fd0-895b-4ebc-862f-08ed8c4c5ff9.html?20644
看这个C++代码，得到一个排练除了交换两个数字，就是一次递归，都谈不到时间和空间复杂度的问题。

Answer 15

恩，是写的很好。
这题如果要追求代码简洁，我也可以这样写：
for (int i=1234; i<9876; i++) {
  if (dup(i)) continue;
}
只是在楼主指定了长度为4之后，我觉得用4个for代码的复杂性还可接受，而执行效率要比上述简洁代码高。因为很多重复的在外层的for就被拦截了，不需要真的逐个比较。
现在不是要研究最好的算法么，当然是执行效率优先了
话说回来，我倒是真的很好奇O（N^2)的算法。目前大家写的，都是接近O（N^4)的

Answer 16

刚才测试了一下各位的时间 k = 2 ~ 9，所有的答案一共是89个
alexandertech 平均用时差不多0.08-0.09s,答案是对的，应该可以再优化下
(阿宝) 平均用了差不多1s,而且还错了。结果里没有0我的代码平均用时差不多0.02-0.03s,感觉写的还不够好，先贴上了看看，别用板砖砸就行了。import java.util.ArrayList;/*
 * 把整数1-9填入算式 ABCD/EFGHI中，每个数字只能用1次，且EFGHI是ABCD的k[2,9]倍（整除）。输出所有可能的情况。
 */public class Test {
static int[] num = new int[9];
static int count = 0;
/**
 * @param args null
 */
public static void main(String[] args) {
double start = System.nanoTime();
for(int i = 2;i <= 9;i++)
getResult(i);
System.out.println("count = " + count);
double end = System.nanoTime();
System.out.println("time = " + (end - start) / 1e9 + "秒");
}

/**
 * @param k [2,9]
 */
static void getResult(int k){
for(int i = 12345 / k;i <= 49876;i++){
if(i * k <= 98765 && i * k >= 12345 && check(i,i * k) == true){
System.out.println(i + " " + i * k + " k = " + k);
count++;
}
}
} static boolean check(int a,int b){
int[] num = new int[9];
while(a != 0 || b != 0){
if(b % 10 != 0 && num[b % 10 - 1] == 0)
num[b % 10 - 1] = 1;
else 
return false;
b /= 10;
if(a == 0)
continue;
if(a % 10 != 0 && num[a % 10 - 1] == 0)
num[a % 10 - 1] = 1;
else
return false;
a /= 10;

}
return true;
}
}time = 0.025207856秒

Answer 17

像这种纯数字运算，应该不要用String吧。因为String replace方法本身就是O(N)的，所以他的时间复杂度其实是O(N^3)

Answer 18

楼主，不是拍砖啊，探讨一下：1）for(int i = 12345 / k;i <= 49876;i++)这句
12345/k很巧妙，<=49876应该有问题，为什么不是<=9876呢，这样会更快2）比较速度，是不能用毫秒比的，起码在秒级别上比，象这样：
    for (int j=0; j<1000; j++)
        for(int i = 2;i <= 9;i++)
            getResult(i);    
跑1000次，比较时间才有意义。毫秒级别的跑1次误差太大
在我的机器上，跑1000次，你的程序是25.09秒，我的是19.85秒。
把你上边的49876改为9876，你的程序是9.71秒3） 为什么说这个算法是O(N^2)呢？这里N是什么？

Answer 19

如果核心算法用我的，check算法用你的，结果会更快，跑1000次4.1秒。
因为核心算法中，我拿到的是排列，比你遍历12345/K～9876更有效率
校验算法中，你用int[]，比我用HashMap节省了创建对象的时间
import java.util.ArrayList;
//import java.util.HashMap;
import java.util.List;public class trick1 {
static int count=0; // 参数：  n ---- EFGHI = n * ABCD
// 返回：  含ABCD的List
public static List<Integer> find(int n) {
List<Integer> list = new ArrayList<Integer>();
int i,j,k,l;
int x;
for (i=1; i<=9; i++) {
for (j=1; j<=9; j++) {
if (j==i) continue;
for (k=1; k<=9; k++) {
if (k==i||k==j) continue;
for (l=1; l<=9; l++) {
if (l==i||l==j||l==k) continue;
x = i*1000+j*100+k*10+l;
if (check(x,x*n))
// if (validate(x,n))
list.add(x);
}
}
}
}
return list;
}
/*
public static boolean validate(int x, int n) {
int x2 = x*n, mod;
if (x2<10000 || x2>99999) return false;
String s = ""+x+x2;
if (s.indexOf("0")>=0) return false;
HashMap map = new HashMap();
for (int i=0; i<s.length(); i++) 
map.put(s.charAt(i), null);
return map.size()==s.length();
}*/    static boolean check(int a,int b){
        int[] num = new int[9];
        int c=0;
        while(a != 0 || b != 0){
            if(b % 10 != 0 && num[b % 10 - 1] == 0) {
                num[b % 10 - 1] = 1;
                c++;
            }
            else 
                return false;
            b /= 10;
            if(a == 0)
                continue;
            if(a % 10 != 0 && num[a % 10 - 1] == 0) {
                num[a % 10 - 1] = 1;
                c++;
            }
            else
                return false;
            a /= 10;
            
        }
        return c==9;
        //return true;
    }


public static void main(String[] args) {
int n;
List<Integer> result; double start = System.nanoTime();
for (int j = 0; j < 1000; j++)
for (int i = 2; i <= 9; i++) {
result = find(i);
count += result.size();
}
        System.out.println("count = " + count);    
        double end = System.nanoTime();
        System.out.println("time = " + (end - start) / 1e9 + "秒");

/*
n = 2;
System.out.println("n=" + n);
result = find(n);
for (int i=0; i<result.size(); i++) 
System.out.println(result.get(i) + " " + result.get(i)*n);
System.out.println(); n = 3;
System.out.println("n=" + n);
result = find(n);
for (int i=0; i<result.size(); i++) 
System.out.println(result.get(i) + " " + result.get(i)*n);
System.out.println();
*/
}}

Answer 20

你改完后的代码在我的机器上跑100次0.16s,1000次只要1.3s,10000次11.3s。其实我的代码已经是O(N)了，之前100次0.56s,1000次只要3.14s,10000次29.14s。排列节约了差不多3倍的时间

Answer 21

将你的全排列算法改进了一下，在我机器上跑1000次能进1s.
public class trick1 {
static int count = 0; // 参数： n ---- EFGHI = n * ABCD
// 返回： 含ABCD的List
public static void find(int n) {
int i, j, k, l;
int x;
for (i = 12 / n; i <= 9; i++) {// 把 1 改成 12 / n
for (j = 1; j <= 9; j++) {
if (j == i)
continue;
for (k = 1; k <= 9; k++) {
if (k == i || k == j)
continue;
for (l = 1; l <= 9; l++) {
if (l == i || l == j || l == k)
continue;
x = i * 1000 + j * 100 + k * 10 + l;
if(x * n < 12345)//不加判断会多解
continue;
if (check(x, x * n)){
count++;
}
}
}
}
}
} //去掉了变量，上面已经判断
static boolean check(int a, int b) {
int[] num = new int[9];
while (a != 0 || b != 0) {
if (b % 10 != 0 && num[b % 10 - 1] == 0) {
num[b % 10 - 1] = 1;
} else
return false;
b /= 10;
if (a == 0)
continue;
if (a % 10 != 0 && num[a % 10 - 1] == 0) {
num[a % 10 - 1] = 1;
} else
return false;
a /= 10; }
return true;
} public static void main(String[] args) {
double start = System.nanoTime();
for (int j = 0; j < 1000; j++)
for (int i = 2; i <= 9; i++) {
find(i);
}
System.out.println("count = " + count);
double end = System.nanoTime();
System.out.println("time = " + (end - start) / 1e9 + "秒");
}
}