《Thinking in Java》上的题目，大家帮忙看看

Question

四位数的吸血鬼数字是由两个二位数的数字相乘而得到,而且此吸血鬼数字由这两个二位数的数字组成,但不允许以两个0结尾,找出所有的四位数的吸血鬼数字.
例:
1260 = 21 * 60
1827 = 21 * 87
2187 = 27 * 81 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝for(int i = 1001; i <= 9801; i ++){
         if(i % 100 == 0){
         continue;
}
for(int j = 11; j <= 99; j++){
int k = i / j;
if(k * j != i || k > 99){
continue;
}
String a = Integer.toString(i);
String b = Integer.toString(j);
String c = Integer.toString(k);
char[] d = b.toCharArray();
if(a.indexOf(d[0]) == -1 || a.indexOf(d[1]) == -1){
continue;
}
a = a.replaceAll("("+d[0]+"|"+d[1]+")", "");
if(a.equals(c)){
System.out.println(i + " = " + j + " * " + k);
break;
}
}
}总觉得自己写的太复杂了，有没有更简单点的解法？

Answer 1

if(a.equals(c)){
System.out.println(i + " = " + j + " * " + k);
break;
}
你的这里漏了

Answer 2

1260 = 21 * 60
1395 = 93 * 15
1435 = 41 * 35
1530 = 51 * 30
1827 = 21 * 87
2187 = 81 * 27能算出来的就这么多，加不加那个break都一样。

Answer 3

写了一个，可能性能好一些。
long startTime1 = System.currentTimeMillis();
for (int i = 11; i <= 99; i++) {
for(int j=11+i-11; j<=99; j++ ){
int k = i*j;
if(k% 100 == 0)
continue;
String a = Integer.toString(i);
String ab = Integer.toString(k);
String b = Integer.toString(j);
char[] aa = a.toCharArray();
char[] bb = b.toCharArray();
if(ab.length()<4)
continue;if (ab.indexOf(aa[0]) == -1 || ab.indexOf(aa[1]) == -1) {
continue;
}
if (ab.indexOf(bb[0]) == -1 || ab.indexOf(bb[1]) == -1) {
continue;
}
ab = ab.replaceFirst("(" + aa[0] + ")", "");
ab = ab.replaceFirst("(" + aa[1] + ")", "");
ab = ab.replaceFirst("(" + bb[0] + ")", "");
ab = ab.replaceFirst("(" + bb[1] + ")", "");
if (ab.length() == 0) {
System.out.println(k + " = " + i + " * " + j);
break;
}
}
}
long stopTime1 = System.currentTimeMillis();
System.out.println(stopTime1-startTime1);

Answer 4

我的break去掉就OK了
1395 = 15 * 93
1260 = 21 * 60
1827 = 21 * 87
2187 = 27 * 81
1530 = 30 * 51
1435 = 35 * 41
6880 = 80 * 86
16
共7个，16ms

Answer 5

cocogg() 的答案应该没有错了，不过问一下，j=11+i-11; 和 j=i; 有什么区别？为什么要这样写？

Answer 6

