一道面试题，欢迎进来讨论

Question

将1-9九个数字组合成3个三位的数字。要求1-9每个数字只使用一次，且第二个数是第一个数的两倍，第三个数是第一个数的三倍（例如：192，384，576）。符合条件的数有几组？将它们打印出来。
面试的时候，思路很混乱，回来后想到一种思路，代码如下：/**
 * 问题：
 *     将1-9九个数字组合成三个三位数。要求1-9每个数字只使用一次，且第二个数是第一个数的两倍，第三个数是第一个数的三倍。
 *     符合条件的数有几组？将他们打印出来。
 * 思路:
 *     从数字方向考虑，找出123-987之间符合题目倍数关系的三个数字，然后再检查三个数是否有重复数字。
 * @author Jeby
 *
 */
public class Group { /**
 * @param args
 */
public static void main(String[] args) {
find();
}

public static void find() {
int a = 0;
int b = 0;
int c = 0;
int count = 0;
for(int i=123;i<=329;i++) {
a = i;
for(int j=246;j<=658;j++) {
b = j;
for(int k=369;k<=987;k++) {
c = k;
if(b==a*2 && c==a*3 && check(a+""+b+""+c)) {
count++;
System.out.println(a+" "+b+" "+c);
}
}
}
}
System.out.println("符合条件的有"+count+"组");
}
/**
 * 去掉字符串中重复的字符，得到一个新字符串，和原字符串比较长度，以此检查是否有重复字符。
 * @param str
 * @return
 */
public static boolean check(String str) {
char[] chars = str.toCharArray();
String afterCheck = "";
for(int i=0;i<chars.length;i++) {
if(afterCheck.indexOf(chars[i])==-1) {
afterCheck += chars[i]; 
}
}
return str.length()>afterCheck.length()?false:true;
}
}程序运行结果：
192 384 576
219 438 657
267 534 801
273 546 819
327 654 981
符合条件的有5组这个题应该还有其他的答案，请赐教。

Answer 1

思路没问题吧。
还可以提高下效率，
把三个循环压成一个就可以了：
在循环体内(int i=123;i<=329;i++) 
直接计算 b = i*2; c = i*3;进一步的优化是提前判断重复数字，比如 133，144，222。还有是124，i*2 = 248，这样也会产生重复，判断一下i的三位数是否有倍数关系也多少可以提升效率。最后判断3个子串是否有数字重复，那方法就多了..
可以直接循环遍历，也可以拆分后用累加法，hash法等等。

Answer 2

自己也写了个
/**
 * 问题：
 *     将1-9九个数字组合成三个三位数。要求1-9每个数字只使用一次，且第二个数是第一个数的两倍，第三个数是第一个数的三倍。
 *     符合条件的数有几组？将他们打印出来。
 *     
 * @author xqh
 *
 */
public class TestGroup {
public static void main(String[] args) {
for (int i = 123; i <= 329; i++) {
if (parseStr(i+""+i*2+""+i*3+"")) 
System.out.println(i + " " + i*2 + " " + i*3);
}
}

/**
 * 判断是否有重复数字
 * @param str 字符串
 * @return 如果重复则返回false,否则返回false
 */
public static boolean parseStr(String str) {
char[] ch = str.toCharArray();
String result = "";
for (int i = 0; i < ch.length; i++) {
if (result.indexOf(ch[i]) == -1) 
result += ch[i];
}
return result.length() == str.length() ? true : false;
}
}

Answer 3

public class Test2 {

public static void main(String[] args) {

    int maxDisTreeNum = 987;
for(int i=123;i<=maxDisTreeNum/3;i++){
if(check(i)){

System.out.println(i+"  "+ i*2 +"  "+i*3);
}
} }

public static  boolean check(int firstNum){

String strFirstNum = firstNum+"";
String strSecondNum = firstNum*2+"";
String strThirdnum = firstNum*3+"";

Set<Character> hashset = new HashSet<Character>();
String[] arr = new String[]{strFirstNum,strSecondNum,strThirdnum};
for(int i=0;i<arr.length;i++){
String temp = arr[i];
for(int j=0;j<temp.length();j++){
hashset.add(temp.charAt(j));
}
}

if(hashset.size()!=9){
return false;
}

return true;
}}

