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
• 領英：http://www.linkedin.com/in/phishman3579
• 電子郵件：[email protected]
• 推特：http://twitter.com/phishman3579

透過捐款支持我

已實施的內容：

目錄

• 資料結構
• 數學
• 數位
• 圖表
• 搜尋
• 序列
• 排序
• 字串函數

資料結構

• AVL樹
• B樹
• 二元堆（由數組或樹支援）
• 二元搜尋樹
• 緊湊後綴特里樹（由帕特里夏特里樹支持）
• 不相交集
• Fenwick 樹 {二元索引樹 (BIT)}
• 圖形
  • 無向
  • 定向（有向圖）
• 哈希數組映射特里樹 (HAMT)
• 哈希映射（關聯數組）
• 區間樹
• 隱式密鑰陷阱
• KD Tree（k維樹或kd樹）
• 列表[由數組或鍊錶支援]
• LCP 數組（最長公共前綴）[由後綴數組支援]
• 矩陣
• 帕特里夏·特里
• 四叉樹（點區域或 MX-CIF）
• 隊列[由數組或鍊錶支援]
• Radix Trie（關聯數組）[由 Patricia Trie 支援]
• 紅黑樹
• 線段樹
• 跳過列表
• 八字樹
• 堆疊[由數組或鍊錶支援]
• 後綴數組
• 後綴樹（Ukkonen 演算法）
• 後綴 Trie [由 Trie 支持]
• 三元搜尋樹
• 崔普
• 樹
• 樹圖（關聯數組）[由 AVL 樹支援]
• 特里樹
• Trie Map（關聯數組）[由 Trie 支援]

數學

• 距離
  • 切比雪夫
  • 歐幾裡得的
• 分配
  • 使用循環
  • 使用遞迴
  • 使用移位和乘法
  • 僅使用輪班
  • 使用對數
• 乘法
  • 使用循環
  • 使用遞迴
  • 僅使用輪班
  • 使用對數
  • 快速傅立葉變換
• 求冪
  • 遞迴求冪
  • 快速遞歸求冪
  • 快速模遞歸求冪
• 質數
  • 是質數
  • 質因數分解
  • 埃拉托斯特尼篩
  • 米勒-拉賓檢驗
  • 互質（互質、互質）
  • 最大公約數
    • 使用歐幾裡得演算法
    • 使用遞迴
• 排列
  • 字串
  • 數位
• 模運算
  • 添加
  • 減去
  • 乘
  • 劃分
  • 力量
• 背包
• 拉默·道格拉斯·普克

數位

• 整數
  • 到二進位字串
    • 使用除法和模數
    • 使用右移和模數
    • 使用 BigDecimal
    • 使用除法和雙精確度
  • 是2的冪
    • 使用循環
    • 使用遞迴
    • 使用對數
    • 使用位
  • 轉換為英語（例如 1 將返回“one”）
• 長頭
  • 到二進位字串
    • 使用除法和模數
    • 使用右移和模數
    • 使用 BigDecimal
• 複雜的
  • 添加
  • 減法
  • 乘法
  • 絕對值
  • 極端值

圖表

• 尋找圖中從起始頂點開始的最短路徑
  • Dijkstra 演算法（非負權重圖）
  • Bellman-Ford 演算法（負權重圖與正權重圖）
• 找到最小生成樹
  • Prim 的（無向圖）
  • 克魯斯卡爾（Kruskal）（無向圖）
• 找到所有對的最短路徑
  • 約翰遜演算法（負權重圖和正權重圖）
  • Floyd-Warshall（負權重圖與正權重圖）
• 循環檢測
  • 深度優先搜索，同時追蹤訪問過的頂點
  • 連接組件
• 拓撲排序
• A*尋路演算法
• 最大流量
  • 推式重新標記
• 圖表遍歷
  • 深度優先遍歷
  • 廣度優先遍歷
• 埃德蒙茲·卡普
• 匹配
  • 渦輪匹配
• 樹中最低的共同祖先

搜尋

• 取得數組中值的索引
  • 線性
  • 快速選擇
  • 二進位[僅限排序數組輸入]
  • 下界[僅限排序數組輸入]
  • 上限[僅限排序數組輸入]
  • 最佳化二進位（二進位直到閾值然後線性）[僅限排序數組輸入]
  • 插值[僅限排序數組輸入]

序列

• 求最長公共子序列（動態規劃）
• 找出最長遞增子序列（動態規劃）
• 找出序列中子序列出現的次數（動態規劃）
• 尋找斐波那契數列中的第 i 個元素
  • 使用循環
  • 使用遞迴
  • 使用矩陣乘法
  • 使用比奈公式
• 求數列中所有元素的總和（算術級數）
  • 使用循環
  • 使用三角數
• 連續子數組的最大和（Kadane 演算法）
• 最長回文子序列（動態規劃）

排序

• 美國國旗排序
• 冒泡排序
• 計數排序（僅限整數）
• 堆排序
• 插入排序
• 歸併排序
• 快速排序
• 基數排序（僅限整數）
• 殼牌排序

字串函數

字串函數

• 反轉字串中的字符
  • 使用額外的存儲（String 或 StringBuilder）
  • 使用就地交換
  • 使用就地異或
• 反轉字串中的單字
  • 使用字元交換和附加儲存（StringBuilder）
  • 使用 StringTokenizer 和附加（字串）
  • 使用 split() 方法和附加儲存（StringBuilder 和 String[]）
  • 使用就地交換
• 是回文
  • 使用額外的存儲（StringBuilder）
  • 使用就地對稱元素比較
• 字串中的字元子集
• 編輯（Levenshtein）兩個字串的距離（遞歸、迭代）

Manacher 演算法（找出最長的回文）

KMP（Knuth–Morris–Pratt）演算法 - 每個前綴的最大前綴後綴長度

字串旋轉

• 按字典順序查找最小字串旋轉
• 按字典順序查找最大字串旋轉