一著名软件公司的java笔试算法题！
一著名软件公司的java笔试算法题！
算法程序题：
该公司笔试题就1个，要求在10分钟内作完。
题目如下：用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连。
问题点数：10、回复次数：17Top
1 楼flyli_wh（fly）回复于 2006-10-09 09:49:02 得分 0
总数为：33743Top
2 楼flyli_wh（fly）回复于 2006-10-09 09:49:28 得分 0
是不是33743条？Top
3 楼javaliu2006（）回复于 2006-10-09 10:46:52 得分 0
老大，是要打印出所有不同排列的情况昵
而不是总数！Top
4 楼ChDw（米）回复于 2006-10-09 11:07:43 得分 5
他要求的是不重复选择吧（这里存在两个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();
}
}
Top
5 楼Rayuu（）回复于 2006-10-09 11:19:57 得分 0
没看懂……跑了一下，有很多重复的结果。Top
6 楼ChDw（米）回复于 2006-10-09 12:01:46 得分 0
不过重复的确未去除倒是一个问题Top
7 楼gseah（）回复于 2006-10-09 12:54:44 得分 0
thinkingTop
8 楼Jujus（某人）回复于 2006-10-11 09:39:36 得分 5
我的解法，共计耗时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);// 尚未实现
}
}Top
9 楼inorro（）回复于 2006-10-11 09:49:42 得分 0
这个帖你发几遍了，还不只在这版里，在其他版也发过了吧。
都给出正解了。你还不结帖，你是不是不会结帖阿。Top
10 楼arbiter（同济流氓）回复于 2006-10-11 11:07:31 得分 0
看见大家循环套循环，圈圈套圈圈的写法，我实在是忍无可忍了，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;
}
}
可以结贴了。
Top
11 楼Jujus（某人）回复于 2006-10-11 11:50:51 得分 0
to 流氓：
我的解法好像不是圈圈套圈圈.....
而且使用字典序法不会出现重复排列值，呵呵，我可是花了65分钟去证明的Top
12 楼arbiter（同济流氓）回复于 2006-10-11 12:05:39 得分 0
恩，我没说你。Top
13 楼fhlfhl（）回复于 2006-10-11 13:52:26 得分 0
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'));
}
}
我利用上午的一些时间写的，请指教Top
14 楼bill1973（比尔）回复于 2006-10-11 18:35:53 得分 0
// 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);
}
}
}Top
15 楼Windsorr（温莎公主）回复于 2006-10-12 00:29:33 得分 0
我想可以写成递归的...乱写了一下...可以满足楼主的要求哦
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);
}
}
}
}
}
}
}
}
Top
16 楼Windsorr（温莎公主）回复于 2006-10-12 00:35:03 得分 0
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);
}
}
}
}
}
}
}
}Top
17 楼Windsorr（温莎公主）回复于 2006-10-12 01:07:37 得分 0
成功写出递归..嘻嘻
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);
}
}
Top
