数据结构与算法 Summery

本文参考代码随想录的经典分类方式，系统总结各个数据结构与算法。每个模块包含：

- 📚 **定义与原理**：核心概念和基础理论
- 🎯 **考点分类**：各种考法和解题模式
- 💡 **精选题目**：每个考点的代表性 LeetCode 题目

📋 第一阶段：基础数据结构

1. 数组 (Array)

📚 定义与原理

数组是存放在连续内存地址中的相同类型数据的集合。

🎯 考点分类

考点1：二分查找

适用场景：有序数组中查找特定元素或边界值，while(left < right) 题目：704, 35, 34, 69, 367

考点2：移除元素（双指针法，快慢指针），因为数组不支持删除只能覆盖

适用场景：原地修改数组，删除特定元素，用后面的非target覆盖前一个 题目：27, 26, 283, 844, 977

考点3：滑动窗口

适用场景：连续子数组问题，动态维护窗口（其实是O(n),窗口两个边界只看扫过的元素是2n） 题目：209, 904, 76

考点4：螺旋矩阵

适用场景：不涉及到什么算法，就是模拟过程，但却十分考察对代码的掌控能力 题目：59, 54

考点5：前缀和

适用场景：KMP算法，在涉及计算区间和的问题时非常有用 题目：58, 44

2. 链表 (Linked List)

📚 定义与原理

链表是通过指针将一组零散的内存节点串联使用的数据结构。链表中的元素不是存放在连续的内存空间，而是通过指针连接。链表支持动态扩容，插入和删除操作时间复杂度为 O(1)，但不支持随机访问，查找元素需要 O(n) 时间。

🎯 考点分类

考点1：链表的基本概念

适用场景：理解链表的基本结构和操作 题目：203, 707

考点2：移除链表元素

适用场景： 核心是 if cur.Next.Val == val cur.Next = cur.Next.Next 题目：203, 19

考点3：设计链表

适用场景： 核心是 if cur.Next.Val == val cur.Next = cur.Next.Next 题目：707

考点4：翻转链表（直接反转的）

