Skip to content

README.md

Latest commit

 

History

History
101 lines (79 loc) · 4.06 KB

README.md

File metadata and controls

101 lines (79 loc) · 4.06 KB

Data Structures & Algorithms (Java)

使用 Java 从零实现常用数据结构与算法，并配套 LeetCode 题解。

项目结构

src/com/
├── ds_algo/       # 数据结构与算法的完整实现
├── leetcode/      # LeetCode 题解（按专题分类）
└── tool/          # 工具类（二叉树打印、断言、随机数组生成、计时等）

数据结构实现

每个模块独立成包，包含完整实现与测试入口（Main / Test*Main）。

包名 数据结构 核心内容
a_complexity 复杂度分析 时间复杂度示例
b_arrayList 动态数组 自动扩容、缩容
c_linkList 链表 单向链表、双向链表、单向循环链表、双向循环链表
d_stack 栈 基于链表实现
e_queue 队列 普通队列、双端队列、循环队列、循环双端队列
f_BST 二叉搜索树 BinaryTree → BST → BBST 继承体系，前/中/后/层序遍历
g_AVLTree AVL 树 继承 BBST，左旋/右旋自平衡
h_RBTree 红黑树 继承 BBST，含 B 树实现
i_set 集合 ListSet（链表实现）、TreeSet（红黑树实现）
j_map 映射 TreeMap（红黑树实现）
k_hashTable 哈希表 HashMap（红黑树解决冲突）、LinkedHashMap、HashSet、LinkedHashSet
l_heap 堆 二叉堆（最大堆 / 最小堆）、批量建堆
m_priorityQueue 优先级队列 基于二叉堆实现
n_haffumanCode 哈夫曼编码 哈夫曼树构建与编码
o_trie 字典树 (Trie) 前缀匹配、搜索
p_unionFind 并查集 Quick Find → Quick Union → 按 Size/Rank 优化 → 路径压缩/路径分裂/路径减半，泛型并查集
q_graph 图 邻接表实现，BFS、DFS、拓扑排序、Prim、Kruskal、Dijkstra、Bellman-Ford、Floyd
z_sorts 排序算法 见下方排序算法表

排序算法

分类 算法
比较排序 冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序、堆排序
非比较排序 计数排序、基数排序、桶排序

排序基于抽象类 Sort<T> 实现，内置比较次数、交换次数和耗时统计，可通过 SortFactory 进行多种排序算法的性能对比。

树的继承体系

BinaryTree<E>
  └── BST<E>              // 二叉搜索树
        └── BBST<E>        // 平衡二叉搜索树（抽象）
              ├── AVLTree<E>
              └── RBTree<E>

并查集优化演进

UnionFind_QF          Quick Find
UnionFind_QU          Quick Union
UnionFind_QU_Size     基于 Size 优化
UnionFind_QU_Rank     基于 Rank 优化
UnionFind_QU_Rank_PC  路径压缩 (Path Compression)
UnionFind_QU_Rank_PH  路径减半 (Path Halving)
UnionFind_QU_Rank_PS  路径分裂 (Path Splitting)
UnionFindGeneric<V>   泛型并查集

LeetCode 题解

按专题分类，共 90+ 道题目：

专题 题目数 示例题目
链表 20+ 反转链表、合并有序链表、环形链表、回文链表、合并K个有序链表
二叉树 14+ 前中后序遍历（递归/非递归/Morris）、构造二叉树、验证BST、最大BST子树
DFS / 回溯 20+ 全排列、子集、组合总和、N皇后、括号生成、单词搜索
动态规划 17+ 零钱兑换、最长公共子序列、最长上升子序列、买卖股票、打家劫舍、最长回文串
数组 5 合并有序数组、颜色分类、最大间距
栈 2 有效括号、用栈实现队列
队列 1 用队列实现栈
优先队列 3 数组中第K大元素、前K个高频元素
图 2 课程表（拓扑排序）

运行方式

项目为纯 Java 源码，无需构建工具，直接编译运行：

cd src
javac com/ds_algo/z_sorts/TestMain.java
java com.ds_algo.z_sorts.TestMain

每个数据结构包下的 Main 或 Test*Main 类均可作为独立入口运行。

License

LICENSE