一著名软件公司的java笔试算法题！

Question

一著名软件公司的java笔试算法题！算法程序题：    该公司笔试题就1个，要求在10分钟内作完。    题目如下：用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连。

Answer 1

他要求的是不重复选择吧（这里存在两个2，分别算的）private int[] num = new int[]{1,2,2,3,4,5};
private boolean[] selected = null;
public static void main(String[] args) throws Exception {
new Test().test();
}
private void test() {
selected = new boolean[num.length];
List<Integer> result = new ArrayList<Integer>();
next(result);
}private void next(List<Integer> result) {
if(result.size() == num.length)
printResult(result);
else {
for(int i = 0; i < num.length; i++) {
if(!selected[i]) {
selected[i] = true;
result.add(num[i]);
next(result);
result.remove(result.size() - 1);
selected[i] = false;
}
}
}
}
private void printResult(List<Integer> result) {
if(result.get(2).intValue() != 4) {
for(int i = 1; i < result.size(); i++)
if(result.get(i - 1).intValue() == 3 && result.get(i).intValue() == 5)
return;
for(int i = 0; i < result.size(); i++)
System.out.print(result.get(i));
System.out.println();
}
}

Answer 2

我的解法，共计耗时90分钟......
思考、论证字典序法是否适用耗时65分钟，编码调试25分钟package org;public class PaiLie {   // 检查排列值是否符合试题中的条件
   private boolean testValues(int[] buf) {
      // 检查4是否在第3位
      if (buf[2] == 4 /* 4在第3位 */) return false;      // 检查3、5是否相连
      for (int i = 0; i < buf.length - 1; i++) {
         if ((buf[i] == 3 && buf[i + 1] == 5)
            || (buf[i] == 5 && buf[i + 1] == 3)) return false;      }
      return true;   }
   // 输出
   private void print(int[] buf) {
      for (int i = 0; i < buf.length; i++) {
         System.out.print(buf[i] + " ");
      }
      System.out.println();
   }
   // ////////////////////////////////////////////////////////////////////
   // 字典法   // 是否应该考虑使用Comparable接口的数组？！
   private void dict(int[] buf) {
      int count = 0; // 计数器      // 初始化排列元，将字典元按由小到大排列，此时，buf中为全排列中的最小值
      for (int i = 0; i < buf.length - 1; i++) {
         for (int j = i + 1; j < buf.length; j++) {
            if (buf[i] > buf[j]) {
               int x = buf[i];
               buf[i] = buf[j];
               buf[j] = x;
            }
         }
      }      // 按字典排序遍历所有的排列值，符合条件的输出
      int[] next = buf;
      do {
         if (testValues(next)) {
            count++;
            print(next);
         }
         next = findNext(next);// 找全排列中的下一个排列值
      } while (next != null);      System.out.println(count);   }
   // 查找字典法中当前排列值的下一个排列值
   private int[] findNext(int[] buf) {      // 自右向左扫描，找到第一个下降点
      int lowerPoint = -1; // 记录下降点
      for (int i = buf.length - 1; i > 0; i--) {
         if (buf[i] > buf[i - 1]) {
            lowerPoint = i - 1;
            break;
         }
      }      if (lowerPoint >= 0) {
         int[] temp = new int[buf.length];
         System.arraycopy(buf, 0, temp, 0, buf.length);// 拷贝前缀         // 找下一个进位值，并于下降位交换
         int stardard = buf[lowerPoint];
         int next = Integer.MAX_VALUE;
         int pos = 0;
         for (int i = lowerPoint + 1; i < buf.length; i++) {
            if (buf[i] > stardard && next > buf[i]) {
               next = buf[i];
               pos = i;
            }
         }         temp[lowerPoint] = next;
         temp[pos] = stardard;         // 对后缀排序，找到最小后缀
         for (int i = lowerPoint + 1; i < buf.length - 1; i++) {
            for (int j = i + 1; j < buf.length; j++) {
               if (temp[i] > temp[j]) {
                  int x = temp[i];
                  temp[i] = temp[j];
                  temp[j] = x;
               }
            }
         }         return temp;      } else
         // 没有下降点时说明已经是最大排列值了
         return null;
   }
   // ////////////////////////////////////////////////////////////////////////////
   // ////////////////////////////////////////////////////////////////////////////   public static void main(String[] args) {
      int[] array = new int[] { 1, 2, 2, 3, 4, 5 };
      PaiLie pl = new PaiLie();
      pl.dict(array);
      //pl.emnu(array);// 尚未实现
   }
}

