ネットワークの形で相互に接続されたノード

頂点: ノード

エッジ: エッジ、ノードのペア

重量/コスト

有向グラフ

無向グラフ

隣接行列

隣接リスト

幅優先検索 DFS

深さ優先検索 TFS

幅と深さの優先検索を実装する

グラフがツリーであるかどうかを確認する

グラフ内のエッジの数を数える

2 つの頂点間の最短距離を見つける

別名: プレフィックス ツリー、特別なツリー状のデータ構造

文字列関連の問題を解決するのに非常に効果的です

クイック検索を提供する

辞書で単語を検索する

検索エンジンの自動候補

IPのルーティング

辞書ツリー内の単語の総数をカウントします。

辞書ツリーに保存されているすべての単語を出力します

辞書ツリーを使用して配列内の要素を並べ替える

辞書ツリーを使用して辞書から単語を作成する

T9 辞書の構築: 辞書ツリー DFS

一意に識別されたオブジェクトをキーと値のペアの形式で保存します

ディクショナリ: キーと値のペアのコレクション

キー key を使用してオブジェクトの値を検索する

Java の HashSet/HashMap、C の unowned_map、Python の dict

<br>動作原理: セット用。キーはハッシュ関数を通じてインデックスを取得し、値が配列に格納されます。 <br>get の場合は、キー関数とハッシュ関数を使用してインデックスを検索し、値を取得します。

キーには、文字列、整数、または長さが不明なものを指定できます。したがって、厳密な意味では O(L) を使用するのが適切です。つまり、操作の時間計算量は O(1) ではなく O(keySize) です。<br>

128 ハッシュ関数

衝突とは、2 つの異なるキーがハッシュ関数による計算後に 2 つの同一の値を取得することを意味します。競合を解決するには主に 2 つの方法があります:<br>オープン ハッシュ。これは、ハッシュ テーブルの基になる配列において、各位置がリンク リストの先頭ノードであることを意味します。このようにして、競合する <key, value> タプルが同じリンク リストに配置されます。 <br>クローズドハッシュ。つまり、競合が発生すると、後続の要素は空いたスペースを見つけるために次の位置に移動します<br>

129 リハッシュ

ハッシュ関数

ハッシュテーブルのサイズ

衝突処理方法

配列内の対称キーと値のペアを検索する

問題を解決するためにハッシュ テーブルを柔軟に使用できるでしょうか?

あなたはハッシュ テーブルの基本原理を理解していますか?

便宜上、完全なパスを追跡します

配列が別の配列のサブセットであるかどうかを調べる

指定された配列が互いに素であるかどうかをチェックします

526. ロードバランサ<br>

134. LRU キャッシュ戦略<br>657. 挿入 削除 GetRandom O(1) - 重複は許可されます<br>209. 1 回だけ出現する最初の文字。

データストリームクラスの問題<br>960. ストリーム内の最初の一意の番号 II<br>138. ランダムなポインタを含むリンクリストのコピー<br>171. 124. 最長連続シーケンス

挿入ソート

クイックソート

選択ソート

マージソート

基数ソート

ヒープソート

静的ルックアップテーブル

動的ルックアップテーブル

ハッシュ表

アルゴリズム 1:O(n) lowerBound O(1) 加算

アルゴリズム 2:O(logn) lowerBound O(logn) 加算

一次元配列

二次元配列

多次元配列

サブアレイ

配列間隔の問題

外部ソートの問題

ビット演算

ツリー配列はほとんど考慮されません

増やす

削除削除

インサートインサート、

サイズサイズ

配列内で 2 番目に小さい要素を検索します

最初の非繰り返し整数を検索する

配列内の正の値と負の値を並べ替えます

65. ソートされた 2 つの配列の中央値、難しい問題<br>

6. ソートされた配列のマージ II<br>64. ソートされた配列のマージ<br>839. 2 つのソートされた間隔リストのマージ<br>577. K のソートされた間隔リストのマージ。 2 つの配列<br>548. 2 つの配列の交差 II<br>793. 複数の配列の交差<br>931. K ソートされた配列の中央値<br>149.時間<br>４０５．合計がゼロである部分行列<br>９４３．不変範囲合計クエリー ６６５．

LIFO。例えば、物流の積み込みでは、後から積んだ商品を先に降ろします。

バイナリ ツリーの非再帰的走査、逆ポーランド式の計算などに使用されます。

DFS の非再帰実装の主なデータ構造

幅優先探索 (BFS) では、展開されるノードが記録されます。

キューを使用してメッセージ キューを実装し、非同期タスクを完了できます。

メッセージの生成と消費の速度が一貫していない場合は、送信されたが受信されていないメッセージを一時的に保存するメッセージ キューが必要になります。

要素を格納するにはストレージ構造 (一般的に使用される配列、場合によってはリンクされたリスト) を使用します。

1 つの配列を使用して 3 つのスタックを実装しますか?

2 つのキューを使用してスタックを実装しますか? <br>

違い

演習<br>

プッシュして、要素を上部に挿入します

Pop はスタックの最上位要素を返して削除します

isEmptyスタックは空であり、trueを返します

top は、先頭の要素を削除せずに返します。

Java は、Vector クラスから拡張された java.util.Stack を使用し、push()、pop()、peek()、empty()、search() などの操作をサポートします。

C の場合は、<stack> でスタックを使用するだけです。このメソッドは Java と似ていますが、C の Peak() が top() と呼ばれ、pop() の場合の戻り値が空である点が異なります。

Python、リストを直接使用し、[-1] などのスライス操作を使用してスタックの最上位を表示し、スタックの最上位をポップする場合は list.pop() を使用し、スタックの最上位をプッシュする場合は list.append() を使用します。 。 <br>

スタックを使用して後置式を評価する

スタックの要素を並べ替える

式が括弧内でバランスが取れているかどうかを判断する

FIFO先入れ先出しシーケンシャルストレージ線形データ構造、スーパーマーケットのチェックアウト

BFS アルゴリズムのメイン データ構造として使用されます。

エンキューキューの最後に要素を挿入します

デキューはキューの先頭要素を削除します

isEmpty 列は空であり、true を返します

top はキューの最初の要素を返します

リンクリストを使用してキューを実装しますか?

2 つのスタックを持つキューを実装しますか? <br>

循環配列を使用してキューを実装しますか?

キューを使用してスタックを表す

キューの最初の k 要素を反転します

キューを使用して 1 から n までの 2 進数を生成する

642. データストリームからの移動平均<br>

955. 円形配列によるキューの実装<br>

ノードチェーン: 各ノードにはデータと後続のノードへのポインタが含まれます。

ファイルシステム、ハッシュテーブル、隣接関係リストを実装する

一方向リンクリスト

二重リンクリスト

最後に挿入

頭に挿入

消去

先頭で削除

検索

isEmpty、空です、trueを返します

逆リンクリスト

リンクされたリスト内のサイクルを検出する

リンクされたリストの最後から n 番目のノードを返します。

リンクされたリストから重複を削除する

階層データ構造

頂点とエッジで構成されています

グラフに示されているように、ツリーにはサイクルがありません。

ルート ルートノード

親親ノード

子 子ノード

リーフノード

兄弟 兄弟ノード

N分木

線分ツリーは基本的にテストされておらず、汎用です。

二分木、頻繁にテストされる

二分木の高さを求める

二分探索木で k 番目の最大値を見つける

ルートノードから距離kのノードを見つけます

バイナリ ツリー内の指定されたノードの祖先ノードを検索します。

104. K 個のソートされたリストを結合する<br>