for(int i = 1001; i <= 9801; i ++){
         if(i % 100 == 0){
         continue;
}to for(int i = 1001; i <= 9801; i ++){
         if(i % 100 == 0 || i % 9 != 0){
         continue;
}

Answer 7

/*
 * IBM Confidential
 * 
 * OCO Source Materials
 * 
 * #ID# IBM CRL Supply Chain Management Research
 * 
 * (C) Copyright IBM Corp. 2005
 * 
 * The source code for this program is not published or otherwise divested of
 * its trade secrets.
 * 
 */
package atest;public class Test4 {
public static void main(String[] args) {
int as [] = new int[4];
int bs [] = new int[4];

long startTime1 = System.currentTimeMillis();
for (int i = 11; i <= 99; i++) {
for (int j = i; j <= 99; j++) 
{
int k = i * j;
if (k % 100 == 0 || k < 1001 || k % 9 != ( i+ j ) % 9)
continue;


as[0] = i / 10;
as[1] = i % 10;
as[2] = j / 10;
as[3] = j % 10;
bs[0] = k % 10;
bs[1] = k / 10;
bs[2] = bs[1] / 10;
bs[3] = bs[2] / 10;
bs[2] = bs[2] % 10;
bs[1] = bs[1] % 10;
for (int x = 0; x < 4;x++)
{
for (int y = 0 ; y < 4 ; y++)
{
if (as[x] == bs[y])
{
as[x] = -1;
bs[y] = -1;
}
}
}
boolean flag = false;
for (int x = 0; x < 4;x++)
{
if (as[x] != -1 || bs[x] != -1)
{
flag = true;
continue;
}
}
if (flag)
{
continue;
}
//
// if (! ( k0 == a1 || k0 == a0 ||   k0 == b1 || k0 == b0)
// )
// {
// continue;
// }
// if (!( k1 == a1 || k1 == a0 ||   k1 == b1 || k1 == b0)) 
// {
// continue;
// }
// if (!( k2 == a1 || k2 == a0 ||   k2 == b1 || k2 == b0))
// {
// continue;
// } 
// if (!( k3 == a1 || k3 == a0 ||   k3 == b1 || k3 == b0))
// {
// continue;
// }
// String a = Integer.toString(i);
// String ab = Integer.toString(k);
// String b = Integer.toString(j);
// char[] aa = a.toCharArray();
// char[] bb = b.toCharArray();
//
// if (ab.indexOf(aa[0]) == -1 || ab.indexOf(aa[1]) == -1) {
// continue;
// }
// if (ab.indexOf(bb[0]) == -1 || ab.indexOf(bb[1]) == -1) {
// continue;
// }
// ab = ab.replaceFirst("(" + aa[0] + ")", "");
// ab = ab.replaceFirst("(" + aa[1] + ")", "");
// ab = ab.replaceFirst("(" + bb[0] + ")", "");
// ab = ab.replaceFirst("(" + bb[1] + ")", "");
// if (ab.length() == 0) {
System.out.println(k + " = " + i + " * " + j);
// }
}
}
long stopTime1 = System.currentTimeMillis();
System.out.println(stopTime1 - startTime1);
}}// end1395 = 15 * 93
1260 = 21 * 60
1827 = 21 * 87
2187 = 27 * 81
1530 = 30 * 51
1435 = 35 * 41
6880 = 80 * 86
0
始终为0;不知怎么回事

Answer 8

k % 9 != ( i+ j ) % 9)
不明白

Answer 9

public class MagicNumber {  static boolean sameDigitals(int s, int s1, int s2) {
    int[] a1 = new int[10];
    int[] a2 = new int[10];
    while (s > 0) {
      a1[s % 10]++;
      s /= 10;
    }
    a2[s1 / 10]++;
    a2[s1 % 10]++;
    a2[s2 / 10]++;
    a2[s2 % 10]++;
    for (int i = 0; i < 10; i++) {
      if (a1[i] != a2[i]) {
        return false;
      }
    }
    return true;
  }     public static void main(String[] args) {
    long begin = System.currentTimeMillis();
    int count = 0;
    for (int i = 11; i < 100; i++) {
      for (int j = 11; j < i; j++) {
        int mut = i * j;
        if (mut < 1000 || mut % 100 == 0) {
          //非四位数或以两个0结尾
          continue;
        }
        if (sameDigitals(mut, i, j)) {
          System.out.println(++count + ":" + mut + "=" + i + "*" + j);
        }
      }
    }
    long end = System.currentTimeMillis();
    System.out.println("Time used: " + (end - begin) + "ms");
  }
}运行时间可能是15ms，也可能是0m。
1:1435=41*35
2:1530=51*30
3:1260=60*21
4:2187=81*27
5:6880=86*80
6:1827=87*21
7:1395=93*15
Time used: 0ms1:1435=41*35
2:1530=51*30
3:1260=60*21
4:2187=81*27
5:6880=86*80
6:1827=87*21
7:1395=93*15
Time used: 15ms

Answer 10

k % 9 != ( i+ j ) % 9)
-------------------------------------------
一个数mod 9 和他的数位之和mod9一样所以 k % 9 是指k的总数位之和( i+ j ) % 9 是指i ,j的总数位之和如果它两不等,就没有必要判断了