Answer 3

看见大家循环套循环，圈圈套圈圈的写法，我实在是忍无可忍了，6个数字还好，给你一百个数字，是不是准备百环大作战了？
我来实现一下我之前讲的基本思路：
1 把问题归结为图结构的遍历问题。实际上6个数字就是六个结点，把六个结点连接成无向连通图，对于每一个结点求这个图形的遍历路径，所有结点的遍历路径就是最后对这6个数字的排列组合结果集。
2 显然这个结果集还未达到题目的要求。从以下几个方面考虑：
  1. 3，5不能相连：实际要求这个连通图的结点3，5之间不能连通, 可在构造图结构时就满足改条件，然后再遍历图。
  2. 不能有重复: 考虑到有两个2，明显会存在重复结果，可以把结果集放在TreeSet中过滤重复结果
  3. 4不能在第三位: 仍旧在结果集中去除满足此条件的结果。采用二维数组定义图结构，最后的代码是：import java.util.Iterator;
import java.util.TreeSet;public class TestQuestion {private String[] b = new String[]{"1", "2", "2", "3", "4", "5"};
private int n = b.length;
private boolean[] visited = new boolean[n];
private int[][] a = new int[n][n];
private String result = "";
private TreeSet set = new TreeSet();public static void main(String[] args) {
new TestQuestion().start();
}private void start() {// Initial the map a[][]
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
a[i][j] = 0;
} else {
    a[i][j] = 1;
}
}
}// 3 and 5 can not be the neighbor.
a[3][5] = 0;
a[5][3] = 0;// Begin to depth　search.
for (int i = 0; i < n; i++) {
    this.depthFirstSearch(i);
}// Print result treeset.
Iterator it = set.iterator();
while (it.hasNext()) {
String string = (String) it.next();
// "4" can not be the third position.
if (string.indexOf("4") != 2) {
System.out.println(string);
}
}
}private void depthFirstSearch(int startIndex) {
visited[startIndex] = true;
result = result + b[startIndex];
if (result.length() == n) {
// Filt the duplicate value.
set.add(result);
}
for(int j = 0; j < n; j++) {
if (a[startIndex][j] == 1 && visited[j] == false) {
depthFirstSearch(j);
} else {
continue;
}
}// restore the result value and visited value after listing a node.
    result = result.substring(0, result.length() -1);
    visited[startIndex] = false;
}
}可以结贴了。

Answer 4

public class Test { /**
 * @param args
 */
public static void f() {
String s;
int ii = 0;
int[] a = { 1, 2, 2, 3, 4, 5, 6 };
int[] b = { 1, 2, 2, 3, 4, 5, 6 };
for (int i0 = 0; i0 < 6; i0++) {
// b = null;
b[0] = a[i0];
for (int i1 = 0; i1 < 7; i1++) {
if (i1 == 7)
break;
if (i1 == i0)
continue;
b[1] = a[i1];
for (int i2 = 0; i2 < 7; i2++) {
if (i1 == 7)
break;
if (i2 == i0 || i2 == i1)
continue;
b[2] = a[i2];
for (int i3 = 0; i3 < 7; i3++) {
if (i3 == 7)
break;
if (i3 == i0 || i3 == i1 || i3 == i2)
continue;
b[3] = a[i3];
for (int i4 = 0; i4 < 7; i4++) {
if (i4 == 7)
break;
if (i4 == i0 || i4 == i1 || i4 == i2 || i4 == i3)
continue;
b[4] = a[i4];
for (int i5 = 0; i5 < 7; i5++) {
if (i5 == 7)
break;
if (i5 == i0 || i5 == i1 || i5 == i2
|| i5 == i3 || i5 == i4)
continue;
b[5] = a[i5];
s = null;
// for (int b1 = 0; b1 < 6; b1++) {
s = "" + b[0] + b[1] + b[2] + b[3] + b[4]
+ b[5];
// }
int index = s.indexOf('3');
if (index < 5 && b[index + 1] == 5)
continue; int ind = s.indexOf('5');
if (ind < 5 && b[ind + 1] == 3)
continue;
// continue; if (b[2] != 4 && s.indexOf('6') == -1) {
System.out.println(s + "----" + ++ii);
} else {
continue;
}
} }
}
}
}
}
} public static void main(String[] args) {
// TODO Auto-generated method stub
Test.f();
// Test.g();
System.out.println("122345".indexOf('5'));
}}
我利用上午的一些时间写的，请指教

