java algorithms implementation

Java : アルゴリズムとデータ構造

アルゴリズムとデータ構造は Java で実装されます。

これは、私が学業と職業生活の中で実装したアルゴリズムとデータ構造のコレクションです。コードは最適化されていませんが、正しく読みやすいように書かれています。アルゴリズムとデータ構造はテストされており、特に記載がない限り、正しいと考えられます。

作成者: ジャスティン・ウェザレル

• 質問については、http://groups.google.com/forum/#!forum/java-algorithms-implementation を使用してください。
• Google: http://code.google.com/p/java-algorithms-implementation
• Github: http://github.com/phishman3579/java-algorithms-implementation
• LinkedIn: http://www.linkedin.com/in/phishman3579
• 電子メール: [email protected]
• Twitter: http://twitter.com/phishman3579

寄付で私をサポートしてください

実装された内容:

目次

• データ構造
• 数学
• 数字
• グラフ
• 検索
• シーケンス
• ソート
• 文字列関数

データ構造

• AVL ツリー
• B ツリー
• バイナリ ヒープ (配列またはツリーによってバックアップされる)
• 二分探索木
• コンパクト・サフィックス・トライ (パトリシア・トライによるバック)
• 素集合
• フェンウィック ツリー {バイナリ インデックス ツリー (BIT)}
• グラフ
  • 無指向性
  • 監督（ディグラフ）
• ハッシュ配列マップトトライ (HAMT)
• ハッシュマップ（連想配列）
• インターバルツリー
• 暗黙的なキー トレプ
• KD ツリー (k 次元ツリーまたは kd ツリー)
• リスト [配列またはリンクされたリストに基づく]
• LCP 配列 (最長共通プレフィックス) [サフィックス配列によってサポートされる]
• マトリックス
• パトリシア・トリー
• クアッドツリー (ポイント領域または MX-CIF)
• キュー [配列またはリンク リストに基づく]
• Radix Trie (連想配列) [Patricia Trie をサポート]
• 赤黒の木
• セグメントツリー
• スキップリスト
• スプレーツリー
• スタック [配列またはリンクされたリストに基づく]
• サフィックス配列
• サフィックス ツリー (ウッコネンのアルゴリズム)
• サフィックス Trie [Trie による裏付け]
• 三分探索ツリー
• トレプ
• 木
• ツリー マップ (連想配列) [AVL ツリーをサポート]
• トライ
• Trie Map (連想配列) [Trie による裏付け]

数学

• 距離
  • チェビシェフ
  • ユークリッド
• 分割
  • ループを使って
  • 再帰を使用する
  • シフトと乗算を使用する
  • シフトだけを使って
  • 対数を使用する
• 乗算
  • ループを使って
  • 再帰を使用する
  • シフトだけを使って
  • 対数を使用する
  • 高速フーリエ変換
• べき乗
  • 再帰的累乗
  • 高速再帰累乗
  • 高速モジュラー再帰累乗
• 素数
  • プライムです
  • 素因数分解
  • エラトステネスのふるい
  • ミラー・ラビンテスト
  • Co-Primes (相対素、相互素)
  • 最大公約数
    • Euclid のアルゴリズムを使用する
    • 再帰を使用する
• 順列
  • 文字列
  • 数字
• モジュラー演算
  • 追加
  • 引き算
  • 乗算する
  • 分ける
  • 力
• ナップザック
• ラマー・ダグラス・ペッカー

数字

• 整数
  • バイナリ文字列へ
    • 除算と剰余を使用する
    • 右シフトとモジュラスを使用する
    • BigDecimal を使用する
    • 除算と倍精度を使用する
  • は 2 の累乗です
    • ループを使って
    • 再帰を使用する
    • 対数を使用する
    • ビットを使って
  • 英語へ (例: 1 は「one」を返します)
• ロング
  • バイナリ文字列へ
    • 除算と剰余を使用する
    • 右シフトとモジュラスを使用する
    • BigDecimal を使用する
• 複雑な
  • 追加
  • 引き算
  • 乗算
  • 絶対値
  • 極値

グラフ

• グラフ内の開始頂点からの最短パスを検索します。
  • ダイクストラのアルゴリズム (非負の重みグラフ)
  • Bellman-Ford アルゴリズム (負および正の重みグラフ)
• 最小スパニングツリーを見つける
  • プリム (無向グラフ)
  • クラスカルのグラフ (無向グラフ)
• すべてのペアの最短経路を見つける
  • Johnsons のアルゴリズム (負および正の重みグラフ)
  • フロイド-ウォーシャル (負および正の体重グラフ)
• 周期検出
  • 訪問した頂点を追跡しながら深さ優先検索を行う
  • 接続されたコンポーネント
• トポロジカルソート
• A* 経路探索アルゴリズム
• 最大流量
  • プッシュ再ラベル
• グラフトラバーサル
  • 深さ優先トラバーサル
  • 幅優先トラバーサル
• エドモンズ・カープ
• マッチング
  • ターボマッチング
• ツリー内の最下位共通祖先

検索

• 配列内の値のインデックスを取得する
  • リニア
  • クイック選択
  • バイナリ [ソートされた配列入力のみ]
  • 下限 [ソートされた配列入力のみ]
  • 上限 [ソートされた配列入力のみ]
  • 最適化されたバイナリ (しきい値まではバイナリ、その後は線形) [ソートされた配列入力のみ]
  • 補間 [ソートされた配列入力のみ]

シーケンス

• 最長の共通部分列を見つける (動的計画法)
• 最長の増加部分列を見つける (動的計画法)
• シーケンス内でサブシーケンスが出現する回数を求める (動的計画法)
• フィボナッチ数列の i 番目の要素を見つける
  • ループを使って
  • 再帰を使用する
  • 行列乗算を使用する
  • ビネーの公式を使うと
• シーケンス内のすべての要素の合計を求める(等差数列)
  • ループを使って
  • 三角数を使う
• 連続する部分配列の最大合計 (Kadane のアルゴリズム)
• 最長の回文部分列 (動的計画法)

ソート

• アメリカの国旗の並べ替え
• バブルソート
• カウンティングソート (整数のみ)
• ヒープソート
• 挿入ソート
• マージソート
• クイックソート
• 基数ソート (整数のみ)
• シェルズソート

文字列関数

文字列関数

• 文字列内の文字を反転する
  • 追加のストレージ (String または StringBuilder) を使用する
  • インプレーススワップを使用する
  • インプレース XOR を使用する
• 文字列内の単語を反転する
  • 文字スワップと追加ストレージ (StringBuilder) を使用する
  • StringTokenizer と追加の (文字列) を使用する
  • Split() メソッドと追加のストレージ (StringBuilder と String[]) を使用する
  • インプレーススワップを使用する
• 回文です
  • 追加のストレージ (StringBuilder) を使用する
  • インプレース対称要素比較の使用
• 文字列内の文字のサブセット
• 編集 (レーベンシュタイン) 2 つの文字列の距離 (再帰的、反復的)

Manacher のアルゴリズム (最長の回文を見つける)

KMP (Knuth-Morris-Pratt) アルゴリズム - 各プレフィックスの最大のプレフィックスとサフィックスの長さ

文字列の回転

• 辞書編集上最小限の文字列ローテーションで検索します
• 辞書編集上の最大の文字列ローテーションで検索します