面试题

Question

AB字符有以下组合 AB, BA
ABC字符有以下组合 ABC, ACB, BAC, BCA, CAB,CBA
输出N字符的组合(说出思路,并有程序实现)

Answer 1

public void sort(String str,String end){
if(end.length()==1){
System.out.println(str+end);
}
for(int i=0;i<end.length();i++){
sort(str+end.substring(i,i+1),end.substring(0,i)+end.substring(i+1));
}

Answer 2

public void sort(String str,String end){ 
if(end.length()==1){ 
System.out.println(str+end); 
} 
else{
for(int i=0;i <end.length();i++){ 
sort(str+end.substring(i,i+1),end.substring(0,i)+end.substring(i+1)); 
}
}
忘了个else- -

Answer 3

定义C（M,N）
     其中N=M-1;
     共有M个元素；
     IF (N=1OR M=1)  C(M,N)=M;
     ELSE 
      C(M,N)=C(M-1,1)+C(M-2,1)

Answer 4

好像不大明白题意 楼上的substring方法也不懂

Answer 5

可以用图的深度优先遍历算法，不过对这道题来说不用也行，下面是一种实现
public class Permutation { private int n = 0; private String result = ""; public Permutation(int n) {
this.n = n;
}
public static void main(String[] s) {
new Permutation(3).printPermutation();
} public void printPermutation() {
if (result.length() == n) {
System.out.println(result);
} else {
for (int i = 65; i < 65 + n; i++) {
if (result.indexOf((char) i) < 0) {
result = result + (char) i;
printPermutation();
result = result.substring(0, result.length() - 1);
}
}
}
}
}

Answer 6

给你个算法， 以前在网上找到的， 很巧妙， 程序实现也很简单：
2。算法来源与互联网组合算法  
  本程序的思路是开一个数组，其下标表示1到m个数，数组元素的值为1表示其下标  
  代表的数被选中，为0则没选中。    
  首先初始化，将数组前n个元素置1，表示第一个组合为前n个数。    
  然后从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为  
  “01”组合，同时将其左边的所有“1”全部移动到数组的最左端。    
  当第一个“1”移动到数组的m-n的位置，即n个“1”全部移动到最右端时，就得  
  到了最后一个组合。    
  例如求5中选3的组合：    
  1   1   1   0   0   //1,2,3    
  1   1   0   1   0   //1,2,4    
  1   0   1   1   0   //1,3,4    
  0   1   1   1   0   //2,3,4    
  1   1   0   0   1   //1,2,5    
  1   0   1   0   1   //1,3,5    
  0   1   1   0   1   //2,3,5    
  1   0   0   1   1   //1,4,5    
  0   1   0   1   1   //2,4,5    
  0   0   1   1   1   //3,4,5   想看C++的实现可以访问： http://www.cppblog.com/biao/archive/2008/03/22/45091.aspx