公司笔试算法题

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

 

 

 

 

 

  基本思路：
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];
visited =falsh;
private int[][] a = new int[n][n];
private String result = "";
private TreeSet TreeSet = new TreeSet();
public static void main(String[] args) {
new TestQuestion().start();
}
private void start() {
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;
}
}
}a[3][5] = 0;
a[5][3] = 0;
for (int i = 0; i < n; i++) {
    this.depthFirstSearch(i);
}
Iterator it = set.iterator();
while (it.hasNext()) {
String string = (String) it.next();

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) {
TreeSet .add(result);
}
for(int j = 0; j < n; j++) {
if (a[startIndex][j] == 1 && visited[j] == false) {
depthFirstSearch(j);
} else {
continue;
}
}
    result = result.substring(0, result.length() -1);
    visited[startIndex] = false;
}
}

 

 

没考虑过用无相连通图求全排列，学习了。
我的思路：递归求全排列+条件筛选，代码：

public static void permutation(int[] src, int m) {
		if (m == src.length) {
			if (src.length > 3 && src[2] != 4) {
				boolean bPrint = true;
				for (int i = 0; i < src.length - 1; i++) {
					if ((src[i] == 3 && src[i + 1] == 5)
							|| (src[i] == 5 && src[i + 1] == 3)) {
						bPrint = false;
					}
				}
				if (bPrint)
					print(src);
			}
		} else {
			for (int i = m; i < src.length; i++) {
				swap(src, m, i);
				permutation(src, m + 1);
				swap(src, m, i);
			}
		}
	}

	public static void print(int[] src) {
		for (int i = 0; i < src.length; i++)
			System.out.print(src[i]);
		System.out.println();
	}

	private static void swap(int[] src, int m, int i) {
		int t = src[m];
		src[m] = src[i];
		src[i] = t;
	}

建议lz把调试过的成功程序贴出来，菜鸟飞过~~

大学里念的忘光鸟~~~~

for 循环,在第3层遇到4就 continue,每次遇到3或5都判断下前面1个是否是另一个,如果是就 continue,完事了,判断3,5的可以抽取出来写1个独立的函数,

楼主题目里：412345也算是符合条件的？

10分钟的题目  LZ你多想了
首先是全for循环 得到待输出的p
然后对p做判断 是否system.out.print就好了

2. 不能有重复: 考虑到有两个2，明显会存在重复结果，可以把结果集放在TreeSet中过滤重复结果

这个太低效了。原题可以转化为：
求1，2，3，4，5，6的所有全排列方案，并作以下过滤：
1） 4不在第3位
2） 3，5不相邻
3） 2不能在6后面
最后在输出时把6换成2

楼上的,2凭啥不能在6后面?

楼上的，“最后在输出时把6换成2”，所以126345和162345 , 最后输出都是122345。保证2不在6后面，在构造全排列过程中就可以去掉重复，不需要缓存历史结果来比较。