BLOG

数据结构

以下是对 LeetCode（力扣）题库中涉及的数据结构的系统性总结，覆盖从基础到高级，按类别细分，力求全面，便于查漏补缺或作为复习清单：

📦 一、线性数据结构

1. 数组与字符串

• 静态数组（int[], vector<int> 等）
• 动态数组（如 ArrayList, std::vector）
• 字符串（string, char[]）
• 字符数组和字符串之间的转换
• 前缀和数组（Prefix Sum）
• 差分数组（Difference Array）
• 滑动窗口（双指针）

2. 链表（Linked List）

• 单链表（Singly Linked List）
• 双向链表（Doubly Linked List）
• 循环链表（Circular Linked List）
• 带随机指针的链表（Random Pointer List）
• 虚拟头节点技巧（Dummy Head）

3. 栈（Stack）

• 顺序栈（数组实现）
• 链式栈（链表实现）
• 单调栈（Monotonic Stack）
• 最小栈（Min Stack）
• 括号匹配类问题

4. 队列（Queue）

• 普通队列（FIFO）
• 循环队列
• 双端队列（Deque, 如 std::deque）
• 单调队列（Monotonic Queue）
• 队列模拟栈、栈模拟队列

🌲 二、树形结构

1. 二叉树（Binary Tree）

• 普通二叉树
• 完全二叉树（Complete Binary Tree）
• 满二叉树（Full Binary Tree）
• 平衡二叉树（Balanced Binary Tree）
• 二叉搜索树（BST）
• 线索二叉树（Threaded Binary Tree）

2. 特殊二叉树

• AVL树
• 红黑树（部分高级题）
• Segment Tree（线段树）
• Fenwick Tree / Binary Indexed Tree（树状数组）
• Trie（字典树/前缀树）
• Huffman Tree（赫夫曼编码）

3. N 叉树、K 叉树

• N-ary Tree
• Ternary Tree（例如三分搜索）

🔗 三、图结构（Graph）

• 邻接表（Adjacency List）
• 邻接矩阵（Adjacency Matrix）
• 有向图 / 无向图
• 加权图（Weighted Graph）
• 拓扑排序结构
• 并查集（Disjoint Set Union, Union-Find）
• 图遍历辅助结构：
  • 访问标记数组
  • 路径记录栈
  • 深度优先遍历（DFS 栈）
  • 广度优先遍历（BFS 队列）

📊 四、堆与优先队列

• 最小堆 / 最大堆（Min Heap / Max Heap）
• K路归并堆（如合并多个有序链表）
• 双堆（Two Heaps，常用于中位数问题）
• 自定义比较器的优先队列

🔎 五、查找结构

• 哈希表（Hash Table / Map）
• 哈希集合（Hash Set）
• 有序映射（如 TreeMap, std::map）
• LRU 缓存（基于哈希表 + 双向链表）
• LFU 缓存（基于多种数据结构组合）

📐 六、区间与线性结构扩展

• 区间树（Interval Tree）
• 动态开点线段树（稀疏 Segment Tree）
• 线段树合并、树上差分
• 稀疏表（Sparse Table）
• 树链剖分（Heavy-Light Decomposition）
• 树状图的 Euler 序列 & RMQ 转换
• 倍增（Binary Lifting）

📈 七、特殊结构/技巧

• 并查集（Union-Find）
• 字符统计表（计数数组）
• 多维数组（Matrix）
• 扫描线算法结构（含事件排序结构）
• 哈希双指针（Two HashSets）
• 动态规划表（DP 数组/矩阵）
• 状态压缩（位运算 + DP）
• 位图（Bitset）

🧠 八、用于建模或模拟的辅助结构

• 模拟类题目的手动栈/队列/指针结构
• 自定义对象 + 重载运算符（如堆的排序）
• 多路指针（多个数组/链表同步遍历）
• BFS 状态编码结构（例如编码二维状态为整数）

🧩 九、组合结构（组合使用）

• 栈 + 哈希表（如 LRU）
• 堆 + 哈希表（如 LFU）
• Trie + DFS（如词典搜索）
• 线段树 + 哈希（如区间频率查询）
• 并查集 + 路径压缩 + 按秩合并
• Hash + Bitset（判重、去重）

🔁 十、经典结构类题型（题型引导结构）

算法

🧮 一、基础算法（算法设计基础）

---

🧠 二、递归与分治

---

🔢 三、动态规划（Dynamic Programming）

1. 一维 DP（背包/线性状态）

2. 区间 DP / 记忆化

---

🔁 四、贪心算法（Greedy）

---

🧭 五、图论算法

1. 图遍历

2. 图最短路径

3. 最小生成树 MST

---

🎯 六、搜索类算法

1. 回溯（Backtracking）

2. 剪枝优化

---

🧩 七、位运算技巧

---

🧮 八、数学算法

---

💡 九、字符串算法

---

🧬 十、高级与综合算法

---

📌 十一、模拟类算法

---

✅ 十二、算法范式对照表

---