Answer 11

当时我写的最直接的实现
public class vampireNumber {
public static void main(String[] args) {
long startTime = System.currentTimeMillis();   //获取开始时间 for(int i=1000;i<10000;i++) {
int a = i/1000;
int b = i/100-10*a;
int d = i%10;
int c = (i%100 - d) / 10;
if( (10*a+b)*(10*c+d)==i || (10*a+c)*(10*b+d)==i || (10*a+d)*(10*b+c)==i ||(a+10*b)*(10*c+d)==i || (a+10*c)*(10*b+d)==i || (a+10*d)*(10*b+c)==i ||(10*a+b)*(c+10*d)==i || (10*a+c)*(b+10*d)==i || (10*a+d)*(b+10*c)==i){
System.out.println("VampireNumber : "+i);
}

} long endTime = System.currentTimeMillis(); //获取结束时间
System.out.println("程序运行时间： "+(endTime-startTime)+"ms");

}}VampireNumber : 1260
VampireNumber : 1395
VampireNumber : 1435
VampireNumber : 1530
VampireNumber : 1827
VampireNumber : 2187
VampireNumber : 6880
程序运行时间： 16ms

Answer 12

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
public class TestGhost {    public static void main(String[] args) {
         long start=System.currentTimeMillis();
        List<Integer> source = new ArrayList<Integer>();
        List<Integer> dest = new ArrayList<Integer>();        Set<Integer> result=new TreeSet<Integer>();
        for (int i = 11; i <= 99; i++) {
            
            
            for (int j = 11; j <= 99; j++) {
                 int k = i * j;
                if (k < 1000||k%100==0) {
                    continue;
                }
                source.clear();
                source.add(i / 10);
                source.add(i%10);
                source.add(j/10);
                source.add(j%10);
                Collections.sort(source);
                dest.clear();
                dest.add(k%10);
                dest.add(k/10%10);
                dest.add(k/100%10);
                dest.add(k/1000);
                Collections.sort(dest);                if(source.equals(dest)){
                     
                    result.add(k);
                }
            }
        }           System.out.println(result);
        System.out.println((System.currentTimeMillis()-start)+"ms");
    }
}
我认为我的算法比较容易看懂
就是时间稍长了一些
[1260, 1395, 1435, 1530, 1827, 2187, 6880]
26ms

Answer 13

兄弟 你把for (int j = 11; j <= 99; j++)  这句"j <=99"改成"j<=i" 速度就快了，话说用这么多集合类有点小题大做了
其实14楼写的就已经很完美了，算法也很好

Answer 14

１９楼提醒了一下，现在平均６ms左右就可以算完了我还是觉得我的方法容易理解哈，不过您可以不同意。。呵呵
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
public class TestGhost {    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        List<Integer> source = new ArrayList<Integer>();
        List<Integer> dest = new ArrayList<Integer>();
        for (int i = 11; i <= 99; i++) {
            for (int j = 11; j <= i; j++) {
                int k = i * j;
                if (k < 1000 || k % 100 == 0) {
                    continue;
                }
                int a1 = i / 10;
                int a2 = i % 10;
                int a3 = j / 10;
                int a4 = j % 10;
                int b1 = k % 10;
                int b2 = k / 10 % 10;
                int b3 = k / 100 % 10;
                int b4 = k / 1000;
                if (a1 + a2 + a3 + a4 != b1 + b2 + b3 + b4) {
                    continue;
                }
                source.clear();
                source.add(a1);
                source.add(a2);
                source.add(a3);
                source.add(a4);
                Collections.sort(source);
                dest.clear();
                dest.add(b1);
                dest.add(b2);
                dest.add(b3);
                dest.add(b4);
                Collections.sort(dest);                if (source.equals(dest)) {
                    System.out.println(k + "=" + i + "*" + j);
                }            }
        }        System.out.println((System.currentTimeMillis() - start) + "ms");
    }
}输出
1435=41*35
1530=51*30
1260=60*21
2187=81*27
6880=86*80
1827=87*21
1395=93*15
6ms

