文書ディレクトリ
アルゴリズム基礎課`データ構造`ソートクイックソート集計ソート二分検索整数浮動小数点数高性能Open 加減法乗除法プレフィックスおよび/差分 1次元 2 2 D ビット演算デュアルポインタ離散化区間合併`データ構造`チェーンテーブルスタックキュー KMP Trieツリーおよび調査セットスタックハッシュ図[ACWing](https://www.acwing.com/blog/content/405/) 図の記憶図の遍歴トポロジ順序図の最短経路図の最小生成ツリー二分図の判別二分図の最大マッチング数学知識動的計画貪欲アルゴリズム向上
アルゴリズムステップ貧乏すぎてテンプレートコードだけ見てみましょうアルゴリズム基礎課
データ構造
ツールバーの
クイックソート
集計ソート
にぶんたんさく
整数
浮動小数点数
高性能操作
加減法
乗除法
接頭辞と差分
1次元
2 D
ビット演算
ダブルポインタ
りさんか
区間マージ
データ構造
チェーンテーブル
シングルダブルスタック
普通/単調キュー
一般/サイクル/単調KMP
Trieツリー
コレクションを調べる
普通改良スタック
ハッシュ
一般/文字列ハッシュ図ACWing
図の記憶
隣接行列(稠密)/隣接テーブル(疎)図の遍歴
DFS/BFS トポロジのソート
有向図について
は、図ノードを1次元配列に並べ替える.
A->B、AはBの前に現れる
パターンに指向性ループがない場合、すなわち、無ループ図(DAG)がある場合にのみ、トポロジーソートは可能であるである.
カリキュラム表を例として:[[1,0],[0,2],[1,3]]は、0カリキュラムが完了した後、1カリキュラムが修了できることを示し、1つの修了の順序を出力する
class Solution {
public:
bool topSort(vector<vector<int>>& G, vector<int>& O, vector<int>& D) {
int N = D.size(), idx = 0;
queue<int> Q;
for (int i = 0; i < N; i++)
if (D[i] == 0) Q.push(i);
while (!Q.empty()) {
int X = Q.front(); Q.pop();
O[idx++] = X;
for (int i = 0; i < G[X].size(); i++) {
int x = G[X][i]; D[x]--;
if (D[x] == 0) Q.push(x);
}
G[X].clear();
}
if (idx == N) return true;
return false;
}
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> inD(numCourses), res(numCourses);
vector<vector<int>> G(numCourses);
for (int i = 0; i < prerequisites.size(); i++) {
G[prerequisites[i][1]].push_back(prerequisites[i][0]);
inD[prerequisites[i][0]]++;
}
if (topSort(G, res, inD)) return res;
return {};
}
};
図の最短パス
Dijkstraアルゴリズムは、素朴でスタック最適化されたものがあり、負の重み( )を処理できない.
Bellman-Ford algorithmアルゴリズムは,負の重みを扱うことができる:最大の違いは,毎回ソース点sから「緩和」更新操作を再開することであり,Dijkstraはソース点から隣接するノードを1つずつ外に拡張し,処理ノードを繰り返すことはなく,Dijkstraの効率が相対的に高いことも分かる.( ) spfaアルゴリズム、キュー最適化BFアルゴリズム、spfaは図中に負のループが存在するかどうかを判断することができる.
floydアルゴリズム、古典的な多源最短経路アルゴリズム図の最小生成ツリー
Primeアルゴリズム:エッジの角度から、エッジ数に依存しないで、貪欲な思想、稠密な図に適しています.
Kruskalアルゴリズム、点の角度から、辺数を依存して、貪欲なアルゴリズム、疎図に適しています
primは点の多い稠密な図に適しており、kruskalは辺の多いものに適している. 二分図の判別
染色法二分図の最大マッチング
ハンガリーアルゴリズム数学の知識
ダイナミックプランニング
欲張る
アルゴリズムの向上
アルゴリズムステップ