Answer 4

楼主。你太不厚道了。将1-9九个数字组合成3个三位的数字，你的答案中出现了一组267 534 801  让我找半天 也得不到你的答案。。
package 类的继承;public class 网上的面试题 {
public static void main(String[] args) {

int []a =new int[9];
int count=0;
for(int i0=1;i0<=9;i0++){
a[0]=i0;

for(int i1=1;i1<=9;i1++){
a[1]=i1;
if(a[0]==a[1]) continue;




for(int i2=1;i2<=9;i2++){
a[2]=i2;
if(a[2]==a[1]||a[2]==a[0]) continue;

for(int i3=1;i3<=9;i3++){
a[3]=i3;
if(a[3]==a[0]||a[3]==a[1]||a[3]==a[2]) continue;

for(int i4=1;i4<=9;i4++){
a[4]=i4;
if(a[4]==a[0]||a[4]==a[1]||a[4]==a[2]||a[4]==a[3]) continue;

for(int i5=1;i5<=9;i5++){
a[5]=i5;
if(a[5]==a[0]||a[5]==a[1]||a[5]==a[2]||a[5]==a[3]||a[5]==a[4]) continue;
for(int i6=1;i6<=9;i6++){
a[6]=i6;
if(a[6]==a[0]||a[6]==a[1]||a[6]==a[2]||a[6]==a[3]||a[6]==a[4]||a[6]==a[5]) continue;

for(int i7=1;i7<=9;i7++){
a[7]=i7;
if(a[7]==a[0]||a[7]==a[1]||a[7]==a[2]||a[7]==a[3]||a[7]==a[4]||a[7]==a[5]||a[7]==a[6]) continue;

for(int i8=1;i8<=9;i8++){
a[8]=i8;
if(a[8]==a[0]||a[8]==a[1]||a[8]==a[2]||a[8]==a[3]||a[8]==a[4]||a[8]==a[5]||a[8]==a[6]||a[8]==a[7]) continue;



int x=a[0]*100+a[1]*10+a[2];
int y=a[3]*100+a[4]*10+a[5];
int z=a[6]*100+a[7]*10+a[8];
if((y==2*x)&&(z==3*x)){
count++;

System.out.print(x+":"+y+":"+z+"   ");

}

}}}}}}}}}
System.out.println("符合条件的有"+count+"组");


}}

Answer 5

public static void main(String[] args) {
 
 int n = 330;
 int b = 102;
 
 StringBuffer sbu; p:
 for (int i = b; i < n; i++) {

    if((i/10)%10==0||i%10==0){
     continue;
    }
    sbu = new StringBuffer();
    sbu.append(i);
    sbu.append(i*2);
    sbu.append(i*3);
    
    String temp = sbu.toString();
    
    for (int j = 0; j <temp.length(); j++) {
int fristIndex  = temp.indexOf(temp.charAt(j));
int lasttIndex  = temp.lastIndexOf(temp.charAt(j));

if(fristIndex!=j||lasttIndex!=j){
continue p;
}
}
    System.out.println(i+","+i*2+","+i*3);
}
}

Answer 6

就是，我怎么没想到利用set集合的元素是不重复的这一点呢？非常感谢！

Answer 7

我……唉！真是拿自己没办法！兄弟，你真厉害！我们都没发现，而你发现了这个BUG……，我们都大意了。

Answer 8

