ここで パターン を鍛えよう。
練習 は LeetCode で。
私たちは問題集ではありません。 問題を読む から 型が見える までの距離を、何時間から数分に縮めます — インタラクティブなアニメーションで 考え方そのものを教えます。文法ではなく。
ファミリー · 3 サブパターン
ツー ポインタ
同じ列上を 2 つの添字が動いて不変条件を保つ — 収束、速い/遅い、スライディングウィンドウの 3 つ。
収束 · 速い/遅い · 窓
単独
二分探索の バリエーション
境界条件はこの分野で最も解決されていない教育上の課題。
3 バリエーション · O(log n)
単独
バックトラッキング
決定木の展開 — アニメーションで理解するのに最も適した構造。
分岐する状態機械
単独
単調 スタック
スタックの状態遷移はコード上では見えないが、アニメーションでは劇的に見える — スタックが主役。
次に大きい要素 · ヒストグラム
第 2 段階
グリッド上の BFS / DFS
キューは幅優先、スタックは深さ優先 — 同じアルゴリズム、2 つの順序。
キュー · スタック · 塗りつぶし
ファミリー · 3 サブパターン
ヒープと 優先度付きキュー
極値(最小・最大)へ安価にアクセスでき、残りはゆるい半順序のまま。3 つのサブパターン:Top-K、2 本のヒープ、K 路マージ。
Top-K · 2 本のヒープ · K 路マージ
第 2 段階
木の 走査
どの走査も各ノードを 1 回ずつ訪問する — 違うのは子の再帰に対するタイミングだけ。
前順 · 中順 · 後順 · 階層順
第 2 段階
連結リストの その場操作
3 本のポインタ — prev、curr、next — があれば、末尾を失わずに連結リストをその場で書き換えられる。
反転 · マージ · 並び替え
ファミリー · 5 サブパターン
動的 計画法
表が 1 マスずつ自身を埋めていき、各マスは定数個の以前のマスから合成される。5 つのサブパターン。
1 次元 · 2 次元 · ナップサック · 区間 · 状態機械
単独 · 第 3 段階
Union Find
N 要素を互いに素な成分に分割して保つ — 2 つの成分をほぼ定数時間でマージし、森はクエリのたびに自身を平坦化する。
連結成分 · O(α(N))
単独 · 第 3 段階
トライ
文字の木の上に文字列集合を格納する — 共通接頭辞を持つ単語はパスを共有し、「単語の終わり」フラグが格納済みの単語と途中の接頭辞を区別する。
接頭辞クエリ · 自動補完 · 単語探索
単独 · 第 3 段階
トポロジカル ソート
有向非巡回グラフを、すべての辺が左から右を向くように線形化する — 各ノードは前提がすべて去った後にのみ列に入る。
Kahn のアルゴリズム · O(V + E) · 循環検出
ファミリー · 4 サブパターン
累積 和
最初に O(N) かけることで、以後の区間クエリはすべて O(1) に償却される — 逆に使えば、区間更新も安価にできる。4 つのサブパターン。
1 次元 · 2 次元 · 差分 · ハッシュ
ファミリー · 4 サブパターン
最短 経路
始点から各ノードへの最短距離を求める — 仕組みは「辺が何を運ぶか」で分岐する。等コストは BFS、非負重みは Dijkstra、負を許すなら Bellman-Ford、全点対は Floyd-Warshall。
BFS · Dijkstra · Bellman-Ford · Floyd-Warshall
単独
区間 マージ
始点でソートしてから線形に走査する — 各区間は現在のマージ区間を右に伸ばすか、それを確定して新しいマージを始めるかのどちらか。パターンの全体はこの 1 つの比較に収まる。
ソート + 線形走査 · O(N log N)
単独
ビット 演算
整数を「値」ではなく「ビットの並び」として見る — 同じ数を XOR すれば 0 になり、0 を XOR すれば変わらない。難しいのは、問題の中に隠れたビットレベルの構造を見抜くこと。
XOR · ビットマスク · O(N)
ファミリー · 2 サブパターン
巡回 ソート
値が [0, N] や [1, N] に収まるとき、添字そのものがポインタになる — 各要素が自分の家を知っている。家へスワップするか符号反転で「見た」を記録するかで、欠損 / 重複の一連の問題が O(N) 時間・O(1) 空間に落ちる。
添字をポインタとして · O(N)
単独
スイープ ライン
各区間を始点 +1、終点 −1 の 2 イベントに分解し、位置でソートして走査する。実行中のアクティブ数が増減し — そのピークが「同時最大」型問題の答えになる。
端点イベント · 走行ピーク · O(N log N)