古典的なJavaアルゴリズムの筆記試験問題を分析する

Java アルゴリズムプログラムに関する質問:

同社には筆記試験問題が 1 つだけあり、10 分以内に完了する必要があります。

トピックは次のとおりです。1、2、2、3、4、5 の 6 つの数字を使用して、512234、412345 などのさまざまな配置をすべて出力するメイン関数を Java で記述します。要件は、「4」を 3 番目の位置に配置できないことと、「3」と「5」を接続できないことです。

Javaアルゴリズムの基本的な考え方：

1 問題をグラフ構造のトラバーサル問題に縮小します。実際、6 つの数字は 6 つのノードです。6 つのノードを無向接続グラフに接続し、各ノードについてこのグラフのトラバーサルパスを見つけます。すべてのノードのトラバーサルパスは、これらの 6 つの数字の順列と組み合わせの結果セットです。

2 明らかに、この結果セットはまだ質問の要件を満たしていません。次の点を考慮してください。

1. 3 と 5 は接続できません: 実際の要件は、この接続グラフのノード 3 と 5 は接続できないことです。この条件は、グラフ構造を構築するときに満たされ、その後グラフをトラバースできます。

2. 重複なし: 2 が 2 つあることを考慮すると、重複する結果が存在することは明らかです。結果セットを TreeSet に配置して、重複する結果を除外することができます。

3. 4 は 3 番目の位置には存在できません。それでも、結果セット内でこの条件を満たす結果は削除されます。

グラフ構造は 2 次元配列を使用して定義されます。最適なコードは次のとおりです。

 java.util.Iterator をインポートします。
 java.util.TreeSet をインポートします。 
 
パブリッククラスTestQuestion{ 
 
プライベートString[] b =新しいString[]{"1", "2", "2", "3", "4", "5"};
プライベート int n = b .length;
プライベートboolean[]訪問=新しいboolean[n];
訪問済み= false ;
プライベートint[][] a = new int[n][n];
プライベート文字列結果= "" ;
プライベート TreeSet TreeSet = new TreeSet(); 
 
パブリック静的voidメイン(String[] args) {
新しい TestQuestion().start();
 } 
 
プライベートvoid start() {
 (int i = 0 ; i <   n ; i++) {
 (int j = 0 ; j <   n ;j++){
もし（ i == j）{
 0 の場合
} それ以外 {
    1 は 0 です。
 }
 }
 }a[3][5] = 0;
 a[5][3] = 0;
 (int i = 0 ; i <   n ; i++) {
    this.depthFirstSearch(i);
 }
イテレータit = set .iterator();
 (it.hasNext()) の間 {
文字列string = (文字列) it.next(); 
 
 （文字列のインデックスが「4」の場合！= 2）{
 System.out.println(文字列);
 }
 }
 } 
 
プライベートvoid depthFirstSearch(int startIndex) {
訪問[開始インデックス] = true;
結果結果= 結果 + b[開始インデックス];
 （結果の長さ() == n）の場合{
 TreeSet .add(結果);
 }
 for(int j = 0 ; j <   n ;j++){
 a[開始インデックス][j] == 1 && 訪問[j] == falseの場合{
深さ優先検索(j);
 } それ以外 {
続く;
 }
 } 
    結果result = result.substring(0, result.length() -1);
    訪問[開始インデックス] = false;
 }
 }