随笔-42  评论-578  文章-1  trackbacks-0
最新彩票网站排名我的舍友晓杰(C++高手)今天去了一家IT公司笔面试,其中就有这么一道题。

题目大意:输入一个字符串,显示出字符串的所有排列。例如:输入"abc",就得输出"abc"、"acb"、"bac"、"bca"、"cab"、"cba" 所有可能的序列。

颇有意义的一道题,我决定用Java语言来写一写。代码如下:
import java.util.Arrays;
public class CharList {

    
//遍历所有可能的排列结果
    public static void traversal(char[] chss, int index){
        
//for循环,从index位置开始向前(向右), index位置的数与i位置的数互换
        for(int i = index; i < chss.length; i ++) {
            
char[] chs = Arrays.copyOf(chss, chss.length);    //Copy出新数组(为了修改其值时互不影响)
            char temp = chs[index];
            chs[index] 
= chs[i];
            chs[i] 
= temp;
            
if(index == chs.length-1) {    //到了字符串末, 输出结果
                System.out.println(new String(chs));
                
break;    //跟出此次循环, 此traversal方法执行完毕,跳回上一级循环(在上一个方法体中)
            }
            traversal(chs, index
+1);        //递归
        }
    }

    
//Test
    public static void main(String[] args) {
        String str 
= "abcd";
        
char[] chs = str.toCharArray();    //转成字符数组
        traversal(chs, 0);
    }

}

程序执行,输出结果为:
abcd
abdc
acbd
acdb
adcb
adbc
bacd
badc
bcad
bcda
bdca
bdac
cbad
cbda
cabd
cadb
cdab
cdba
dbca
dbac
dcba
dcab
dacb
dabc


本文原创,转载请注明出处,谢谢!http://yaqisp.com/rongxh7(心梦帆影JavaEE技术博客)
    

posted on 2010-03-23 02:04 心梦帆影 阅读(3059) 评论(8)  编辑  收藏 所属分类: JavaSE

评论:
# re: 舍友笔试中的一道算法题(我的解法) 2010-03-23 10:50 | ms
private static List<String> overall(String str){
List<String> strs = new ArrayList<String>();
for(int i=0;i<str.length();i++){
List<String> subStrings = overall(str.substring(0,i)+str.substring(i+1));
for(String s : subStrings){
strs.add(str.substring(i,i+1)+s);
}
}
if(str.length()==1){
strs.add(str);
}
return strs;
}  回复  更多评论
  
# re: 舍友笔试中的一道算法题(我的解法) 2010-03-23 10:56 | Grissom
if the input string contains the redundant char, for example: "aaaa"?
  回复  更多评论
  
# re: 舍友笔试中的一道算法题(我的解法) 2010-03-23 16:01 | Lancelot
import java.util.ArrayList;
import java.util.List;

import org.apache.commons.lang.ArrayUtils;
import org.apache.commons.lang.time.StopWatch;

/*
* @(#)PermutationAndCombination.java 2010-3-23
*
* @COPYRIGHT@
*/

/**
* <p>
* 排列组合
* </p>
*
* @version 1.0
* @author Lancelot
*
*/
public class PermutationAndCombination {

private char[] resource = new char[0];

private List result海南快三app—官方网址22270.COMuffer = new ArrayList();

public PermutationAndCombination() {}

public PermutationAndCombination(char[] resource) {

this.resource = resource;
}

public PermutationAndCombination(String resource) {

this.resource = resource.toCharArray();
}

public List process() {

for(int i = 0, num = resource.length; i < num; i++) {

char[] part = ArrayUtils.subarray(resource, i, i + 1);
char[] tmpResource = ArrayUtils.remove(resource, i);
permutation(tmpResource, part);
}

return result海南快三app—官方网址22270.COMuffer;
}

private void permutation(char[] resource, char[] prefix) {

int num = resource.length;
if( 1 == num ) {

char[] result = ArrayUtils.addAll(prefix, resource);

System.out.println(String.valueOf(result));

//下面的代码可以解决重复结果的问题——比如传入了aaaa/ aaba这样的字符串,但效率会稍差。
/*String resultString = String.valueOf(result);
if( !result海南快三app—官方网址22270.COMuffer.contains(resultString) ) {
result海南快三app—官方网址22270.COMuffer.add(resultString);
}*/
} else {

for(int i = 0; i < num; i++) {

char[] result = ArrayUtils.add(prefix, resource[i]);

permutation(ArrayUtils.remove(resource, i), result);
}
}
}

public static void main(String[] args) {

StopWatch clock = new StopWatch();
clock.start();
System.out.println(new PermutationAndCombination("abcdefge").process());
clock.stop();
System.out.println("clock.getTime() => " + clock.getTime());
}
}

这段代码可在1.3/ 1.4的环境下运行,而且在效率与博主的代码相差无几的情况下,可读性要更好。
  回复  更多评论
  
# re: 舍友笔试中的一道算法题(我的解法) 2010-03-23 16:45 | wangkaiyong
太 厉害了,看了半天才看懂,楼主对递归很熟,佩服佩服,有空教教我  回复  更多评论
  
# re: 舍友笔试中的一道算法题(我的解法) 2010-03-23 21:36 | sunnycare
最新彩票网站排名你的算法前提是,字符串没有重复字符。  回复  更多评论
  
# re: 舍友笔试中的一道算法题(我的解法) 2010-03-24 16:21 | Gauss Reborn
我写了个更清晰的算法
只用了核心代码3部完成全排列递归
recurrence;
/*
最新彩票网站排名* :输入一个字符串,显示出字符串的所有排列。例如:输入"abc",就得输出"abc"、"acb"、"bac"、"bca"、"cab"、"cba" 所有可能的序列。
*
* */
public class QuanPaiLie {

public void swap(char[] array,int i,int j){
char temp = array[i];
array[i] = array[j];
array[j]=temp;
}

public void compute(char[] array, int pos){
if(pos == array.length){
for(char ch:array){
System.out.print(ch);
}
System.out.println();
}
for(int i=pos;i<array.length;i++){
swap(array, i, pos);
compute(array,pos+1);
swap(array, pos, i);
}

}


public static void main(String[] args) {
String input = "abc";
char[] c = input.toCharArray();
new QuanPaiLie().compute(c,0);
}

}
  回复  更多评论
  
# re: 舍友笔试中的一道算法题(我的解法) 2010-03-25 20:24 | Lancelot
@Gauss Reborn
你的代码,效率很差,而且与楼主的算法一样,能不能再提出其他的算法???  回复  更多评论
  
# re: 舍友笔试中的一道算法题(我的解法) 2010-03-29 13:51 | nswish
这类问题一般都是用递归来解
不知道有没有高手,可以使用非递归的方式求解问题  回复  更多评论
  

只有注册用户登录后才能发表评论。

网站导航: