求解一道JavaSE面试题! 一个数组,内1,2,3,4,5,6,这六个数,打印出它所有可能的组合,按升序排列;要求4不能在第三位,3和5不能相连.求解!哪位大侠帮帮忙...... 解决方案 » 免费领取超大流量手机卡,每月29元包185G流量+100分钟通话, 中国电信官方发货 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)); } } }} 没用递归,比较笨的方法,容易理解: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); }} 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(); }} 这个问题我一直想学习啊,但是我可以给点建议1.先用递归搜索出所有的组合排列情况(这也是我不会使用的地方,呵呵),并放入到一个list<String>中2.然后再对这个list遍历,首先,如果某个数第三位是4,就删除,否则判断字符3的位置和字符5的位置是否相差为1或者-1。如果是的话还是删除。3.剩下的这些就是符合条件的所有组合了,在对他们进行排序。呵呵,这是我的想法。由于不会第一步的递归,所以也就没有代码了 可以不用递归的。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); } } }} 安27楼的意思,是不是26楼只要把for()中的int i=123456 改成int i=1就可以了哦 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); } } }太容易了,上次有这个人问过这些问题, 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); } } }这个实现升序的 上面那句import datastruct.treenode.bintree.treestruct;应该删掉 递归求解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 652431Done in 78ms. wireshark 工具使用 多线程运行问题求教! 为什么paint方法调用了n次,只执行了一次? 急求各个进制之间相互转换的教程 求助,这个问题的更好的算法(空间时间复杂度尽量低). 这里有一个程序,帮忙看看 问一个简单的问题 怎样从数据库中取出数据添到ComboBox中去? 这里还有 99分,,大家快来 ERP和CRM的区别,有谁知道? debug时的expression窗口有用吗?我觉得没有variable窗口有用。 学习方法请教
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));
}
}
}}
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);
}
}
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();
}
}
1.先用递归搜索出所有的组合排列情况(这也是我不会使用的地方,呵呵),并放入到一个list<String>中
2.然后再对这个list遍历,首先,如果某个数第三位是4,就删除,否则判断字符3的位置和字符5的位置是否相差为1或者-1。如果是的话还是删除。
3.剩下的这些就是符合条件的所有组合了,在对他们进行排序。
呵呵,这是我的想法。由于不会第一步的递归,所以也就没有代码了
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);
}
}
}
}
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);
}
}
}
太容易了,上次有这个人问过这些问题,
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);
}
}
}
这个实现升序的
应该删掉
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.