3

インタビューでこんな質問をされました。順序付けられた辞書があり、順序付けられていない文字のリストが与えられたとします。これらの文字をどのように優先順位付けしますか? この辞書には、26 文字すべての出現が保証されている単語が含まれています。ただし、ディクショナリのサイズはいくらでもよいことに注意してください。ディクショナリは数語程度の小ささで、文字ごとに個別のセクションがない場合があります。たとえば、a;で始まる単語のセクションがない場合があります。ただしa、「bat」などの別の単語の一部として表示されます。

辞書は、「zebra」、「apple」、「cat」、「crass」のように「順序付け」(/皮肉) される可能性があり、リスト { a, z, r} が与えられた場合、正しい順序は { z, a, になります。 r}. 辞書では "zebra" が "apple" の前にあるので、前置詞zが前aにあることがわかります. "apple" が "cat" の前にあるので、a前にあることがわかりますc. "cat" が "crass" の前にあるので、私たちは知っています.この順序はandがあいまいな前置詞で残されますが、文字のリストが { a, , }だったので、解決策は { , , } であることがわかります。rcrazrzar

4

3 に答える 3

11

26 個の頂点を持つ有向グラフを使用します。各頂点は文字を表します。頂点 A から頂点 B へのエッジは、アルファベットで B が A の前にあることを意味します。

最初のステップは、頂点のみでエッジのないこのようなグラフを確立することです。

次に、入力辞書を単語ごとにスキャンします。そして、各単語を前の単語と比較します。スキャンした単語ごとに正確に 1 つの関係を見つける必要があります。したがって、このグラフにエッジを追加します。辞書が正しいと仮定すると、競合はないはずです。

辞書を完成させたら、アルファベットを次のように出力します。

  1. ランダムな頂点を選択し、何も指していない文字が 1 つ見つかるまでそのパスをトラバースします。これはアルファベットの最初の文字です。出力してグラフから削除します。
  2. すべての頂点が削除されるまで 1 を続けます。

編集: このアルゴリズムをよりよく説明するために、サンプル入力で実行してみましょう。

入力: {"zebra', "apple", "cat", "crass"}

単語 0 と単語 1、z が a の前にあることがすぐにわかるので、エッジ a->z を作成します

単語 1 と単語 2、a が c の前に来ることがすぐにわかるので、別のエッジ c->a を作成します。

単語 2 と単語 3、最初の文字は同じ "c" ですが、2 番目の文字は異なります。したがって、a が r の前に来ることがわかり、別のエッジ r->a が得られます。

これですべての単語が読み上げられます。頂点をランダムに選択して順序を出力すると (c を選択するとします)、グラフに c->a->z があります。z を出力し、グラフから z を削除します (NULL としてマークします)。ここで別のものを選択すると (たとえば、r を選択するとします)、グラフで r->a が見つかります。a を出力し、グラフから a を削除します。今度は別のものを選択します (たとえば、もう一度 c を選択するとします)。パスが見つからないので、c を出力して削除します。ここで、最後の r を選択します。これもパスがないため、r を出力して削除します。すべての頂点が削除されたので、アルゴリズムは完了です。

出力は z、a、c、r です。"c" と "r" の順序はランダムです。これは、入力からそれらの関係が実際にはわからないためです。

于 2012-04-24T20:45:22.900 に答える
1

"zebra' < "apple" < "cat" < "crass" という事実から、文字ごとの関係を導出する最も効率的な方法は、ループですべての単語の N 番目の文字を考慮することです。ここで、N は最初は 0 です。関係 "z" < "a" < "c". そのループは、同じ接頭辞を持つ単語のグループの (N + 1) 番目の文字の関係を再帰的に抽出できます (つまり、位置 <= N のテキスト)。 N == 1 で同じ接頭辞の "cat" と "crass" を使用すると、関係 "a" < "r" が得られます。

x < y既知の関係は、真理値の 2 次元配列で表すことができます。

y\x a b c...r...z
a   -   N   N   Y
b     -
c   Y   -       Y
r   Y       -
z   N   N       -

強引なアプローチは、入力リスト内の文字のすべてのペア (つまり、{a, z, r} -> az, ar, zr) を反復処理して、 , をテーブルで検索することa<zですa<r:z<rこれが false の場合は、文字とシーバン全体を再起動します。これ以上文字を入れ替えずにプロセス全体を完了すると、出力は規則に従って一貫してソートされます。これは、バブルソートを行うのと少し似ています。

これを高速化するために、テーブル内のセルに暗黙の関係を設定することについて、より積極的に行うことができます。たとえば、"z" < "a" < "c" および "a" < "r" を知っているので、" z" < "r". 上記の「単純な」表を実行して、各文字 (たとえば、それと ) について知っていることをすべて見つけてから、a と c について知っていることを実行することで、これを行うことができz<aますz<c。ツリーが過度に深くならないようにするには、このように 1 レベルの間接化をたどり、テーブルが安定するまで繰り返します。

于 2012-04-25T08:44:00.410 に答える
-3

問題の説明方法に基づいて、あなたの例は正しくありません。あなたの答えは です{z,r,a}。ただし、以下は問題を解決するコードです。私の想定とは異なる注文を返すように変更できます{z,r,a}。

Set<Character> charPrecedence(List<String> dictionary, char[] letters){
    Set<Character> result = new HashSet<Character>();
    //since your characters are the 26 letters instead of the 256 chars
    // a bit vector won't do; you need a map or set
    Set<Character> alphabets = new HashSet<Character>();
    for(char c: letters)
       alphabets.add(c);

    //now get to work
    for(String word: dictionary){
       if(alphabets.isEmpty()) return result;
       for(char c: word.toCharArray()){
          if(alphabets.remove(c))
           result.add(c);
       }
    }
    //since the dictionary is guaranteed to contain all the 26 letters,
    //per the problem statement, then at this point your work is done.
    return result;
}

最良のケース O(1); 最悪の場合 O(n) ここで、n は辞書内の文字数です。つまり、1 つの特定の文字が 1 回だけ表示され、チェックする最後の文字です。

于 2012-04-24T23:15:16.360 に答える