對(duì)一個(gè)算法筆試題的注解

算法程序題：

    該公司筆試題就1個(gè)，要求在10分鐘內(nèi)作完。

    題目如下：用1、2、2、3、4、5這六個(gè)數(shù)字，用java寫(xiě)一個(gè)main函數(shù)，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"與"5"不能相連。

  基本思路：
1 把問(wèn)題歸結(jié)為圖結(jié)構(gòu)的遍歷問(wèn)題。實(shí)際上6個(gè)數(shù)字就是六個(gè)結(jié)點(diǎn)，把六個(gè)結(jié)點(diǎn)連接成無(wú)向連通圖，對(duì)于每一個(gè)結(jié)點(diǎn)求這個(gè)圖形的遍歷路徑，所有結(jié)點(diǎn)的遍歷路徑就是最后對(duì)這6個(gè)數(shù)字的排列組合結(jié)果集。
2 顯然這個(gè)結(jié)果集還未達(dá)到題目的要求。從以下幾個(gè)方面考慮：
  1. 3，5不能相連：實(shí)際要求這個(gè)連通圖的結(jié)點(diǎn)3，5之間不能連通, 可在構(gòu)造圖結(jié)構(gòu)時(shí)就滿足改條件，然后再遍歷圖。
  2. 不能有重復(fù): 考慮到有兩個(gè)2，明顯會(huì)存在重復(fù)結(jié)果，可以把結(jié)果集放在TreeSet中過(guò)濾重復(fù)結(jié)果。//TreeSet用于過(guò)濾一個(gè)集合中相同的東西還真是個(gè)挺不錯(cuò)的方法
  3. 4不能在第三位: 仍舊在結(jié)果集中去除滿足此條件的結(jié)果。

采用二維數(shù)組定義圖結(jié)構(gòu)，最后的代碼是：

 1package test;
 2
 3import java.util.Iterator;
 4import java.util.TreeSet;
 5
 6public class TestQuestion {
 7
 8    private String[] b = new String[] { "1", "2", "2", "3", "4", "5" };
 9    private int n = b.length;
10    private boolean[] visited = new boolean[n];
11    private int[][] a = new int[n][n];
12    private String result = "";
13    private TreeSet treeSet = new TreeSet();// 用于保存結(jié)果，具有過(guò)濾相同結(jié)果的作用。
14
15    public static void main(String[] args) {
16        new TestQuestion().start();
17    }
18
19    private void start() {
20        // 創(chuàng)建合法路徑標(biāo)識(shí)集合
21        for (int i = 0; i < n; i++) {
22            for (int j = 0; j < n; j++) {
23                if (i == j) {
24                    a[i][j] = 0;
25                } else {
26                    a[i][j] = 1;
27                }
28            }
29        }
30        a[3][5] = 0;
31        a[5][3] = 0;
32        for (int i = 0; i < n; i++) {
33            this.depthFirstSearch(i);// 深度遞歸遍歷
34        }
35        Iterator it = treeSet.iterator();
36        while (it.hasNext()) {
37            String string = (String) it.next();
38
39            if (string.indexOf("4") != 2) {
40                System.out.println(string);
41            }
42        }
43    }
44
45    /** *//**
46     * 深度優(yōu)先遍歷
47     * 
48     * @param startIndex
49     */
50    private void depthFirstSearch(int startIndex) {
51        // 遞歸的工作
52        visited[startIndex] = true;// 用于標(biāo)識(shí)已經(jīng)走過(guò)的節(jié)點(diǎn)
53        result = result + b[startIndex];// 構(gòu)造結(jié)果
54        if (result.length() == n) {
55            treeSet.add(result);// 添加到TreeSet類型中，具有過(guò)濾相同結(jié)果的作用
56        }
57        // 每走到一個(gè)節(jié)點(diǎn)，挨個(gè)遍歷下一個(gè)節(jié)點(diǎn)
58        for (int j = 0; j < n; j++) {
59            if (a[startIndex][j] == 1 && visited[j] == false) {
60                depthFirstSearch(j);// 深度遞歸遍歷
61            } else {
62                continue;
63            }
64        }
65        // 遞歸的收尾工作
66        result = result.substring(0, result.length() - 1);
67        visited[startIndex] = false;// 取消訪問(wèn)標(biāo)識(shí)
68    }
69}
70