最近在读《Thinking in JAVA》,在里面发现一个很有意思的题，该题在75页，第四章第十题

原题：

吸血鬼数字是指位数为偶数的数字，可以由一堆数字想乘而得到。而这对数字各包含乘积的一半位数的数字，其中从最初的数字中选取的数字可以任意排序。以两个0结尾的数字是不允许的，例如，下列的数字都是“吸血鬼”数字：

1260=21*60

1827=21*87

2187=27*81

写出一个程序，找出4位数的所有吸血鬼数字

先列出一种书上给的答案，程序我稍微优化了一下，思想没变

public static int a(int i) {return i/1000;}public static int b(int i) {return (i%1000)/100;}public static int c(int i) {return ((i%1000)%100)/10;}public static int d(int i) {return i%10;}public static int com(int i, int j) {return (i * 10) + j;}public static void productTest (int i, int m, int n) {num++;if(m * n == i) System.out.println(i + " = " + m + " * " + n);}public static void main(String[] args) {for(int i = 1001; i < 9999; i++) {int a=a(i);int b=b(i);int c=c(i);int d=d(i);productTest(i, com(a, b), com(c, d));productTest(i, com(a, b), com(d, c));productTest(i, com(a, c), com(b, d));productTest(i, com(a, c), com(d, b));productTest(i, com(a, d), com(b, c));productTest(i, com(a, d), com(c, b));productTest(i, com(b, a), com(c, d));productTest(i, com(b, a), com(d, c));productTest(i, com(b, c), com(d, a));productTest(i, com(b, d), com(c, a));productTest(i, com(c, a), com(d, b));productTest(i, com(c, b), com(d, a));}}

 该方法共运算了107976次 用时26ms

每个人电脑不一样用时可能不一样，但是运算次数肯定是一样的

这种方法简单粗暴，一个遍历，然后就是挑，因为这是前章的内容，所以作者也没用太高明的方法，主要演示循流程控制

我一寻思，不行啊，我写一个更好的

四个数两两组合想乘等于一个四位数，那这个四位数肯定不能有两个0

解释一下：首先千位不能是0，两个零都放到低位想乘得0，只能左边一个右边一个，如果是百位和十位是0，那么想乘出来个位不是0，与条件相反，如果百位和个位是0，那么想乘出来十位和个位是0，与条件想法，所以说四位数肯定不能有两个0

加上这个过滤跑一下试试

 for(int i = 1001; i < 9999; i++) {//得到百位数、十位数、个位数int a=a(i);int b=b(i);int c=c(i);int d=d(i);//如果个十百千四个数中有两个是0，那么就不可能是吸血鬼数字// 千位肯定不是0，剩下的三个数俩是0，所以三个数的和等于其中一个数if (b+c+d==b||b+c+d==c||b+c+d==d){continue;}productTest(i, com(a, b), com(c, d));productTest(i, com(a, b), com(d, c));productTest(i, com(a, c), com(b, d));productTest(i, com(a, c), com(d, b));productTest(i, com(a, d), com(b, c));productTest(i, com(a, d), com(c, b));productTest(i, com(b, a), com(c, d));productTest(i, com(b, a), com(d, c));productTest(i, com(b, c), com(d, a));productTest(i, com(b, d), com(c, a));productTest(i, com(c, a), com(d, b));productTest(i, com(c, b), com(d, a));}

该方法共运算了104964次，时间26ms

好像并没啥变化哈，只有运算少了一点点

那我们反过来想，不拆四位数了，我们两个两位数想乘等于四位数，然后拼接两个两位数成数组，经过排序后和四位数的数组对比

for (int i=10;i<100;i++){for (int j=i+1;j<100;j++){int target=i*j;if (target<1000||target>9999){continue;}num++;int[] targetNum = { target / 1000, target / 100 % 10, target / 10 % 100 % 10, target%10 };int[] strNum = { i % 10, i / 10, j % 10, j / 10 };Arrays.sort(targetNum);Arrays.sort(strNum);if (Arrays.equals(targetNum,strNum)){System.out.println(target + " = " + i + " * " + j);}}}

该方法共运算了3271次 时间13ms

确实有效，无论是运算次数还是时间都缩短了不少

想不到更好的办法就百度，找到一种不错的，它用了一种很巧妙的过滤，大体思路是这样的：

首先2个数的乘积是4位数(大于等于1000,小于10000),一个数确定时,另一个数范围随之确定

随后不能有两个数为0，千位不是0，所以说后两位不能是0

最后四位数减去前两位和后两位可以被9整除

前面两个条件没问题，主要是最后条件很奇怪：

假设a,b,c,d分别代表千位数、百位数、十位数、个位数，x,y分别代表两个两位数，那么a*1000+b*100+c*10+d=四位数

10x+y=四位数，x=10*a+b，y=10*c+d，四位数-x-y=990a+99b+9c=9*(110a+11b+c)

所以说四位数减两个两位数的结果肯定可以被9整除

String[] ar_str1, ar_str2;int from;int to;int i_val;for (int i = 10; i < 100; i++) {from = Math.max(1000 / i, i + 1);to = Math.min(10000 / i, 100);// 2个数的乘积是4位数(大于等于1000,小于10000),i确定时,另一个数范围随之确定for (int j = from; j < to; j++) {i_val = i * j;if (i_val % 100 == 0 || (i_val - i - j) % 9 != 0) {continue;}num++;ar_str1 = String.valueOf(i_val).split("");ar_str2 = (String.valueOf(i) + String.valueOf(j)).split("");Arrays.sort(ar_str1);Arrays.sort(ar_str2);if (Arrays.equals(ar_str1, ar_str2)) {System.out.println(i_val + " = " + i + " * " + j);}}}

该方法共运算了232次，时间60ms

运算次数一下子减少了很多，但是时间却上涨了不少，我想可能是后面字符串导致的，整形数组比较远比字符串数组操作快速，因为字符串数组的底层实现也是整形数组（我猜的，有错误请指正）

int[] startDigit = new int[4];int[] productDigit = new int[4];int target;for (int i = 10; i <= 99; i++) {for (int j = i; j <= 99; j++) {target = i * j;if (target % 100 == 0 || (target - i - j) % 9 != 0) {continue;}startDigit[0] = i / 10;startDigit[1] = i % 10;startDigit[2] = j / 10;startDigit[3] = j % 10;productDigit[0] = target / 1000;productDigit[1] = (target % 1000) / 100;productDigit[2] = target % 1000 % 100 / 10;productDigit[3] = target % 10;int count = 0;for (int x = 0; x < 4; x++) {for (int y = 0; y < 4; y++) {num++;if (productDigit[x] == startDigit[y]) {count++;productDigit[x] = -1;startDigit[y] = -2;if (count == 4) {System.out.println(target + " = " + i + " * " + j);}}}}}}

该方法共运算了4712次，时间1ms

过滤后有232个数，每个数颠倒顺序比对16遍

前面那个范围过滤没什么必要，可以减少一定次数，但是时间也会增加

如果你有更好的方法请留言给我