java algorithms implementation

Java：算法和数据结构

算法和数据结构是用Java实现的。

这是我在学术和职业生涯中实现的算法和数据结构的集合。该代码未经过优化，但已编写为正确且可读的。算法和数据结构经过测试，除非另有说明，否则被认为是正确的。

由贾斯汀·韦瑟雷尔创建

• 对于问题，请使用：http://groups.google.com/forum/#!forum/java-algorithms-implementation
• 谷歌：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）算法 - 每个前缀的最大前缀后缀长度

字符串旋转

• 按字典顺序查找最小字符串旋转
• 按字典顺序查找最大字符串旋转