Answer 5

// a 为 1 2 3 4 5; b 开始为"" 
private static void PrintInt(ArrayList<Integer> a, String b) { // b=""
if (a.size() ==1){
System.out.print(b + a.get(0) + "\t");
return;
}else {
for (int i=0; i< a.size(); i++){
String temp_b=b;
temp_b+=a.get(i);
ArrayList<Integer> temp =(ArrayList<Integer>)a.clone();
temp.remove(i);
PrintInt(temp, temp_b);
}
}

}

Answer 6

我想可以写成递归的...乱写了一下...可以满足楼主的要求哦import java.util.ArrayList;public class JavaLiu {
public static void main(String[] args) {
String str1, str2, str3, str4, str5, str6;
ArrayList list = new ArrayList();
list.add("1");
list.add("2");
list.add("2");
list.add("3");
list.add("4");
list.add("5");
ArrayList list1, list2, list3, list4, list5, list6;
for (int a = 0; a < 6; a++) {
list1 = (ArrayList) list.clone();
str1 = (String) list1.get(a);
for (int b = 0; b < 5; b++) {
list2 = (ArrayList) list1.clone();
list2.remove(a);
str2 = str1 + list2.get(b);
for (int c = 0; c < 4; c++) {
list3 = (ArrayList) list2.clone();
list3.remove(b);
str3 = str2 + list3.get(c);
for (int d = 0; d < 3; d++) {
list4 = (ArrayList) list3.clone();
list4.remove(c);
str4 = str3 + list4.get(d);
for (int e = 0; e < 2; e++) {
list5 = (ArrayList) list4.clone();
list5.remove(d);
str5 = str4 + list5.get(e);
list6 = (ArrayList) list5.clone();
list6.remove(e);
str6 = str5 + list6.get(0);
if (str6.charAt(2) != '4'
&& str6.indexOf("35") == (-1)) {
System.out.println(str6);
}
}
}
}
}
}
}
}

Answer 7

import java.util.ArrayList;public class JavaLiu {
   public static void main(String[] args) {
      String str1, str2, str3, str4, str5, str6;
      ArrayList list = new ArrayList();
      list.add("1");
      list.add("2");
      list.add("2");
      list.add("3");
      list.add("4");
      list.add("5");
      ArrayList list1, list2, list3, list4, list5, list6;
      for (int a = 0; a < 6; a++) {
         list1 = (ArrayList) list.clone();
         str1 = (String) list1.get(a);
         for (int b = 0; b < 5; b++) {
             list2 = (ArrayList) list1.clone();
             list2.remove(a);
             str2 = str1 + list2.get(b);
             for (int c = 0; c < 4; c++) {
                list3 = (ArrayList) list2.clone();
                list3.remove(b);
                str3 = str2 + list3.get(c);
                for (int d = 0; d < 3; d++) {
                   list4 = (ArrayList) list3.clone();
                   list4.remove(c);
                   str4 = str3 + list4.get(d);
                   for (int e = 0; e < 2; e++) {
                       list5 = (ArrayList) list4.clone();
                       list5.remove(d);
                       str5 = str4 + list5.get(e);
                       list6 = (ArrayList) list5.clone();
                       list6.remove(e);
                       str6 = str5 + list6.get(0);
                       if (str6.charAt(2) != '4'
                        && str6.indexOf("35") == (-1)) {
                        System.out.println(str6);
                       }
                       }
                   }
                }
             }
         }
      }
}

Answer 8

成功写出递归..嘻嘻import java.util.ArrayList;public class Sunkist {
private static void Windsorr(String str2, ArrayList list2) {
String str = str2.toString();
ArrayList list = (ArrayList) list2.clone();
if (list.size() == 1) {
str = str + list.get(0);
if (str.charAt(2) != '4' && str.indexOf("35") == (-1)) {
System.out.println(str);
}
} else {
for (int i = 0; i < list.size(); i++) {
str = str + list.get(i);
list.remove(i);
Windsorr(str, list);
str = str2.toString();
list = (ArrayList) list2.clone();
}
}
}public static void main(String[] args) {
String str = "";
ArrayList list = new ArrayList();
list.add("1");
list.add("2");
list.add("2");
list.add("3");
list.add("4");
list.add("5");Windsorr(str, list);
}
}