求解一道JavaSE面试题!

Question

一个数组,内1,2,3,4,5,6,这六个数,打印出它所有可能的组合,按升序排列;要求4不能在第三位,3和5不能相连.求解!哪位大侠帮帮忙......

Answer 1

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Test { /**
 * @param args
 */
static List<Integer> L= new ArrayList<Integer>();

//生成k到m的所有排列组合
//int a[]={1,2,3} => {123,132,213,231,321,312}
static void permutation(int ary[],int k,int m){
int i;
if(k==m){
String s="";
for(i=0;i<=m;i++)
s=s+ary[i];
L.add(Integer.parseInt(s));
}else{
for(i=k;i<=m;i++){
int temp=ary[k];
ary[k]=ary[i];
ary[i]=temp;

permutation(ary,k+1,m);

temp=ary[k];
ary[k]=ary[i];
ary[i]=temp;
}
}
}
public static void main(String[] args) {
/* 一个数组,内1,2,3,4,5,6,这六个数,
打印出它所有可能的组合,
按升序排列;要求4不能在第三位,3和5不能相连.
*/ 
int ary[]={1,2,3,4,5,6};
permutation(ary,0,5);//生成1...6的所有排列

//1,去掉3和5相连的数.2,去掉第三位是4的数 
for(int i =0;i<L.size();i++){
String tmp=L.get(i).toString();
if(tmp.indexOf("53")!=-1||tmp.indexOf("35")!=-1||tmp.charAt(2)=='4'){
System.out.println(L.get(i)+"去掉");
}else{
System.out.println(L.get(i));
}
}

}}

Answer 2

没用递归，比较笨的方法，容易理解：
import java.util.*;public class Hello {    public ArrayList<String> paiLie(int[] array) {
        ArrayList<String> al = new ArrayList<String>();
        if (array.length != 6) {        } else {
            for (int i1 = 0; i1 < 6; i1++) {
                for (int i2 = 0; i2 < 6; i2++) {
                    if (i2 == i1)
                        continue;
                    else
                        for (int i3 = 0; i3 < 6; i3++) {
                            if (i3 == i1 || i3 == i2)
                                continue;
                            else
                                for (int i4 = 0; i4 < 6; i4++) {
                                    if (i4 == i1 || i4 == i2 || i4 == i3)
                                        continue;
                                    else
                                        for (int i5 = 0; i5 < 6; i5++) {
                                            if (i5 == i4 || i5 == i1
                                                    || i5 == i2 || i5 == i3)
                                                continue;
                                            else
                                                for (int i6 = 0; i6 < 6; i6++) {
                                                    if (i6 == i4 || i6 == i1
                                                            || i6 == i2
                                                            || i6 == i3
                                                            || i6 == i5)
                                                        continue;
                                                    else
                                                        al.add("" + array[i1]
                                                                + array[i2]
                                                                + array[i3]
                                                                + array[i4]
                                                                + array[i5]
                                                                + array[i6]);                                                }
                                        }
                                }
                        }
                }
            }
        }
        return al;
    }    public static void main(String[] args) {
        int[] array = { 1, 2, 3, 4, 5, 6 };
        int count=0;
        Hello h = new Hello();
        ArrayList<String> a = h.paiLie(array);
        for (int x = 0; x < a.size(); x++) {
            if (a.get(x).indexOf("35") >= 0 || a.get(x).indexOf("53") >= 0
                    || a.get(x).substring(2, 3).equals("4")) {
            } else {
                System.out.println(a.get(x));
                count ++;
            }
        }
        System.out.println(count);
    }
}

Answer 3

import java.util.Set;
import java.util.TreeSet;public class DanChi {
   private int size;
   private char danchi[];
   private int count=0;
   private Set <Integer> s;
   public void setDanChi(String danchi){
   this.danchi=danchi.toCharArray();
   size=danchi.length();
   s=new TreeSet<Integer>();
   }
   public void display(){
   for(Integer a:s){
   System.out.println(a);
   }
   System.out.println(count);
   }
   public void argument(int newSize){
   if(newSize==1){
   return ;
   }
   for(int i=0;i<newSize;i++){
   argument(newSize-1);
   if(newSize==2){
   if(new String(danchi).charAt(2)!='4'&&!new String(danchi).matches("\\d*35\\d*|\\d*53\\d*")){
   s.add(new Integer(new String(this.danchi)));
   this.count++;
   }
   }
   int poin=size-newSize;
   char c=danchi[poin];
   int j;
   for( j=poin+1;j<size;j++){
   danchi[j-1]=danchi[j];
   }
   danchi[j-1]=c;
   }   }
   public static void main(String args[]){
   DanChi dc=new DanChi();
   dc.setDanChi("123456");
   dc.argument(dc.size);
   dc.display();
   }
}

