java的一道笔试题

Question

写一个函数，要求输入abc,则输出abc的所有排列：abc,acb,bca,bac,cab,cba.（写出最终代码）

Answer 1

动态的话,估计也不是那么好做,如果做死了只有ABC,那就是三层循环问题了

Answer 2

public static void main(String[] args) {
String source="";
String[] array1={"a","b","c"};
List<String> results=new ArrayList<String>();
for (int i = 0; i < array1.length; i++) {
for (int j = 0; j < array1.length-1; j++) {
if(array1[j]==array1[j+1]){
continue;
}
String a=new String(array1[j]);
array1[j]=array1[j+1];
array1[j+1]=a;
for (int k = 0; k < array1.length; k++) {
source+=array1[k];
}
boolean isHave=false;
for (int m = 0; m < results.size(); m++) {
if(results.get(m).equals(source)){
isHave=true;
break;
}
}
if(!isHave){
results.add(source);
}
source="";
}
}
for (int i = 0; i < results.size(); i++) {
System.out.println(results.get(i));
}
}
效率有些低

Answer 3

import java.io.UnsupportedEncodingException;
import java.util.LinkedHashSet;
import java.util.Set;public class Test {
public static void main(String[] args) throws UnsupportedEncodingException {
Set<String> result = perm("abac");
for (String s : result)
System.out.println(s);
} public static Set<String> perm(String str) {
Set<String> result = new LinkedHashSet<String>();
perm(new StringBuilder(str), new StringBuilder(), result);
return result;
} public static void perm(StringBuilder str, StringBuilder prefix,
Set<String> result) {
int length = str.length();
int prefixLength = prefix.length();
if (length == 0) {
result.add(prefix.toString());
return;
} for (int i = 0; i < length; i++) {
char ch = str.charAt(i);
perm(str.deleteCharAt(i), prefix.append(ch), result);
str.insert(i, ch);
prefix.deleteCharAt(prefixLength);
}
}
}

Answer 4

五十上面的那个throws吧，万用测试类，忘记把这个删了

Answer 5

public static void addIntoList(List charlist,StringBuffer sb,List resultList){
if(charlist.size()==1){
sb.append(charlist.get(0));
resultList.add(sb.toString());
sb.deleteCharAt(sb.length()-1);
}else{
int size = charlist.size();
for(int j=0;j<size;j++){
Object removeChar = charlist.get(j);
sb.append(removeChar);
int index = sb.length();
charlist.remove(j);
addIntoList(charlist,sb,resultList);
charlist.add(j, removeChar);
sb.deleteCharAt(index-1);
}
}
} public static void main(String[] args){
List<String> resultList = new ArrayList<String>();
// Scanner scan = new Scanner(System.in);
// String str = scan.next();
String str = "abc";
char[] chars = str.toCharArray();
for(int i=0;i<chars.length;i++){
List<Character> charlist = new ArrayList<Character>();
for(Character c:chars){
charlist.add(c);
}
StringBuffer sb = new StringBuffer();
addIntoList(charlist,sb,resultList);
}
System.out.println(resultList.toString());
}

Answer 6

