面试一个编程题，没做出来帮我看看

public class Test {
private void queue(int[] sss, int[] ss1) {
if (sss.length > 1) {
int[] yyy = new int[sss.length - 1];
int[] yy1 = new int[ss1.length + 1];
for (int i = 0; i < sss.length; i++) {
int sum;
for (int j = 0; j < yyy.length; j++) {
if (j < i)
sum = j;
else
sum = j + 1;
yyy[j] = sss[sum];
}
for (int k = 0; k < ss1.length; k++) {
yy1[k] = ss1[k];
}
yy1[yy1.length - 1] = sss[i];
queue(yyy, yy1);
}
} else {
for (int s : ss1)
System.out.print(s + " ");
System.out.println(sss[0]);
}
} public void taxis(int[] sss) {
int[] ss1 = new int[0];
queue(sss, ss1);
} public static void main(String[] args) {
int[] sss = { 4, 5, 8, 9 };
Test test = new Test();
test.taxis(sss);
}
}4 5 8 9
4 5 9 8
4 8 5 9
4 8 9 5
4 9 5 8
4 9 8 5
5 4 8 9
5 4 9 8
5 8 4 9
5 8 9 4
5 9 4 8
5 9 8 4
8 4 5 9
8 4 9 5
8 5 4 9
8 5 9 4
8 9 4 5
8 9 5 4
9 4 5 8
9 4 8 5
9 5 4 8
9 5 8 4
9 8 4 5
9 8 5 4

用递归最好解决
或者用N（N=sss.length）重循环

void  Perm(int list[], int k, int m) {
int i;
   if (k == m)  {
      for (i = 0; i <= m; i++)
cout << a[i] << " ";
cout << endl;
   } else
for(i=k; i <= m; i++) {
          Swap(list[k], list[i]);
          Perm(list, k+1, m);
          Swap(list[k], list[i]);
      }
} void Swap(int  & a, int  &b) {
int t = a;
a = b;
b = t;
}

用c＋＋写的，刚学java，还不是很熟练

方法一
应用回溯法，每个数的取法都有N个方向（1——N），当取够N个数时，输出一个排列，然后退后一步，取前一个数的下一个方向（即前一个数+1），并且要保证所有数字不能重复。当前数字的所有方向都取完时，继续退一步，一直重复到第一个数为止方法二
应用剔除，列出所有的千位数，
1.剔出出现重复数字的数
2.剔出数字中出现不匹配4,5,9,8
最简单的办法是
System.out.println("4,5,9,8")
.....
写24个

/*
* 现在有int sss [] = {4,5,8,9}，写一段程序让程序输出sss这个数组的所有排序！
* 比如说4,5,8,9
* 4,5,9,8
* 4,9,5,8
* 4,9,8,5等等所有的排序种类，总共应该是24种,这个程序应该怎么编写？谢谢
*
*/
import java.util.ArrayList;
public class Order { /**
* 生成子序列
* 比如说a=”5“，b={(8,9),(9,8)}
* 返回的数据就是{(5,8,9),(5,9,8).......}
* 即是在b的每条记录中将a插进去
* @param a
* @param b
* @return
*/
public ArrayList<String> switchTwo(String a,ArrayList<String> b){
/*获取list的长度，后面list长度会改变，必须在前面记录下*/
int size=b.size();

/*将a插在前面*/
for(int i=0;i<size;i++){
b.add(a+","+b.get(i));
}

/*这一段代码惨不忍睹，作用将a插在中间，即是逗号后面
*
* 主要疑惑点在取得逗号的位置，我的做法是：
* 比如{5,8,9},第一个很好取，第二个则是获取该字符串的一个字串，让第二个逗号变成字串的第一个逗号
* 其实这可以写一个方法了
*
* 不知道各位还有没有其它好点方法，请多多指教
*/
for(int i=0;i<size;i++){
/*获取字符串*/
String temp=b.get(i);
/*用于记录子字符串*/
String templ=temp;
/*逗号在原字符串中的位置*/
int ipos=0;
while(templ.indexOf(",")!=-1){
ipos=ipos+templ.indexOf(",");
StringBuffer sb=new StringBuffer(temp);
/*插入语句*/
sb.insert(ipos+1, a+",");
b.add(sb.toString());
templ=new String(temp.substring(ipos+1));
/*位置的问题很烦人，建议看看API*/
ipos++;
}
}
/*将a插到后面*/
for(int i=0;i<size;i++){
b.add(b.get(i)+","+a);
}

/*移去处理的原始数据，就是传过来的list的数据*/
for(int i=0;i<size;i++){
b.remove(0);
}
return b;
}

/**
* 用的是递归方法，要取得{4,5,8,9}的排列，首先要取得{5,8,9}的排列
* @param a
* @return
*/
public ArrayList<String> getOrder(int[] a){
if(a.length==1){
ArrayList<String> list=new ArrayList<String>();
list.add(new String(a[0]+""));
return list;
}
else{
int[] b=new int[a.length-1];
for(int i=1;i<a.length;i++){
b[i-1]=a[i];
}
return switchTwo(new String(a[0]+""),getOrder(b));
}
}

public static void main(String args[]){
int[] a={4,5,8,9};
long start=System.currentTimeMillis();
ArrayList<String> list=new Order().getOrder(a);
long end=System.currentTimeMillis();
System.out.println(end-start);
for(String b:list){
System.out.println(b);
}
System.out.println(list.size());
}
}