public void printGroupMeetConditions(int[] array, int start, int end) {
if (start >= end) {
printFindIt(array);
return;
}
for (int i = start; i <= end; i++) {
swap(i, start, array);
printGroupMeetConditions(array, start + 1, end);
swap(i, start, array);
}
} /**
 * Question: Combine 1 ~~ 9, nine digit numbers into three 3 bits numbers,
 * number two have two times value of number one and number three three
 * times of number one. for instance: 192,384,576
 * 
 * @param args
 */ public void optimzedGroupMeetingCondigtions() {
int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
for (int i = 0; i < 3; i++) {
swap(i, 0, array);
printGroupMeetConditions(array, 1, 8);
swap(i, 0, array);
}
} private void printFindIt(int[] array) {
int number1 = getNumber(array, 0);
int number2 = getNumber(array, 3);
int number3 = getNumber(array, 6);
if ((number2 == number1 * 2) && (number3 == number1 * 3)) {
System.out.println(number1 + " , " + number2 + " , " + number3);
}
} private int getNumber(int[] array, int i) {
int number = array[i] * 100 + array[i + 1] * 10 + array[i + 2];
return number;
} private void swap(int i, int j, int[] array) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
} public static void main(String[] args) {
doFind();
doFind2();
} private static void doFind() {
long startTime = System.nanoTime();
int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
CombinationTests ct = new CombinationTests();
ct.printGroupMeetConditions(array, 0, 8);
long endTime = System.nanoTime();
System.out.println("Time speed: " + (endTime - startTime));
} private static void doFind2() {
long startTime = System.nanoTime();
CombinationTests ct = new CombinationTests();
ct.optimzedGroupMeetingCondigtions();
long endTime = System.nanoTime();
System.out.println("Time speed: " + (endTime - startTime));
}

Answer 9

经过和各位讨论后，现在贴一个目前较好的答案，大家参考：public class Group { /**
 * @param args
 */
public static void main(String[] args) {
find();
}

public static void find() {
int a = 0;
int b = 0;
int c = 0;
int count = 0;
for(int i=123;i<=329;i++) {
a = i;
b = i*2;
c = i*3;
if(check(a+""+b+""+c)) {
count++;
System.out.println(a+" "+b+" "+c);
}
}
System.out.println("符合条件的有"+count+"组");
}
/**
 * 去掉字符串中重复的字符，得到一个新字符串，和原字符串比较长度，以此检查是否有重复字符。
 * @param str
 * @return
 */
public static boolean check(String str) {
char[] chars = str.toCharArray();
String afterCheck = "";
for(int i=0;i<chars.length;i++) {
if(chars[i]=='0') {
return false;
} else if(afterCheck.indexOf(chars[i])==-1) {
afterCheck += chars[i]; 
}
}
return str.length()>afterCheck.length()?false:true;
}
}程序运行结果：
192 384 576
219 438 657
273 546 819
327 654 981
符合条件的有4组

Answer 10

 = = 。。没有考虑到0。。
重新贴：public static void main(String[] args) {
        
        int n = 330;
        int b = 102;
        
        StringBuffer   sbu = new StringBuffer();   p:
        for (int i = b; i < n; i++) {
           
           if((i/10)%10==0||i%10==0){
               continue;
           }
         
           sbu.append(i);
           sbu.append(i*2);
           sbu.append(i*3);
           
           String temp = sbu.toString();
           
           for (int j = 0; j <temp.length(); j++) {
               int fristIndex  = temp.indexOf(temp.charAt(j));
               int lasttIndex  = temp.lastIndexOf(temp.charAt(j));
               
               if(fristIndex!=j||lasttIndex!=j||temp.charAt(j)=='0'){
                sbu.delete(0,sbu.length());
                   continue p;
               }
           }
           sbu.delete(0,sbu.length());
           System.out.println(i+","+i*2+","+i*3);
       }
   }

Answer 11