ublic static void addIntoList(List charlist,StringBuffer sb,List resultList){
        if(charlist.size()==1){
            sb.append(charlist.get(0));
            resultList.add(sb.toString());
            sb.deleteCharAt(sb.length()-1);
        }else{
            int size = charlist.size();
            for(int j=0;j<size;j++){
                Object removeChar = charlist.get(j);
                sb.append(removeChar);
                int index = sb.length();
                charlist.remove(j);
                addIntoList(charlist,sb,resultList);
                charlist.add(j, removeChar);
                sb.deleteCharAt(index-1);
            }

Answer 7

用了递归做的。
不是abc，而是别的字母也没问题。不过如果输入的字母当中有重复的
resultList就要考虑换成HashSet之类的了。

Answer 8

public static List<String> func(String  str){
List<String> result=new ArrayList<String>();
if(str != null && str.length()>0){
if(str.length()==1){
result.add(str);
}
else{
char c=str.charAt(0);
List<String> list=func(str.substring(1));
for(int i=0;i<list.size();i++){
String tmp=list.get(i);
for(int j=0;j<=tmp.length();j++){
result.add(tmp.substring(0, j)+c+tmp.substring(j));
}
}
        }
  }
return result;
 }
   
public static void main(String[] args) {
List<String> list=Test.func("abc1");
     for(String str : list){
            System.out.println(str);
        }
}

Answer 9

public static List<String> func(String  str){
List<String> result=new ArrayList<String>();
String elment ="";
if(str != null && str.length()>0){
if(str.length()==1){
result.add(str);
}
else{
char c=str.charAt(0);
List<String> list=func(str.substring(1));
for(int i=0;i<list.size();i++){
String tmp=list.get(i);
for(int j=0;j<=tmp.length();j++){
elment = tmp.substring(0, j)+c+tmp.substring(j);
if(!result.contains(elment)){
result.add(elment);
}
}
}
        }
  }
return result;
 }
   
public static void main(String[] args) {
List<String> list=Test.func("abc");
     for(String str : list){
            System.out.println(str);
        }
}

Answer 10

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Test {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String str = scan.next(); List<String> result = perm(str);
for (String s : result)
System.out.println(s);
} public static List<String> perm(String str) {
List<String> result = new ArrayList<String>();
perm(new StringBuilder(str), new StringBuilder(), result);
return result;
} public static void perm(StringBuilder str, StringBuilder prefix,
List<String> result) {
int length = str.length();
int prefixLength = prefix.length();
if (length == 0) {
result.add(prefix.toString());
return;
}
char[] arr = new char[length];
for (int i = 0; i < length; i++) {
char ch = str.charAt(i);
boolean repeat = false;
for (int j = 0;; j++) {
if (arr[j] == 0) {
arr[j] = ch;
break;
}
if (arr[j] == ch) {
repeat = true;
break;
}
} if (!repeat) {
perm(str.deleteCharAt(i), prefix.append(ch), result);
str.insert(i, ch);
prefix.deleteCharAt(prefixLength);
}
}
}
}改了下算法，对于重复处理不适用Set了，而在递归的循环里利用数组判断，提高效率

Answer 11

public static List<String> func(String  str){
        List<String> result=new ArrayList<String>();
        if(str != null && str.length()>0){
            if(str.length()==1){
                result.add(str);
            }
            else{
                char c=str.charAt(0);
                List<String> list=func(str.substring(1));
                for(int i=0;i<list.size();i++){
                    String tmp=list.get(i);
                    for(int j=0;j<=tmp.length();j++){
                        result.add(tmp.substring(0, j)+c+tmp.substring(j));
                    }
                }
            }
         }
        return result;
     }
       
    public static void main(String[] args) {
        List<String> list=Test.func("abc1");
            for(String str : list){
                System.out.println(str);
            }
    }

Answer 12

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;public class PermutationTest { public static void getOne(char[] original,char[] dest,Set<String> resultSet)
{
int destLen = dest.length;
for(int len = original.length,i = 0; i < len; i++)
{
char[] newDest = new char[destLen + 1];
System.arraycopy(dest, 0, newDest, 0, destLen);
newDest[destLen] = original[i];
if(len == 1) {
resultSet.add(String.valueOf(newDest));
System.out.println(resultSet.size());
}
else {
char[] newOriginal = removeElement(Arrays.copyOf(original, len), i);
getOne(newOriginal,newDest,resultSet);
}
}
}

public static void main(String[] args) {
long start = System.currentTimeMillis();
char[] dest = {};
String temp = "abcdefghi"; // 再加一个会抛异常
Set<String> resultSet = new HashSet<String>();
getOne(temp.toCharArray(), dest, resultSet);
System.out.println(resultSet.size());
long end = System.currentTimeMillis();
System.out.println(end - start);
}

public static char[] removeElement(char[] target,int index)
{
int len = target.length;
char[] temp = new char[len - 1];
for(int i=0,j=0;i<len;i++)
{
if(index == i)
continue;
temp[j++] = target[i];
}
return temp;
}
}

Answer 13

把set改为list效率更高些：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class PermutationTest { public static void getOne(char[] original,char[] dest,List<String> resultList)
{
int destLen = dest.length;
for(int len = original.length,i = 0; i < len; i++)
{
char[] newDest = new char[destLen + 1];
System.arraycopy(dest, 0, newDest, 0, destLen);
newDest[destLen] = original[i];
if(len == 1) {
resultList.add(String.valueOf(newDest));
}
else {
char[] newOriginal = removeElement(Arrays.copyOf(original, len), i);
getOne(newOriginal,newDest,resultList);
}
}
}

public static void main(String[] args) {
long start = System.currentTimeMillis();
char[] dest = {};
String temp = "abcdefghij";
List<String> resultList = new ArrayList<String>();
getOne(temp.toCharArray(), dest, resultList);
System.out.println(resultList.size());
long end = System.currentTimeMillis();
System.out.println(end - start);
}

public static char[] removeElement(char[] target,int index)
{
int len = target.length;
char[] temp = new char[len - 1];
for(int i=0,j=0;i<len;i++)
{
if(index == i)
continue;
temp[j++] = target[i];
}
return temp;
}
}