亚洲美女激情视频,九月丁香婷婷亚洲综合色,国产午夜亚洲精品国产

對一個算法筆試題的注解

算法程序題：

該公司筆試題就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中過濾重復結果。//TreeSet用于過濾一個集合中相同的東西還真是個挺不錯的方法
3. 4不能在第三位: 仍舊在結果集中去除滿足此條件的結果。

采用二維數組定義圖結構，最后的代碼是：

package test;
2

import java.util.Iterator;
4

import java.util.TreeSet;
5

public class TestQuestion {
7

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();// 用于保存結果，具有過濾相同結果的作用。
14

public static void main(String[] args) {
16

new TestQuestion().start();
17

}
18

private void start() {
20

// 創建合法路徑標識集合
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

if (string.indexOf("4") != 2) {
40

System.out.println(string);
41

}
42

}
43

}
44

/**
46

* 深度優先遍歷
47

*
48

* @param startIndex
49

*/
50

private void depthFirstSearch(int startIndex) {
51

// 遞歸的工作
52

visited[startIndex] = true;// 用于標識已經走過的節點
53

result = result + b[startIndex];// 構造結果
54

if (result.length() == n) {
55

treeSet.add(result);// 添加到TreeSet類型中，具有過濾相同結果的作用
56

}
57

// 每走到一個節點，挨個遍歷下一個節點
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;// 取消訪問標識
68

}
69

}
70

轉載于http://www.tkk7.com/ITdavid/archive/2008/02/27/182483.html

posted on 2008-03-01 10:42 魯勝迪閱讀(296) 評論(0) 編輯收藏

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理

對一個算法筆試題的注解

對一個算法筆試題的注解

導航

統計

常用鏈接

留言簿(4)

隨筆分類

隨筆檔案

文章分類

新聞分類

搜索

最新評論

閱讀排行榜

評論排行榜