public class Find_num 
{
public boolean compare_digit(int digit_1,int digit_2)  //比较两个数是否有重叠的部分以及 自身是否出现重复的数字
{
char [] digit_check1=Integer.toString(digit_1).toCharArray();
char [] digit_check2=Integer.toString(digit_2).toCharArray();
// int i,j;
for(int i=0;i<digit_check1.length;i++)  //判断第一个数字自身是否有重复的数字
{
for(int j=i+1;j<digit_check1.length;j++)
{
if(digit_check1[i]==digit_check1[j])
{
return false;
}
}
}
for(int i=0;i<digit_check2.length;i++)  //判断第二个数字自身是否有重复的数字
{
for(int j=i+1;j<digit_check2.length;j++)
{
if(digit_check2[i]==digit_check2[j])
{
return false;
}
}
}
for(int i=0;i<digit_check1.length;i++)   //判断两个数字之间是否有重复的数字
{
for(int j=0;j<digit_check2.length;j++)
{
if(digit_check1[i]==digit_check2[j])
{
return false;
}
}
}
return true;
}
public boolean check(int digit_1,int digit_2,int digit_3)
{
char [] digit_check1=Integer.toString(digit_1).toCharArray(); //将数字1转化为字符数组形式
char [] digit_check2=Integer.toString(digit_2).toCharArray();
char [] digit_check3=Integer.toString(digit_3).toCharArray();
boolean aftercheck_1=false;  //判断三个数字是否有重叠的数字后的结果
boolean aftercheck_2=false;
boolean aftercheck_3=false;
for(int i=0;i<digit_check1.length;i++)  //检查是否含有0
{
if((digit_check1[i]=='0')||(digit_check2[i]=='0')||(digit_check3[i]=='0'))
{
return false;
}
}
aftercheck_1=compare_digit(digit_1,digit_2);  //判断数字1与数字2是否有重叠
aftercheck_2=compare_digit(digit_1,digit_3);  //判断数字1与数字3是否有重叠
aftercheck_3=compare_digit(digit_2,digit_3);  //判断数字3与数字2是否有重叠
if(aftercheck_1==true&&aftercheck_2==true&&aftercheck_3==true)  //三个数字都没有重叠
{
return true;
}
return false;
}
public void find()
{
int digit_1;  //数字1
int digit_2;  //数字2
int digit_3;  //数字3
int count=0;
boolean result;
for(digit_1=123;digit_1<=329;digit_1++)  //数字1的范围
{

digit_2=2*digit_1;
digit_3=3*digit_1;
result=false;
result=check(digit_1,digit_2,digit_3);  //检查三个数字是否符合标准
if(result==true)
{
System.out.println(digit_1+" "+digit_2+" "+digit_3);
count++;
}
}
System.out.println("总共有 "+count+"对");
}
public static void main(String [] args)
{
Find_num Finding=new Find_num();  //
Finding.find();

}
}

Answer 12

复杂可能在于组合算法吧~， 其他的就很简单了，，我里面贴出代码了，包括运行时间，比较了一下，时间还可以public void printGroupMeetConditions(int[] array, int start, int end) {
        if (start >= end) {
            printFindIt(array);
            return;
        }
        for (int i = start; i <= end; i++) {
            swap(i, start, array);
            printGroupMeetConditions(array, start + 1, end);
            swap(i, start, array);
        }
    }上面这段就是组合算法，每找到一个串，就计算是否符合条件

Answer 13

无论是在循环体内判断，或者是先取出数字再判断，时间复杂度均为O(N^2)
其实这是一道数学题，不需要穷举。
我的分析如下
设最小的三位数为n,a = n/3.
那么a的每一位加起来的和总是10，有1位是3的倍数。且a的末尾不能为0和5.
由题意可知n在区间[123,329]，那么a就在区间[46,109]内。（4+6=10，1+0+9=10）
但是12x * 2 = 2xx
13x * 3 = 3xx 或40x 或 41x
14x * 3 = 4xx
15(1-3) * 3 = 45x均不符合题意
所以最小值应为154,154/3 = 51,由于55末尾是5，排除
所以a的最小值为64。根据分析，代码如下public class Test { public static void main(String[] args) {
find();
} static void find(){
int count = 0;
for(int i = 64;i <= 109;i += 9){
if(i % 5  == 0 || check(i) == false){
continue;
}
else{
count++;
System.out.println(i * 3 + " " + i * 6 + " " + i * 9);
}
}
System.out.println("count = " + count);
}

static boolean check(int n){
while(n != 0){
if((n % 10) % 3 == 0){
return true;
}
n /= 10;
}
return false;
}
}

Answer 14

不错，还真没有想到零啊   xtj332强啊！！

Answer 15

就是仔细点  就发现了这个BUG。。我有时候发编程的时候也是这样，马虎一点，照搬天找不到错误的原因咱们都要小心