Answer 15

我运行你的程序都是15,16,0ms没出现过6ms呀。。

Answer 16

解释一下１２楼，一个数如果能被９整除，那么它的各位数字之和也能被９除。
就像是一个数如果能被３整数，它的各位数字之和也能被３除
k=a1*10^3+a2*10^2+a3*10+a4
 =a1*999+a1+a2*99+a2+a3*9+a3+a4
 =9*(111*a1+11*a2+a3)+(a1+a2+a3+a4)
 
所以k除以９的余数与a1+a2+a3+a4相同 

Answer 17

我是win7-64　　t6670或许快一点吧。

Answer 18

在我机子上可以5ms
不过我知道，这只能算是一个基本过得去的算法。学无止境
package javaapplication1;import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
public class TestGhost {    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        List<Integer> source = new ArrayList<Integer>();
        List<Integer> dest = new ArrayList<Integer>();
        for (int i = 11; i <= 99; i++) {
            for (int j = 11; j <= i; j++) {
                int k = i * j;
                if (k < 1000 || k % 100 == 0||(i+j)%9!=k%9) {
                    continue;
                }
                int a1 = i / 10;
                int a2 = i % 10;
                int a3 = j / 10;
                int a4 = j % 10;
             
                int b1 = k % 10;
                int b2 = k / 10 % 10;
                int b3 = k / 100 % 10;
                int b4 = k / 1000;
                if (a1 + a2 + a3 + a4 != b1 + b2 + b3 + b4) {
                    continue;
                }
                source.clear();
                source.add(a1);
                source.add(a2);
                source.add(a3);
                source.add(a4);
                Collections.sort(source);
                dest.clear();
                dest.add(b1);
                dest.add(b2);
                dest.add(b3);
                dest.add(b4);
                Collections.sort(dest);                if (source.equals(dest)) {
                    System.out.println(k + "=" + i + "*" + j);
                }            }
        }        System.out.println((System.currentTimeMillis() - start) + "ms");
    }
}

Answer 19

public class Test {
public static void main(String[] args) {
int k = 0;
String resuStr;
String leftStr;
char[] resuChars;
char[] leftChars;
boolean flag = false;

long   start   =   System.currentTimeMillis(); 
//避免重复，避免两个数都0结尾
for(int i = 10; i < 100; i++) {
for(int j = i + 1; j < 100; j++) {
k = i * j;

resuStr = Integer.toString(k);

//判断是否为四位数
if(resuStr.length() != 4) {
continue;
}

//拼接表达式左边相剩部分
leftStr = Integer.toString(i) + Integer.toString(j);

//遍历比较
resuChars = resuStr.toCharArray();
leftChars = leftStr.toCharArray();

for(char oneChar : resuChars) {
flag = false;
for(int n = 0; n < leftChars.length;  n++) {
if(oneChar == leftChars[n]) {
leftChars[n] = ' ';
flag = true;
break;
}
}
if(!flag) {
break;
}
}

if(flag) {
//此等式成立，输出结果
System.out.println( i + " * " + j + " = " + k);
flag = false;
}
}
}

long   stop   =   System.currentTimeMillis();
System.out.println(stop-start);
}
}
要了15ms
慢慢总结一下规律应该还可以做一下忧化的
编程这种东西就是这样了

Answer 20

接着补充１２楼
a1*10+a2+a3*10+a4＝i+j=a1+a2+a3+a4+9(a1+a3) 显然它和a1+a2+a3+a4被９除后的余数相同而k=a1*10^3+a2*10^2+a3*10+a4=9*(111*a1+11*a2+a3)+(a1+a2+a3+a4)
    亦和a1+a2+a3+a4被９除后的余数相同所以它们处于被９除的同一个等价类中

