問題タブ [array-algorithms]

私はサフィックスの範囲を構築しようとしています

文字列があれば"catalog""catalyst" "ban" "bany"

すると接尾辞木は次のようになります

各文字列のサフィックス範囲を今すぐ見つけたいと思います。文字列「Cat」を取得すると、「cat」がプレフィックスであるすべてのサフィックスを囲む範囲が得られるはずです。各文字列を区切るためにセンチネルを使用する必要があります..「$」の場合があります

誰かがc++を使用してこれを見つけるための最良の方法を私に提案できますか？どんな参考文献も役に立ちます。ありがとうございました

アプリケーションでは、パターンの多くの2D座標（x、y）を測定します。このパターンは、xおよびy方向に固定ピッチのグリッド上のポイントのセットで構成されています。これらの座標にはすべて品質のスコアがあり、このスコアに基づいて並べ替えられます。私がやりたいのは、最初にこれらの座標をxで並べ替え、一緒に属するx座標のグループ（領域）を定義することです。このステップの後、y領域のさまざまなx領域を並べ替えたいと思います。

この後、対応するパターン（グリッド）ラベルに座標にラベルを付けることができます。

例：測定された座標（x、y）=（2,2）、（2,3）、（1,2）、（1,3）、（2,1）、（1,1）、（3,2 ）、（3,3）、（3、1）

ステップ1の後：（x、y）=（1,2）、（1,3）、（1,1）（2,2）、（2,3）、（2,1）（3,2）、 （3,3）、（3,1）

ステップ2の後：（x、y）=（1,1）、（1,2）、（1,3）、（2,1）、（2,2）、（2,3）、（3,1 ）、（3,2）、（3、3）

このタスクをすでに実行しているソートルーチンはありますか？パターンの一部の座標が測定されない場合にも、ルーチンは機能するはずです。

誰かが私にいくつかの手がかりを与えることができますか、私は経験豊富なc ++プログラマーではありませんが、おそらくいくつかのヒントがあれば私は仕事をすることができます！

n個のリストを比較し、すべてのリストに表示されないすべての値を返すメソッドを作成する最も効率的な方法は何ですか。

となることによって

lists.GetNonShared（）;

1、5、8、9、10を返します

私は持っていた

しかし、それが効率的かどうかはわかりませんでした。順序は関係ありません。ありがとう！

試験の準備中にこの問題が発生しました。

数値a1、...、anおよびb1、....、bnの2つの配列が与えられ、各数値は0または1であり、、ai + ai + 1のような最大スパン（i、j）を見つけるための最速のアルゴリズム+ .... + aj = bi + bi + 1 + ....+bjまたはそのようなスパンがないことを報告します。

（A）ハッシュが許可されている場合、O（3 ^ n）およびomega（2 ^ n）の時間がかかります。

（B）キー比較モードでO（n ^ 3）とomega（n ^ 2.5）と時間を取ります

（C）シータ（n）の時間とスペースを取ります

（D）2n個の要素の合計が偶数の場合にのみO（平方根（n））の時間がかかります。

出来ますか？そうでない場合、サイズnの配列が与えられた場合、配列を並べ替える方がよいかどうかをどのように知ることができますか？

2 つの要素がペアになっていない n=2k+2 要素の配列があります。8 つの要素の配列の例: 1 2 3 47 3 1 2 0. "47" と "0" は配列内でペアになっていません。ペアになっていない要素が 1 つしかない配列がある場合、この問題は XOR で解決します。しかし、私は 2 つの不対要素を持っています! 私に何ができる？解決策は、O(n) 時間のパフォーマンスと O(1) の追加メモリです。

3x3 グリッドを想像してください:

パーセンテージ%は、空きスペース/位置を表します。

行は、最初の行の構成の順列が次のいずれかになるように、文字列のビーズのように移動できます。

2行目も同様。3 番目の行には空のスロットが含まれていないため、変更できません。

各行の可能な順列を考慮して、可能なすべてのグリッドを作成しようとしています。

出力は次のグリッドを生成する必要があります。

各行を調べてスペースを左右にシフトし、それから新しいグリッドを生成して再帰する方法を試しました。すべてのグリッドをセットに保持し、無限再帰を防ぐために、まだ調査されていない位置のみを生成するようにします。

ただし、私のアルゴリズムは非常に非効率的 (順列ごとに ~1 秒!!) のようで、見栄えもよくありません。これを行う雄弁な方法があるかどうか疑問に思っていましたか？特にパイソンでは。

私には漠然としたアイデアがいくつかありますが、見落としている短くて簡単な方法があると確信しています。

編集: 3x3 は単なる例です。グリッドは任意のサイズにすることができ、重要なのは行の組み合わせです。例えば：

も有効なグリッドです。

編集 2:文字は順序を維持する必要があります。たとえば[A, %, B] != [B, %, A]、[B, A, %]有効ではありません

インタビューで、2 次元配列を O(n) 時間でソートすることについて質問されました。O(n) 時間でそれを行うにはどうすればよいですか。誰かがそれに光を当てることができますか..ありがとう.

入力：

出力

リストの値にある程度の「近さ」があるかどうかを確認したい。これを行うための適切なアルゴリズムはありますか? 最もpythonicな方法のボーナスポイント。

有効

有効ではありません

長い質問になりますが、深呼吸してから読んでください。

1 次元配列のインデックスを多次元配列のベクトル インデックスに変換する最速のアルゴリズムを理解したいと思います。

なぜそれが必要なのかを理解するために、例を見てみましょう。

私は 2 次元配列を持っています: Array[i1][i2]

i1 は i1_b=0 から i1_e=2 まで実行されます

i2 は i2_b=0 から i2_e=1 まで実行されます

したがって、この配列はファイルに 1 行ずつ出力されます。

配列[0][0]

配列[0][1]

配列[0][2]

配列[1][0]

配列[1][1]

配列[1][2]

ここで、ファイルを 1 行ずつ読み取ります。インデックス k は、最後に読み取られる行の番号です。

Array[0][0] と k=0 である最初の行を読みました

Array[0][1] と k=1 である 2 行目を読みました

...

k は k_b=0 から k_e=5 までで、

k=0 は i1=0、i2=0 に対応します

k=1 は i1=0、i2=1 に対応します

...

問題: だから私の問題は、k を i1 と i2 に最速で変換する方法ですか? （ファイルの読み取り中は必要ありませんが、後でプログラムで必要です）

この例では、ソリューションの 1 つが次のようになります。

i1=k/(i1_e - i1_b + 1);

i2=k%(i1_e - i1_b + 1);

質問 1: サイクルとコンピューター時間の点で最速のソリューションですか?

わかった。質問 2: このアルゴリズムを多次元配列に一般化するにはどうすればよいですか?

配列[i1][i2][i3][i4]

i1=k/(i1_e - i1_b + 1);

i2=k%(i1_e - i1_b + 1);

i3=i2/(i1_e - i1_b + 1);

i4=i2%(i1_e - i1_b + 1);

質問 3: それが最速の方法ですか?

質問 4: 関連する質問は、剰余除算、整数除算、整数の加算、および整数の乗算のレイテンシはどのくらいですか? これらの数値がアーキテクチャに依存する場合は、私にも知らせてください。

前もって感謝します！

PS この問題を、秒を日-時-分-秒に変換する最速のアルゴリズムと考える方が簡単かもしれません。