Java算法程序題：

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

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

Java算法基本思路：

1 把問題歸結(jié)為圖結(jié)構(gòu)的遍歷問題。實際上6個數(shù)字就是六個結(jié)點，把六個結(jié)點連接成無向連通圖，對于每一個結(jié)點求這個圖形的遍歷路徑，所有結(jié)點的遍歷路徑就是***對這6個數(shù)字的排列組合結(jié)果集。

2 顯然這個結(jié)果集還未達到題目的要求。從以下幾個方面考慮：

1. 3，5不能相連：實際要求這個連通圖的結(jié)點3，5之間不能連通, 可在構(gòu)造圖結(jié)構(gòu)時就滿足改條件，然后再遍歷圖。

2. 不能有重復(fù): 考慮到有兩個2，明顯會存在重復(fù)結(jié)果，可以把結(jié)果集放在TreeSet中過濾重復(fù)結(jié)果

3. 4不能在第三位: 仍舊在結(jié)果集中去除滿足此條件的結(jié)果。

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

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;  
resultresult = 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;  
}  
}  
    resultresult = result.substring(0, result.length() -1);  
    visited[startIndex] = false;  
}  
}  
 

注:郁悶,花了半個多小時才能寫出來,還是看的提示!!!無向圖,學(xué)數(shù)據(jù)結(jié)構(gòu)時對他就不是很感冒

【編輯推薦】

1. Java連接MySQL中文亂碼處理
2. 在Java應(yīng)用程序中使用Jfreechart配置
3. Java虛擬機內(nèi)部構(gòu)成淺析
4. 淺談Java線程的生命周期
5. 關(guān)于Java繼承的一些復(fù)習(xí)