天堂√在线观看一区二区 ,不卡的av在线播放,亚洲精品自产拍

算法程序題：

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

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

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

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

1

package test;
2

3

import java.util.Iterator;
4

import java.util.TreeSet;
5

6

public 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é)果，具有過濾相同結(jié)果的作用。
14

15

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

new TestQuestion().start();
17

}
18

19

private void start() {
20

// 創(chuàng)建合法路徑標(biāo)識集合
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)識已經(jīng)走過的節(jié)點(diǎn)
53

result = result + b[startIndex];// 構(gòu)造結(jié)果
54

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

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

}
57

// 每走到一個節(jié)點(diǎn)，挨個遍歷下一個節(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;// 取消訪問標(biāo)識
68

}
69

}
70

轉(zhuǎn)載于http://www.aygfsteel.com/ITdavid/archive/2008/02/27/182483.html

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

新用戶注冊刷新評論列表


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




網(wǎng)站導(dǎo)航: 博客園 IT新聞 Chat2DB C++博客博問管理

<

2008年3月

>

日

一

二

三

四

五

六

24

25

26

27

28

29

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

4

5

導(dǎo)航

統(tǒng)計

隨筆 - 122
文章 - 0
評論 - 89
引用 - 0

常用鏈接

留言簿(4)

隨筆分類

隨筆檔案

文章分類

FLEX (rss)

新聞分類

J-Hi (rss)

對一個算法筆試題的注解