全排列的思想就是
Cn1 C(n-1)1........
6楼正解

int main(int argc, char* argv[])
{
unsigned char cur[4] = {'a','b','c','d'};
unsigned char * iCur = cur;
unsigned char * jCur = cur;
unsigned char * kCur = cur;
unsigned char * mCur = cur; for( int i = 0; i<4; i++)
{
for( int j = 0; j<4; j++ )
{
for( int k=0; k<4; k++)
{
for( int m =0; m<4; m++)
if( iCur[i] == jCur[j] || kCur[k] == jCur[j] || mCur[m] == jCur[j] || iCur[i] == kCur[k] || iCur[i] == mCur[m] || kCur[k] == mCur[m])
{}
else
{
printf( "%c\t%c\t%c\t%c\t\n",iCur[i],jCur[j],kCur[k],mCur[m]);
}
}
}
}
return 0;
}
HAHA,Just a Test

import java.util.ArrayList;
import java.util.Arrays;public class Test {
/**
* 稍微改了下,变成3个参数
* 这样数组内数字重复的话也没问题
* 其中sss是要排序的数组
* 其他两参数初始用空的数组集合代进去就行
* @param sss
* @param ss1
* @param s11
* @return
*/
private ArrayList<int[]> queue(int[] sss, int[] ss1, ArrayList<int[]> s11) {
/*
* 如果sss长度不为0,那么递归
* 这里的主要概念就是,从sss里拿出一个元素
* 然后sss长度减1,去掉元素后面的元素都往前提一位
* 然后ss1长度加1,把刚才从sss里取出的放到ss1最后一位
*
* 因为用的是数组不是集合类,所以不能改
* 只好new了两个新的出来
* 用yyy代替sss,用yy1代替ss1
* for下嵌套的两个for
* 第一个是给新的yyy赋值
* 第二个是给新的yy1赋值
*/
if (sss.length > 0) {
int[] yyy = new int[sss.length - 1];
int[] yy1 = new int[ss1.length + 1];
for (int i = 0; i < sss.length; i++) {
for (int j = 0; j < yyy.length; j++) {
if (j < i)
yyy[j] = sss[j];
else
yyy[j] = sss[j + 1];
}
for (int k = 0; k < ss1.length; k++) {
yy1[k] = ss1[k];
}
yy1[yy1.length - 1] = sss[i];
queue(yyy, yy1, s11);
}
/*
* 此时sss长度应为0,ss1为原sss长度
* ss1则是排好顺序的数组
* 判断集合类里是否有数组与ss1相同
* 有,直接返回集合类
* 没有,添加ss1到集合类里再返回
*/
} else {
for (int[] s : s11)
if (Arrays.equals(ss1, s))
return s11;
s11.add(ss1);
return s11;
}
return s11;
} /**
* 过渡和输出用的方法
* @param sss
*/
public void taxis(int[] sss) {
int[] ss1 = new int[0];
ArrayList<int[]> s11 = new ArrayList<int[]>();
s11 = queue(sss, ss1, s11);
for (int[] s1 : s11) {
for (int s : s1)
System.out.print(s + " ");
System.out.println();
}
} public static void main(String[] args) {
int[] sss = { 1, 2, 3, 3 };
Test test = new Test();
test.taxis(sss); }
}

