有关算法的程序题

今天上网的时候看到这样一道程序题，做完后觉得很经典，写出来与大家分享。

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

1. static int[] bits = new int[] { 1, 2, 3, 4, 5 }; 
2.  
3. /** 
4.  * @param args 
5.  */ 
6. public static void main(String[] args) { 
7. sort("", bits); 
8. } 
9.  
10. private static void sort(String prefix, int[] a) { 
11. if (a.length == 1) { 
12. System.out.println(prefix + a[0]); 
13. } 
14.  
15. for (int i = 0; i < a.length; i++) { 
16. sort(prefix + a[i], copy(a, i)); 
17. } 
18. } 
19.  
20. private static int[] copy(int[] a,int index){ 
21. int[] b = new int[a.length-1]; 
22. System.arraycopy(a, 0, b, 0, index); 
23. System.arraycopy(a, index+1, b, index, a.length-index-1); 
24. return b; 
25. } 

基本思路： 1 把问题归结为图结构的遍历问题。实际上6个数字就是六个结点，把六个结点连接成无向连通图，对于每一个结点求这个图形的遍历路径，所有结点的遍历路径就是 最后对这6个数字的排列组合结果集。 2 显然这个结果集还未达到题目的要求。从以下几个方面考虑： 1. 3，5不能相连：实际要求这个连通图的结点3，5之间不能连通, 可在构造图结构时就满足改条件，然后再遍历图。 2. 不能有重复: 考虑到有两个2，明显会存在重复结果，可以把结果集放在TreeSet中过滤重复结果 3. 4不能在第三位: 仍旧在结果集中去除满足此条件的结果。 采用二维数组定义图结构，最后的代码是：

1. import java.util.Iterator; 
2. import java.util.TreeSet; 
3.  
4. public class TestQuestion { 
5.  
6. private String[] b = new String[]{"1", "2", "2", "3", "4", "5"}; 
7. private int n = b.length; 
8. private boolean[] visited = new boolean[n]; 
9. private int[][] a = new int[n][n]; 
10. private String result = ""; 
11. private TreeSet set = new TreeSet(); 
12.  
13. public static void main(String[] args) { 
14. new TestQuestion().start(); 
15. } 
16.  
17. private void start() { 
18.  
19. // Initial the map a[][] 
20. for (int i = 0; i < n; i++) { 
21. for (int j = 0; j < n; j++) { 
22. if (i == j) { 
23. a[i][j] = 0; 
24. } else { 
25.     a[i][j] = 1; 
26. } 
27. } 
28. } 
29.  
30. // 3 and 5 can not be the neighbor. 
31. a[3][5] = 0; 
32. a[5][3] = 0; 
33.  
34. // Begin to depth　search. 
35. for (int i = 0; i < n; i++) { 
36.     this.depthFirstSearch(i); 
37. } 
38.  
39. // Print result treeset. 
40. Iterator it = set.iterator(); 
41. while (it.hasNext()) { 
42. String string = (String) it.next(); 
43. // "4" can not be the third position. 
44. if (string.indexOf("4") != 2) { 
45. System.out.println(string); 
46. } 
47. } 
48. } 
49.  
50. private void depthFirstSearch(int startIndex) { 
51. visited[startIndex] = true; 
52. resultresult = result + b[startIndex]; 
53. if (result.length() == n) { 
54. // Filt the duplicate value. 
55. set.add(result); 
56. } 
57. for(int j = 0; j < n; j++) { 
58. if (a[startIndex][j] == 1 && visited[j] == false) { 
59. depthFirstSearch(j); 
60. } else { 
61. continue; 
62. } 
63. } 
64.  
65. // restore the result value and visited value after listing a node. 
66.     resultresult = result.substring(0, result.length() -1); 
67.     visited[startIndex] = false; 
68. } 
69. } 

怎么样，很有收获吧，哈哈

本文转自sucre03 51CTO博客，原文链接：http://blog.51cto.com/sucre/416697，如需转载请自行联系原作者