Answer 4

这个问题我一直想学习啊，但是我可以给点建议
1.先用递归搜索出所有的组合排列情况(这也是我不会使用的地方，呵呵)，并放入到一个list<String>中
2.然后再对这个list遍历，首先，如果某个数第三位是4，就删除，否则判断字符3的位置和字符5的位置是否相差为1或者-1。如果是的话还是删除。
3.剩下的这些就是符合条件的所有组合了，在对他们进行排序。
呵呵，这是我的想法。由于不会第一步的递归，所以也就没有代码了

Answer 5

可以不用递归的。for(int i = 123456 ; i <= 654321 ; i++){
     String temp = String.valueOf(i);
     Set<Character> set = new HashSet<Character>();
     for(int j = 0 ; j < 6; j++){
set.add(temp.charAt(j));
}
     if(set.size() < 6){
         continue;
}
     else if(set.contains('0') || set.contains('7') || set.contains('8') || set.contains('9')){
continue;
}
     else{
           if(temp.charAt(2) == '4'){
               continue;
               }
           else{
                if(temp.matches(".*53.*") ||temp.matches(".*35.*") ){
                       continue;
                   }
                else{
                       System.out.println(temp);
                    }
             }
}
}

Answer 6

安27楼的意思，是不是26楼只要把for()中的int i=123456 改成int i=1就可以了哦

Answer 7

import java.util.*;  
public class Callsort {  
static int count=0;
    public static void main(String[] args) throws Exception{  
        String[] array = new String[]{"1","2","3","4","5","6"};  
        listAll(Arrays.asList(array),"",array.length);           System.out.println("结果数:"+count);
    }
    public static void listAll(List<String> candidate, String prefix,int length){  
        if(prefix.length()==length&&
         prefix.lastIndexOf("35")==-1&&
         prefix.lastIndexOf("53")==-1) {
         System.out.println(prefix);
            count++;
        }
        for( int i=0; i < candidate.size(); i++ ) {  
            List<String> temp = new ArrayList<String>(candidate);  
            listAll(temp, prefix+temp.remove(i),length);  
        }  
    }  
}
太容易了,上次有这个人问过这些问题,

Answer 8

import java.util.*;  
import datastruct.treenode.bintree.treestruct;
public class Callsort {  
static int count=0;
static TreeSet<Integer> t=new TreeSet<Integer>();
    public static void main(String[] args) throws Exception{  
        String[] array = new String[]{"1","2","3","4","5","6"};  
        listAll(Arrays.asList(array),"",array.length);  
         Iterator it=t.iterator();
         while (it.hasNext()) {
          System.out.println(it.next());
}
         System.out.println("结果数:"+count);
    }
    public static void listAll(List<String> candidate, String prefix,int length){  
        if(prefix.length()==length&&
         prefix.lastIndexOf("35")==-1&&
         prefix.lastIndexOf("53")==-1) {
         t.add(Integer.parseInt(prefix));
            count++;
        }
        for( int i=0; i < candidate.size(); i++ ) {  
            List<String> temp = new ArrayList<String>(candidate);  
            listAll(temp, prefix+temp.remove(i),length);  
        }  
    }  
}
这个实现升序的

Answer 9

上面那句import datastruct.treenode.bintree.treestruct;
应该删掉

Answer 10

递归求解
public class Assemble{
    private int count = 1;
    public void getAssemble(String result, Vector<Character> source){
        if((result.length() == 3) && (result.charAt(2) == '4'))
            return;
        if(result.endsWith("35") || result.endsWith("53"))
            return;
        if(result.length() == 6){
            System.out.print("count is "+count++);
            System.out.println(" result is "+result);
            return;
        }
        for(int i = 0; i < source.size(); i++){
            Vector<Character> t = (Vector<Character>)source.clone();
            t.remove(i);
            getAssemble(result + source.get(i), t);
        }
    }
    private static int getCurrentMilliSec()
    {
        Calendar calendar = Calendar.getInstance();
        return(calendar.get(Calendar.MILLISECOND));
    }
    public static void main(String[] args){
        int start = getCurrentMilliSec();
        Assemble as = new Assemble();
        Vector<Character> v = new Vector<Character>();
        v.add('1');
        v.add('2');
        v.add('3');
        v.add('4');
        v.add('5');
        v.add('6');
        as.getAssemble("", v);
        int finish = getCurrentMilliSec();
        System.out.println("Done in "+(finish-start)+"ms.");
    }
}
实测，结果为
....
count is 396 result is 652431
Done in 78ms.