Answer 21

貌似都不是think in java啊。

Answer 22

看我的：【说明：以下的程序代码比各位的都要长，且运行时间也肯定最长，因为里头构造了3个类，但每个类都有鲜明的特征和含义，且代码可以重用，符合thinking in java的思路，而且main函数简单清楚，一看就懂。】//寻找4位数的Vampire数字
class findVamp
{
public static void main(String args[])
{
int i,j = 0;
long startTime1 = System.currentTimeMillis(); 
Vampire vam; for (i=1000; i<10000; i++)
{
vam = new Vampire(i); if (vam.isQualified)
{
vam.Count++;
j = vam.Count;
System.out.println("Vampire Number : " + i + " = " + vam.twoDigitNum1[vam.pairs] + " * " + vam.twoDigitNum2[vam.pairs]);
}
}
System.out.println("Total " + j + " Numbers"); long stopTime1 = System.currentTimeMillis(); 
System.out.print("Time used ：");
System.out.print(stopTime1-startTime1);
System.out.println("ms");
}
}//构造一个4位数的类，且不能以00结尾
class FourDigitNum
{
static Boolean isQualified = false;
static int Count = 0; FourDigitNum(int Num)
{
if (Num >1000 && Num <10000 && Num % 100 != 0)
isQualified = true;
}
}//从4位数类派生一个类，此类的数字都可以被分解为两个两位数的乘积
class FDNCanBeDiv extends FourDigitNum
{
static int[] twoDigitNum1, twoDigitNum2;
static int pairs = 0; //注：该成员变量记录了当前的四位数可以分解为多少对的两位数乘积 FDNCanBeDiv(int Num)
{
super(Num);

if (isQualified)
{
twoDigitNum1 = new int[100];
twoDigitNum2 = new int[100];
int i,j; pairs = 0; for (i=11; i<100; i++)
{
j = Num / i;
if (j * i != Num) continue;
if (j<11 || j>99) continue;
twoDigitNum1[pairs] = i;
twoDigitNum2[pairs] = j;
pairs++;
}
if (pairs == 0)
isQualified = false;
}
}}//vampire类
class Vampire extends FDNCanBeDiv
{
Vampire(int Num)
{
super(Num);
if (isQualified)
{
char a,b,c,d,tmp[];
String tmpStr;
int i; for (i=0; i<pairs; i++)
{
//a和b是第一个两位数的两个数字，类型为char
tmpStr = Integer.toString(twoDigitNum1[i]);
tmp = tmpStr.toCharArray();
a = tmp[0];
b = tmp[1]; //c和d是第二个两位数的两个数字，类型为char
tmpStr = Integer.toString(twoDigitNum2[i]);
tmp = tmpStr.toCharArray();
c = tmp[0];
d = tmp[1];

//将乘积中数字字符，根据两个两位数中的每一个数字字符点名
tmpStr = Integer.toString(Num);
tmpStr = tmpStr.replaceFirst("(" + a + ")" , "x");
tmpStr = tmpStr.replaceFirst("(" + b + ")" , "x");
tmpStr = tmpStr.replaceFirst("(" + c + ")" , "x");
tmpStr = tmpStr.replaceFirst("(" + d + ")" , "x"); if (tmpStr.equals("xxxx"))
{
pairs = i;
return;
}
}
isQualified = false;
}
}
}
【程序的运行结果】
C:\Program Files\Java\jdk1.6.0_23\test>javac findVamp.javaC:\Program Files\Java\jdk1.6.0_23\test>java findVamp
Vampire Number : 1260 = 21 * 60
Vampire Number : 1395 = 15 * 93
Vampire Number : 1435 = 35 * 41
Vampire Number : 1530 = 30 * 51
Vampire Number : 1827 = 21 * 87
Vampire Number : 2187 = 27 * 81
Vampire Number : 6880 = 80 * 86
Total 7 Numbers
Time used : 125ms

Answer 23

Think in java里有这题？楼上的解法都很聪明。