Java 数据结构与算法学习仓库

按课本体系手写实现 Java 版数据结构与算法，并配合 LeetCode和Luogu 例题练习 目标：理解原理、能手写实现、能分析复杂度、能映射到题目

---

✨ 技术栈

---

📚 学习路线（对应课本目录）

一、初识算法

• 二分查找：基础版 / 改变版
• 衡量算法好坏
• 再看二分查找：平衡版 / Java 版 / Leftmost & Rightmost
• 时间复杂度估算
• 耗时估算
• LeetCode 704 二分查找
• LeetCode 35 搜索插入位置
• LeetCode 34 搜索开始结束位置
• 递归基础
• 单路递归 / 多路递归
• 递归优化：记忆法、尾递归、复杂度、Master 定理

二、基础数据结构

2.1 数组

• 概述
• 动态数组
• 二维数组
• 局部性原理
• 越界检查
• LeetCode 88 合并有序数组

2.2 链表

• 单向链表
• 单向链表（带哨兵）
• 双向链表（带哨兵）
• 环形链表（带哨兵）
• LeetCode 206 / 203 / 19 / 83 / 82 / 21 / 23 / 876 / 234 / 141 / 142 / 237 / 160

2.3 栈 / 队列 / 双端队列 / 优先队列 / 阻塞队列

• 栈：概述、链表实现、数组实现、应用
• LeetCode 20 / 120 / 232 / 225 / 150 / 70 / 103 / 641
• 队列 / 双端队列
• 优先队列 / 堆
• 阻塞队列
• LeetCode 215 / 703 / 295 / 23 / 1138

2.4 树

• 二叉树：存储、遍历、BFS、DFS
• LeetCode 102 / 144 / 94 / 145 / 101 / 111 / 226 / 236 / 105 / 106
• 二叉搜索树（BST）
• AVL 树
• 红黑树
• B 树 / B+ 树概念
• LeetCode 450 / 701 / 700 / 98 / 938 / 1008 / 235

2.5 哈希表

• 第一版、hashCode、冲突与思考
• LeetCode 1 / 3 / 49 / 217 / 136 / 242 / 387 / 347 / 164 / 912 / 148

---

三、基础算法

• 查找：线性查找、二分查找、哈希查找
• 排序：冒泡、选择、堆排、插入、希尔、归并、快排、计数、桶、基数
• LeetCode 排序 / TopK / 数据流中位数
• 图：概念、BFS、DFS、拓扑排序、最短路径、最小生成树、并查集
• 贪心：Dijkstra、零钱兑换、Huffman、区间、背包
• 动态规划：Fibonacci、路径、背包、零钱、钢条切割、LCS、LIS、打家劫舍
• 分治：二分、快排、归并、合并 K 个链表
• 回溯：全排列、组合总和、N 皇后、数独
• 双指针 / 滑动窗口 / 单调栈 / 单调队列
• 字符串：最长公共前缀、最长回文子串、最小覆盖子串
• 设计题：LRU、LFU、跳表、TinyURL、Twitter、股票问题

---

一、初识算法

• 二分查找：基础版 / 改变版
• 衡量算法好坏
• 再看二分查找：平衡版 / Java 版 / Leftmost & Rightmost
• 时间复杂度估算
• 耗时估算
• LeetCode 704 二分查找
• LeetCode 35 搜索插入位置
• LeetCode 34 搜索开始结束位置
• 递归基础
• 单路递归 / 多路递归
• 递归优化：记忆法、尾递归、复杂度、Master 定理

二、基础数据结构

2.1 数组

• 概述
• 动态数组
• 二维数组
• 局部性原理
• 越界检查
• LeetCode 88 合并有序数组

2.2 链表

• 单向链表
• 单向链表（带哨兵）
• 双向链表（带哨兵）
• 环形链表（带哨兵）
• LeetCode 206 / 203 / 19 / 83 / 82 / 21 / 23 / 876 / 234 / 141 / 142 / 237 / 160

2.3 栈 / 队列 / 双端队列 / 优先队列 / 阻塞队列

• 栈：概述、链表实现、数组实现、应用
• LeetCode 20 / 120 / 232 / 225 / 150 / 70 / 103 / 641
• 队列 / 双端队列
• 优先队列 / 堆
• 阻塞队列
• LeetCode 215 / 703 / 295 / 23 / 1138

2.4 树

• 二叉树：存储、遍历、BFS、DFS
• LeetCode 102 / 144 / 94 / 145 / 101 / 111 / 226 / 236 / 105 / 106
• 二叉搜索树（BST）
• AVL 树
• 红黑树
• B 树 / B+ 树概念
• LeetCode 450 / 701 / 700 / 98 / 938 / 1008 / 235

2.5 哈希表

• 第一版、hashCode、冲突与思考
• LeetCode 1 / 3 / 49 / 217 / 136 / 242 / 387 / 347 / 164 / 912 / 148

---

三、基础算法

• 查找：线性查找、二分查找、哈希查找
• 排序：冒泡、选择、堆排、插入、希尔、归并、快排、计数、桶、基数
• LeetCode 排序 / TopK / 数据流中位数
• 图：概念、BFS、DFS、拓扑排序、最短路径、最小生成树、并查集
• 贪心：Dijkstra、零钱兑换、Huffman、区间、背包
• 动态规划：Fibonacci、路径、背包、零钱、钢条切割、LCS、LIS、打家劫舍
• 分治：二分、快排、归并、合并 K 个链表
• 回溯：全排列、组合总和、N 皇后、数独
• 双指针 / 滑动窗口 / 单调栈 / 单调队列
• 字符串：最长公共前缀、最长回文子串、最小覆盖子串
• 设计题：LRU、LFU、跳表、TinyURL、Twitter、股票问题

---

🚀 运行方式

可以直接在 IntelliJ IDEA 中打开 BasicDataStructures 模块，右键运行。

---

📊 复杂度速查（持续更新）

内容	时间复杂度（平均）	空间复杂度	备注
二分查找	O(log n)	O(1)	有序区间
线性查找	O(n)	O(1)	通用
单链表插入/删除（已知前驱）	O(1)	O(1)	查找 O(n)
堆插入 / 删除	O(log n)	O(1) 辅助	优先队列
归并排序	O(n log n)	O(n)	稳定
快速排序（平均）	O(n log n)	O(log n) 栈	不稳定
BST 操作（平均）	O(log n)	O(h)	退化为链 O(n)

---

📅 更新记录

日期	内容
2026-08-20	初始化仓库，完成二分查找基础实现

---

📚 参考资料

• 课程课本
• LeetCode
• Luogu

---

📌 说明

• 本仓库为 个人学习用途，代码以“理解原理 + 可手写”优先
• 包名 / 类名随课本章节和 Java 规范调整
• 结构实现与 LeetCode 题解尽量分离，避免混淆
• 不追求生产级性能，重点在清晰与可推导

---

📄 License

MIT License © 2026 RainxButterfly

---

⭐ 如果对你有参考意义，欢迎点个 Star ~