适用场景： 双指针记录下一个之后翻转本身，cur->next 本质上始终是一个指向节点的指针字段，但在表达式里是“读”还是“写”它，决定了它被当作值（被解引用使用）还是地址（被写入）来看待。 while(cur) { temp = cur->next; // 保存一下 cur的下一个节点，因为接下来要改变cur->next cur->next = pre; // 翻转操作 // 更新pre 和 cur指针 pre = cur; cur = temp; } 题目：206, 92

考点5：两两交换链表中的节点

适用场景： 主要想清楚交换步骤，搞个虚拟头节点，这样就不用单独判断head了 题目：24

考点6：删除链表的倒数第N个节点

适用场景： fast先走n（实操走n+1）然后slow和fast一起走，fast=nil了，删slow，才2n 题目：19

考点7：链表相交

适用场景： 注意是指针相同不是值相同，让长的链先走｜L1-L2｜多步就能保证出发线相同 题目：160

考点8：是否有环和环起始

适用场景： 是否有环看fast和slow是否相遇，起始看相遇地方和开头同时走相遇即起始（如果只转了1圈就相遇，那fast=2slow） 题目：141, 142

3. 哈希表 (Hash Table)

📚 定义与原理

哈希表是根据关键码的值而直接进行访问的数据结构，通过哈希函数将关键码映射到表中的位置。哈希表的主要优势是能够在平均 O(1) 时间内完成查找、插入和删除操作。常见实现包括数组、set（集合）、map（映射）。 当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。

🎯 考点分类

考点1：有效异位词

适用场景：使用天然统计26个字母和1-26的对应，将 s[i] - ‘a’ 所在的元素做+1 操作 题目：242, 383, 49, 438, 1002

考点2：两个数组的交集

适用场景：巧妙利用键和值的关系，让num作为set的键 题目：349, 350

考点3：快乐数

适用场景：判断数是否循环出现，使用set记录出现过的数字 题目：202

考点4：两数之和

适用场景：巧妙的把值当键，把索引当值，边遍历边查找 题目：1

考点5：四数相加

适用场景：key在于这题只需要count次数，我们可以统计array a和b的sum的种数和出现的次数，再依次看0-（c+d）是否出现且把次数相加 题目：454

考点6：三数之和

适用场景：哈希法不太行，用双指针，需要去重 题目：15

考点7：四数之和

适用场景：哈希法不太行，还是用双指针，只不过在三数基础上再加一层for 题目：18

4. 字符串 (String)

📚 定义与原理

字符串是由字符组成的序列，在C++中以字符数组形式存储，末尾有'\0'结束符。字符串的常见操作包括查找、替换、分割、匹配等。重要算法包括KMP字符串匹配算法，能在O(m+n)时间内完成模式匹配。

🎯 考点分类

考点1：字符串反转

适用场景：整体或部分反转字符串 题目：344, 541, 剑指Offer05, 151, 剑指Offer58-II

考点2：替换数字

适用场景：合理使用切片和append 题目：剑指Offer05

考点3：翻转字符串

适用场景：难点在于空间需要O（1），所以只能对原字符串操作，思路是先erase空格，再整体翻转，再翻转单词 题目：151

考点4：右旋字符串

适用场景：还是整体翻转，再翻转内部切片 题目：剑指Offer58-II

考点5：strStr()（！！！）

适用场景：KMP KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。 前缀表：记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。 题目：28

5. 双指针法

📚 定义与原理

双指针法是使用两个指针在线性结构中进行扫描的算法技巧。根据两个指针的移动方式，可分为对撞指针（两端向中间移动）和快慢指针（同向移动但速度不同）。双指针法能够将O(n²)的暴力解法优化到O(n)。

🎯 考点分类

考点1：移除元素（快慢指针）

适用场景：原地修改数组或字符串 题目：27, 26, 283

考点2：反转/翻转（对撞指针）

适用场景：需要首尾配对的场景 题目：344, 557

考点3：滑动窗口（！！！）

适用场景：连续子数组/子字符串问题 题目：209, 904

考点4：多数之和

适用场景：在数组中找到多个数满足特定和值 题目：15, 18

6. 栈与队列

📚 定义与原理

栈（Stack）是一种后进先出（LIFO）的数据结构，只允许在一端进行插入和删除操作。队列（Queue）是一种先进先出（FIFO）的数据结构，允许在一端插入，另一端删除。栈和队列都可以用数组或链表实现。

🎯 考点分类

考点1：栈和队列的基本应用

适用场景：栈先进后出，队列先进先出，pop，push，peek 题目：20, 1047, 150

考点2：用栈实现队列

适用场景：两个栈，一个进栈，一个出栈，push进栈，pop出栈需要把进栈的所有push到出栈中 题目：739, 496, 503, 42, 84

考点3：用队列实现栈

适用场景：一个队列，就push直接进，pop把除最后一个元素外依次重新进队列 题目：225, 232, 622, 641

考点4：有效的括号

适用场景：匹配括号，扫左括号，进右括号，只用匹配是否相等就行 题目：239, 862

考点5：逆波兰表达式

适用场景：数字入栈，碰到op出两个数字运算结果再入栈 题目：155, 716, 895

考点6：滑动窗口（！！！）

适用场景：单调队列，学会构建，关键是push的时候把比新值小的全删了，pop的时候看是否和左边出去的相同，也就是维持队列里有最大值和新值（可重） 题目：155, 716, 895

考点7：前k个高频元素（！！！）

适用场景：搞个map存每个数，然后排序，节省时间就搞个最小堆 题目：155, 716, 895

📋 第二阶段：树形结构

7. 二叉树 (Binary Tree)

📚 定义与原理

二叉树是每个节点最多有两个子节点的树形数据结构，子节点分为左子节点和右子节点。二叉树的遍历方式包括： - 前序遍历：根→左→右 - 中序遍历：左→根→右
- 后序遍历：左→右→根 - 层序遍历：按层从上到下，从左到右

🎯 考点分类

考点1：二叉树的遍历方式

适用场景：理解递归结构，掌握基本遍历 题目：144, 94, 145, 102

考点2：二叉树的层序遍历

适用场景：BFS和DFS 题目：101, 104, 111, 222, 110, 257, 404, 513, 112, 113

考点3：二叉树的修改与构造

适用场景：根据条件构造或修改二叉树 题目：226, 106, 105, 654, 617

考点4：求二叉搜索树的属性

适用场景：利用BST的有序性质 题目：700, 98, 530, 501, 236, 235

考点5：二叉搜索树的修改与构造

适用场景：BST的插入、删除、构造操作 题目：701, 450, 669, 108, 538

8. 回溯

📚 核心概念

• 完全二叉树实现的优先队列
• 大顶堆：父节点 ≥ 子节点
• 小顶堆：父节点 ≤ 子节点
• 插入、删除时间复杂度 O(log n)

🎯 考点要点

• 堆的维护：上浮、下沉操作
• Top-K 问题：大顶堆找最小，小顶堆找最大
• 堆排序：原地排序算法
• 多路归并：多个有序序列合并

题目：215, 23, 295, 347, 378

📋 第三阶段：图与高级数据结构

9. 图 (Graph)

📚 核心概念

• 顶点和边的集合：G = (V, E)
• 有向图 vs 无向图，有权图 vs 无权图
• 表示方法：邻接矩阵、邻接表

🎯 考点要点

• 图的遍历：DFS、BFS 的实现和应用
• 连通性问题：强连通分量、连通图判断
• 最短路径：Dijkstra、Floyd、Bellman-Ford
• 最小生成树：Kruskal、Prim 算法
• 拓扑排序：有向无环图的线性排序

题目：200, 207, 743, 547, 1631

10. 并查集 (Union-Find)

📚 核心概念

• 处理动态连通性问题的数据结构
• 基本操作：union（合并）、find（查找）
• 路径压缩和按秩合并优化

🎯 考点要点

• 连通性判断：判断两个元素是否在同一集合
• 动态连通性：支持动态添加连接关系
• 路径压缩：优化查找操作时间复杂度
• 按秩合并：平衡树的高度

题目：200, 547, 128, 721, 1319

11. 字典树 (Trie)

📚 核心概念

• 专门处理字符串集合的树形数据结构
• 根到叶子路径表示一个字符串
• 支持高效的前缀查询

🎯 考点要点

• 前缀匹配：快速查找具有特定前缀的字符串
• 字符串插入查找：时间复杂度与字符串长度相关
• 空间优化：压缩字典树减少空间消耗
• 应用场景：自动补全、拼写检查

题目：208, 211, 212, 421, 440

📋 第四阶段：算法思想

12. 排序算法

📚 核心概念

• 比较排序：冒泡、选择、插入、归并、快速、堆排序
• 非比较排序：计数、桶、基数排序
• 稳定性：相等元素的相对位置是否改变

🎯 考点要点

• 时间复杂度分析：最好、平均、最坏情况
• 空间复杂度：原地排序 vs 非原地排序
• 适用场景：小数组、大数组、特定数据分布
• 自定义排序：比较器的使用

题目：912, 75, 148, 179, 315

13. 二分搜索

📚 核心概念

• 在有序数组中查找特定元素
• 时间复杂度 O(log n)
• 左边界、右边界、最接近值查找

🎯 考点要点

• 边界处理：开区间、闭区间、半开区间
• 搜索空间：线性空间、解空间
• 单调性判断：二分的前提条件
• 变种应用：旋转数组、山脉数组

题目：704, 34, 33, 153, 4

14. 动态规划 (DP)

📚 核心概念

• 将复杂问题分解为重叠子问题
• 状态定义、状态转移方程、初始状态、返回值
• 记忆化搜索 vs 自底向上

🎯 考点要点

• 经典模型：背包、LIS、LCS、编辑距离
• 状态压缩：滚动数组优化空间复杂度
• 区间DP：子问题为区间的动态规划
• 树形DP：在树上进行的动态规划

题目：70, 62, 300, 72, 322

15. 贪心算法

📚 核心概念

• 每一步都做当前最优选择
• 局部最优解导致全局最优解
• 需要证明贪心选择性质和最优子结构

🎯 考点要点

• 贪心策略证明：数学归纳法或反证法
• 排序贪心：按某种顺序排序后贪心选择
• 区间问题：活动安排、会议室分配
• 字符串贪心：字典序、回文构造

题目：455, 435, 121, 55, 45

16. 回溯算法

📚 核心概念

• 系统性搜索所有可能的候选解
• 做选择 → 递归 → 撤销选择
• 剪枝优化减少无效搜索

🎯 考点要点

• 排列组合：全排列、组合、子集生成
• 约束满足：N皇后、数独求解
• 路径搜索：迷宫、单词搜索
• 剪枝策略：提前终止无效分支

题目：46, 78, 39, 51, 79

📋 第五阶段：专题算法

17. 字符串算法

📚 核心概念

• 字符串匹配：KMP、Boyer-Moore、Rabin-Karp
• 字符串处理：反转、查找、替换
• 回文问题：回文判断、最长回文子串

题目：5, 28, 125, 3, 647

18. 位运算

📚 核心概念

• 基本位运算：与、或、异或、非、左移、右移
• 位运算技巧：判断奇偶、交换变量、统计二进制位
• 位掩码：状态压缩、集合操作

题目：136, 191, 338, 421, 268

19. 数学算法

📚 核心概念

• 数论：质数、最大公约数、最小公倍数
• 组合数学：排列组合、卡特兰数、斐波那契数
• 概率统计：随机算法、蒙特卡洛方法

题目：204, 50, 172, 384, 365

🎯 刷题策略与建议

📅 学习计划

第 1-2 周：基础数据结构

• 目标：掌握数组、链表、栈、队列的基本操作
• 建议：每天 2-3 题，重点理解数据结构特性
• 重点：双指针、快慢指针、单调栈等技巧

第 3-4 周：树形结构

• 目标：熟练掌握二叉树的各种遍历和操作
• 建议：递归思维训练，理解树的递归结构
• 重点：前中后序遍历、层序遍历、BST 性质

第 5-6 周：图和高级数据结构

• 目标：理解图的基本算法和高级数据结构
• 建议：重点掌握 DFS/BFS、并查集、字典树
• 重点：连通性问题、最短路径、前缀匹配

第 7-8 周：算法思想

• 目标：掌握动态规划、贪心、回溯等算法思想
• 建议：大量练习，总结状态转移方程
• 重点：经典 DP 模型、贪心证明、回溯剪枝

第 9-10 周：专题强化

• 目标：针对薄弱环节专项训练
• 建议：模拟面试、限时刷题
• 重点：字符串、位运算、数学题目

💡 刷题技巧

📊 能力评估

📚 学习资源推荐

在线课程

• LeetCode 官方题解：详细的解题思路和代码实现
• 代码随想录：系统的算法学习路线
• labuladong 的算法小抄：经典算法模板总结

参考书籍

• 《算法导论》：算法理论基础
• 《算法 4》：Java 实现的经典算法
• 《剑指 Offer》：面试算法题集合
• 《程序员代码面试指南》：IT 名企算法与数据结构题目最优解

在线工具

• LeetCode：在线刷题平台
• 牛客网：算法竞赛和面试准备
• Visualgo：算法可视化学习网站
• Algorithm Visualizer：数据结构和算法动画演示

祝您在算法学习的道路上不断进步！🚀