VC
void main(void){
int num[] = {4, 5, 8, 9}; for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
if (j != i)
for (int k = 0; k < 4; k++)
if (k != j && k != i){
cout << num[i] << " " << num[j] << " ";
cout << num[k] << " " << num[6 - i - j - k] << endl;
}
个人感觉，递归不适合这题~~

如果是10个数呢？
你难道要写100个for？？

//每得到1..len的一个序列，则可输出一个排序
//所以问题是得到所有1...len的序列
//自然想到递归
void sort(int array[],int pos[],int len,int lenC)
{
if(len==1){
for(int j=0;j<lenC;j++) cout<<array[pos[j]]<<" ";
cout<<endl;
return;
}
for(int i=0;i<len;i++){
int temp=pos[len-1];
pos[len-1]=pos[i];
pos[i]=temp;
sort(array,pos,len-1,lenC);
temp=pos[len-1];
pos[len-1]=pos[i];
pos[i]=temp;
}
}int main()
{
int data[]={4,5,8,9};
int pos[4];
for(int i=0;i<4;i++) pos[i]=i;
sort(data,pos,4,4);
return 0;
}

package com.txwoo.my;
import java.util.*;public class Joy { /**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
HashSet a = new HashSet();
int[] su = {1,2,3,4};
String in="" ;
for (int i= 0;i<su.length;i++) {
in = in + su[i];
}
a =devide(in,a);
System.out.println("***a.size="+a.size());
for(Iterator it = a.iterator();it.hasNext();) {
System.out.println("***="+it.next());
}
}
private static HashSet devide(String in,HashSet hah) {
if (in.length()==0) {
return hah;
}
String s = in.substring(0,1);
String str;
HashSet hs = new HashSet();
int i=0;
for (Iterator it = hah.iterator();it.hasNext();i++) {
str =it.next().toString();
for (int j=0;j<str.length();j++) {
hs.add(str.substring(0,j)+s+str.substring(j));
}
hs.add(str+s);
}
if (hah.size() ==0) {
hs.add(s);
}
return devide(in.substring(1),hs);
}
}***a.size=24
***=3124
***=4312
***=2143
***=3214
***=3241
***=4213
***=1432
***=1423
***=2431
***=1324
***=2314
***=2413
***=1243
***=1234
***=2341
***=4123
***=3142
***=4132
***=4321
***=2134
***=3421
***=3412
***=1342
***=4231

#include<stdio.h>
void main()
{
int sss[]={4,5,8,9};
int i,j;
int *ptr0=&sss[0];
int *ptr1=&sss[1];
int *ptr2=&sss[2];
int *ptr3=&sss[3];
int exc; for(i=0;i<4;i++)
{
for(j=0;j<3;j++)
{
printf("%d %d %d %d\n",*ptr0,*ptr1,*ptr2,*ptr3);
printf("%d %d %d %d\n",*ptr0,*ptr1,*++ptr2,*--ptr3); ptr2--;
ptr3++; exc=sss[1];
*ptr1=sss[2];
*ptr2=sss[3];
*ptr3=exc;
}
exc=sss[0];
*ptr0=sss[1];
*ptr1=sss[2];
*ptr2=sss[3];
*ptr3=exc;
}
}

建议楼主下载一本Java数据结构和算法.pdf
里面第６章　递归
中的变位字就是讲这个，非常详细

System.out.println(
"4   5   8   9\n"+
"4   5   9   8\n"+
"4   8   5   9\n"+
"4   8   9   5\n"+
"4   9   5   8\n"+
"4   9   8   5\n"+
"5   4   8   9\n"+
"5   4   9   8\n"+
"5   8   4   9\n"+
"5   8   9   4\n"+
"5   9   4   8\n"+
"5   9   8   4\n"+
"8   4   5   9\n"+
"8   4   9   5\n"+
"8   5   4   9\n"+
"8   5   9   4\n"+
"8   9   4   5\n"+
"8   9   5   4\n"+
"9   4   5   8\n"+
"9   4   8   5\n"+
"9   5   4   8\n"+
"9   5   8   4\n"+
"9   8   4   5\n"+
"9   8   5   4\n");

这样：public class test{
  String[] list;
  StringBuffer sb = new StringBuffer();
  int start;
  test(String in){
    list = in.split(",");
printList();
System.out.print(sb);
  }
  void replaceStr(int c1,int c2){
    String temp = list[c1];
    list[c1] = list[c2];
    list[c2] = temp;
  }
  void printList(){
    if(start==list.length-1)
      for(int i=0;i<list.length;i++)
        sb.append(list[i]+(i==list.length-1?"\n":","));
    else
      for(int i=start;i<list.length;i++){
        replaceStr(start++,i);
        printList();
        replaceStr(i,--start);
      }
  }
  public static void main(String args[]){
    new test(args[0]);
  }
}===========================C:\java>java test 4,5,8,9
4,5,8,9
4,5,9,8
4,8,5,9
4,8,9,5
4,9,8,5
4,9,5,8
5,4,8,9
5,4,9,8
5,8,4,9
5,8,9,4
5,9,8,4
5,9,4,8
8,5,4,9
8,5,9,4
8,4,5,9
8,4,9,5
8,9,4,5
8,9,5,4
9,5,8,4
9,5,4,8
9,8,5,4
9,8,4,5
9,4,8,5
9,4,5,8

可以用4个for循环每个循环输出一个数取随即数只要是他不等于前面的已经输出的,还有就是控制好循环次数就可以了

public class ListArrays { /**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = new int[]{1, 2, 3, 4, 5};
new ListArrays().list(a);
}

public void list(int[] a){
if(a.length == 1)
print(a[0]);
else{
for(int i = 0; i< a.length; i++){
print(a[i]);
//int[] b = 除了a[i] 的数组 ,这便没空写了
list(b);
}
}
}
private void print(int a){
System.out.println(a);
}

package org.hgalois.j2se.arithmetic;import java.util.ArrayList;
import java.util.List;/**
* 实质上是求1...n的全排列，求出1...n的全排列后可以对任意的字符数组作全排列输出
* @author Hgalois
*
*/public class AllSerial {

private int n ;

// 用于记录上一次输出的序列
private int[] lastNums ;

// 记录当前递归得到的结果序列
private List<Integer> curNums = new ArrayList<Integer>() ;

public AllSerial(int n) {
this.n = n ;

lastNums = new int[n] ;

for(int i=0; i<n; ++i)
lastNums[i] = i + 1 ;
}

public void printAllSerial() {
for(int i=0; i<n; ++i) {
// 标记数组
boolean [] flags = new boolean[n] ;

// 初始化标记数组
for(int j=0; j<n; ++j)
flags[i] = false ;

// 输出和调用递归函数
curNums.add(new Integer(i + 1)) ;
flags[i] = true ;

subSerial(flags) ;
}
}

private void subSerial(boolean [] flags) {
boolean flag = false ;

for(int i=0; i<flags.length; ++i) {
if(!flags[i]) {
curNums.add(new Integer(i + 1)) ;
flag = true ;
boolean [] newflag = new boolean[flags.length] ;
System.arraycopy(flags, 0, newflag, 0, flags.length) ;
newflag[i] = true ;
subSerial(newflag) ;
}
}

if(!flag) {
int curSize = curNums.size() ;
for(int i=curSize; i>0; --i )
lastNums[n - (curSize - i) - 1] = curNums.get(i-1) ;
for(int i=0; i<lastNums.length; ++i)
System.out.print(lastNums[i] + " ") ;
System.out.println() ;
curNums.clear() ;
}
}

public static void main(String[] args) {
new AllSerial(4).printAllSerial() ;
}}/*
运行结果：
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1
*/

public class TTest { /**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] in={2,3,4,5};
for(int i=0;i<4;++i){
for(int j=0;j<4;++j){
if(i!=j){
for(int m=0;m<4;++m){
if((m!=i)&(m!=j)){
for(int n=0;n<4;++n){
if((n!=i)&(n!=j)&(n!=m)){
System.out.println(in[i]+" "+in[j]+" "+in[m]+" "+in[n]);
}}}
}}
}
}
}
}

用C语言到不是很难用 JAVA就不知道了咯

public class Test {
    public void test(String number ,String result ,int len){
     if(result.length()==len){
     System.out.println(result);
     }
     else{
     for(int i=0;i<number.length();i++){
     if(result.indexOf(number.charAt(i))<0){
     this.test(number, result+number.charAt(i), len);
     }
     }
     }
    }
    public static void main(String ss[]){
     Test tt = new Test();
     tt.test("5678", "", "5678".length());
    }
}

neng yunxinag ma

try this
参数是你要输入的数组的所有内容public class Permutation {
public static void main(String[] args) {
number = args;
len = args.length;
print(0);
} static String[] number;
static int len; private static void print(int n) {
if (n == len) {
for (int i = 0; i < len - 1; i++) {
System.out.print((number[i] + ","));
}
System.out.print(number[len - 1] + "\n");
return;
}
String temp;
for (int i = n; i < len; i++) {
temp = number[i];
number[i] = number[n];
number[n] = temp;
print(n + 1);
temp = number[i];
number[i] = number[n];
number[n] = temp;
}
}
}

public class t2 {
public void t2(){};
public static void main(String args[]){
int testint[]={4,6,8,9};
t2 T=new t2();
T.printallpaixu(testint,"");
}
public void printallpaixu(int A[],String frontstr){
int size=A.length;
if (size==2) {
System.out.println(frontstr+" "+A[0]+" "+ A[1]);
System.out.println(frontstr+" "+A[1]+" "+ A[0]);
return;
}
for (int i=0;i<size;i++){
String newforntstr=frontstr+" "+A[i];
printallpaixu(getMinusArray(i,A),newforntstr);
}
}
/*获得少一个元素的新数组*/
private int[] getMinusArray(int movepos,int[] oldarray){
int size=oldarray.length;
int[] newarray=new int[size-1];
for (int i=0;i<size;i++){
if (i<movepos) {
newarray[i]=oldarray[i];
} else if(i>movepos){
newarray[i-1]=oldarray[i];
}
}
return newarray;
}
}

自己写了一个, 然后和 16 楼的程序比较了一下, 输出结果及顺序完全相同.
又比较了一下效率, 发现我的高不少. 先自赞一个!
不知道是我的测试方法不正确还是怎么着, 现在贴出来让大家看看./**
* 现在有int sss[] = {4,5,8,9}，写一段程序让程序输出sss这个数组的所有排序！
* 比如说4,5,8,9
* 4,5,9,8
* 4,9,5,8
* 4,9,8,5等等所有的排序种类，总共应该是24种,这个程序应该怎么编写？谢谢
*/
public class RandomArray
{
private int kind = 1;
private StringBuilder sbuf = new StringBuilder(20);        /* 16 楼的程序开始 */
private void queue(int[] sss, int[] ss1)
{
if (sss.length > 1)
{
int[] yyy = new int[sss.length - 1];
int[] yy1 = new int[ss1.length + 1];
for (int i = 0; i < sss.length; i++)
{
int sum;
for (int j = 0; j < yyy.length; j++)
{
if (j < i)
sum = j;
else
sum = j + 1;
yyy[j] = sss[sum];
}
for (int k = 0; k < ss1.length; k++)
{
yy1[k] = ss1[k];
}
yy1[yy1.length - 1] = sss[i];
queue(yyy, yy1);
}
}
else
{
// sbuf.append("第").append(kind++).append("种: ");
for (int s : ss1)
sbuf.append((char) s + "");
sbuf.append((char) sss[0]);
// System.out.println(sbuf);
sbuf = new StringBuilder(20);
}
} public void taxis(int[] sss)
{
kind = 1;
int[] ss1 = new int[0];
queue(sss, ss1);
}
        /* 16 楼程序结束. 下面的两个方法就是我的程序了 ^_^ */
private int[] getSubArray(int[] array, int kickPosition)
{
if (array == null || array.length == 0)
return array;
int[] copyArray = new int[array.length - 1];
int posCopyArray = 0;
for (int posArray = 0; posArray < array.length; posArray++)
{
if (posArray == kickPosition)
continue;
else
copyArray[posCopyArray++] = array[posArray];
}
return copyArray;
} public void allArrange(int[] array)
{
int[] tmp;
if (array == null || array.length == 0)
return;
if (array.length == 1)
{
// System.out.println(sbuf.toString() + array[0]);
}
else
{
for (int i = 0; i < array.length; i++)
{
tmp = this.getSubArray(array, i);
sbuf.append(array[i]);
allArrange(tmp);
}
}
if (sbuf.length() != 0)
sbuf.deleteCharAt(sbuf.length() - 1);
}        /* 测试方法, 各运行 1000 遍需要的时间
public static void main(String[] args)
{
int[] sss = { '1', '2', '3', '4', '5', '6' };
int times = 1000;
int i;
RandomArray test = new RandomArray();
long t1 = System.currentTimeMillis();
i = times;
while (i-- > 0)
{
test.taxis(sss);
}
long t2 = System.currentTimeMillis();
i = times;
while (i-- > 0)
{
test.allArrange(sss);
}
long t3 = System.currentTimeMillis();
System.out.println(t2 - t1);
System.out.println(t3 - t2);
}
}
下面是结果1953
313

测试：
C:\java>java RandomArray
2904 16
521 65
10 38

C:\java> java   RandomArray
2904   16
521   65
210   38

调试易

面试一个编程题，没做出来帮我看看

解决方案 »