数据结构与算法 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, 206

考点2：双指针技巧

适用场景：检测环、找中点、倒数第K个节点 题目：24, 19, 面试题02.07, 142

3. 栈与队列 (Stack & Queue)

📚 定义与原理

栈：后进先出(LIFO)的数据结构，只能在栈顶进行插入和删除操作。主要操作包括push(入栈)、pop(出栈)、top/peek(查看栈顶元素)。

队列：先进先出(FIFO)的数据结构，在队尾插入元素，在队头删除元素。主要操作包括enqueue(入队)、dequeue(出队)、front(查看队头)。

🎯 考点分类

考点1：栈的基本应用

适用场景：括号匹配、逆序处理、递归模拟 题目：232, 225, 20, 1047

考点2：队列的基本应用

适用场景：层序遍历、BFS搜索 题目：239

考点3：优先级队列（堆）

适用场景：Top K问题、动态维护最值 题目：347

4. 哈希表 (Hash Table)

📚 定义与原理

哈希表是根据关键码的值而直接进行访问的数据结构，通过哈希函数将关键码映射到表中的位置。哈希表的主要优势是能够在平均 O(1) 时间内完成查找、插入和删除操作。常见实现包括数组、set（集合）、map（映射）。

🎯 考点分类

考点1：数组作为哈希表

适用场景：元素范围有限且连续的情况 题目：242, 383, 49, 438

考点2：set集合

适用场景：判断元素是否存在，去重操作 题目：349, 350, 202

考点3：map映射

适用场景：需要记录元素及其相关信息 题目：1, 454, 15, 18

5. 字符串 (String)

📚 定义与原理

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

🎯 考点分类

考点1：字符串反转

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

考点2：字符串匹配

适用场景：在主串中查找模式串 题目：28, 459

6. 双指针法

📚 定义与原理

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

🎯 考点分类

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

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

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

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

考点3：滑动窗口

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

考点4：多数之和

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

📋 第二阶段：树形结构

7. 二叉树 (Binary Tree)

📚 定义与原理

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

🎯 考点分类

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

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

考点2：二叉树的属性

适用场景：计算树的各种属性值 题目：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. 堆 (Heap)

📚 核心概念

• 完全二叉树实现的优先队列
• 大顶堆：父节点 ≥ 子节点
• 小顶堆：父节点 ≤ 子节点
• 插入、删除时间复杂度 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：数据结构和算法动画演示

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