一道java面试题目

给出下题的算法(Java语言实现)
将1、2、3、4、5、6、7、8、9 这九个数字分成三个百位数,每个数字用且只用一次,
并且第三个数字是第一个的3倍,第二个数字是第一个的2倍。
求三个数。[说明,结果可能多于一组,例如327 654 981]
这个是看到一家公司的面试题目,想了一下还没有找到什么好的方法来解决。
请各位帮下忙。

7个回答

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class Test {

public static void main(String[] args) {
    int i,j,k,m,n,t1,t2,t3;
    Set total=new HashSet();
    for(int t=1;t<10;t++) {
        total.add(t);
    }
    Set set=new HashSet();
    Set lastThree=new HashSet();
    for(i=1;i<4;i++) {
        set.add(i);
        for(j=1;j<10;j++) {
            if(j==i){ continue;}
            set.add(j);
            for(k=1;k<10;k++) {
                if(k==i||k==j) { continue;}
                set.add(k);
                m=3*(i*100+j*10+k);
                if(m>987){set.remove(k);continue;}//如果已超出范围,没必要再往下判断
                t1=m%10; if(t1==0) {set.remove(k);continue;} //个位数
                t2=(m%100)/10; if(t2==0) {set.remove(k);continue;} //十位数
                t3=m/100;  if(t3==0) {set.remove(k);continue;}//百位数
                if(set.contains(t1)){set.remove(k);continue;}
                set.add(t1);
                if(set.contains(t2)) {set.remove(k);set.remove(t1);continue;}
                set.add(t2);
                if(set.contains(t3)) {set.remove(k);set.remove(t1);set.remove(t2);continue;}
                set.add(t3);
                //System.out.println("  "+i+j+k+"   "+m);
                total.removeAll(total);
                for(int q=1;q<10;q++) {
                    total.add(q);
                }
                total.removeAll(set);
                int[] s=new int[3];
                Iterator iterator=total.iterator();
                int p=0;
                while(iterator.hasNext()) {
                    s[p]=Integer.parseInt(iterator.next()+"");
                    p++;
                }
                n=s[0]*100+s[1]*10+s[2];   
                if(n==2*(i*100+j*10+k)) { System.out.println(i+""+j+""+k+"    "+n+"    "+m);}
                n=s[0]*100+s[2]*10+s[1];    
                if(n==2*(i*100+j*10+k)) { System.out.println(i+""+j+""+k+"    "+n+"    "+m);}
                n=s[1]*100+s[0]*10+s[2];   
                if(n==2*(i*100+j*10+k)) { System.out.println(i+""+j+""+k+"    "+n+"    "+m);}
                n=s[1]*100+s[2]*10+s[0]; 
                if(n==2*(i*100+j*10+k)) { System.out.println(i+""+j+""+k+"    "+n+"    "+m);}
                n=s[2]*100+s[0]*10+s[1]; 
                if(n==2*(i*100+j*10+k)) { System.out.println(i+""+j+""+k+"    "+n+"    "+m);}
                n=s[2]*100+s[1]*10+s[0]; 
                if(n==2*(i*100+j*10+k)) { System.out.println(i+""+j+""+k+"    "+n+"    "+m);}
                set.remove(t1);
                set.remove(t2);
                set.remove(t3);
                set.remove(k);
            } 
               set.remove(j);
        }
        set.remove(i);
    }
}

}

运行结果:
192 384 576
219 438 657
273 546 819
327 654 981

我的思想是,第一个数百位数最大为3,可谓一层循环,十位和各位则组成两层循环。
用一个Set容器来存储第一个三位数,利用第一个数求出第三个数(3倍第一个数),把第三个数的每一位求出,看是否符合,符合则加入set容器,而这时只剩下三个数,对这三个数的六种情况求解,等于第一个数的两倍即成立。很麻烦,思想很简单

可以当作一个排列组合来做,运用穷举法。可以把3个数字看作9个坑,9个数字往9个坑里填,一旦满足条件就输出,不过这是个笨办法。

千万别穷举,我用Erlang试了,会挂的:)~

应该这样算比较块:

  1. 循环从111 -> 333的数字,遇到有0的continue
  2. [N, N * 2, N * 3] 这样就可以作为一个正确序列了

应该是正解把, 赫赫, 没测试过

package com.A;

public class InterViewDemo {
public InterViewDemo() {
int i, j, k, l;

    for (i = 111; i < 999; i++) {
        j = i / 100;// 得到三位数的百位数
        k = i / 10 - j * 10;// 得到三位数的十位数
        l = i - j * 100 - k * 10;// 得到三位数的个位数
        if (j % 3 == 0 && k % 2 == 0 && k != 0 && l != 0)// 由于在111到999之间有含有零的数,所以十位数和各位数不能等于零
            if (j != k && j != l && k != l)//个位和十位以及百位数不能相等
                System.out.println(i);

    }

}

public static void main(String[] args) {

    new InterViewDemo();

}

}

不好意思 题目看错啦 哈哈 :oops:

先分析一下结果的可能性,第一个数字必然是1**-3**之间,分析每组的第一个数字有以下几种组合:

1** - 2** - 3**
1** - 2** - 4**

1** - 3** - 4**
1** - 3** - 5**

2** - 4** - 6**
2** - 4** - 7**

2** - 5** - 7**
2** - 5** - 8**

3** - 6** - 9**
这样有9中组合,然后在每种组合中还有6个剩余的数字来进行组合,
循环次数为9*6^6.
在每次循环中对比较的算法进行设计也会很大的提升效率,我的初步设想是每一种组合只判断前两个数之和是否是第三个数,因为加运算远比乘法运算要高效,如果满足了这个条件再进行倍数验证,如果满足则输出。

又想了一下,循环次数可以少于9*6^6。
在每种组合中三个数字确定,有6个位置需要填充,首先判断前四个位置填充后前两个三位数是否满足2倍条件,如果不满足就不用再组合第五六个位子,这样循环次数就会减少很多。

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!