数据结构与算法

一、基础数据结构

数据结构是算法的载体，先掌握组织数据的基本方式。

线性结构

• 数组：连续内存，随机访问 O(1)，插入删除 O(n)。
• 链表：离散内存，插入删除 O(1)，随机访问 O(n)。
• 栈：后进先出，用于函数调用、括号匹配、撤销操作。
• 队列：先进先出，用于任务调度、BFS 搜索。

非线性结构

• 哈希表：以空间换时间，实现 O(1) 查找。
• 树：二叉树、二叉搜索树、堆，是很多复杂结构的地基。
• 图：顶点 + 边，建模网络、社交、地图等关系。

二、核心算法

排序与查找

• 排序：快排、归并、堆排序，理解各自最坏时间复杂度。
• 查找：二分查找及其变体（找左边界、右边界）。

搜索与动态规划

• DFS / BFS：树的遍历与图的最短路径（无权）。
• 动态规划：状态定义 + 转移方程，是面试重灾区。
• 贪心：局部最优递推全局最优，需证明。

三、复杂度分析

用大 O 表示法衡量算法效率，是选择方案的依据。

• 时间复杂度：随数据规模增长，执行次数如何变化。
• 空间复杂度：运行时额外占用的内存。
• 学会比较：O(1) < O(log n) < O(n) < O(n log n) < O(n²)。

写代码前先想复杂度，面试时主动说出，会加分。

四、练习路径

推荐按阶段推进，每阶段配合刷题巩固：

1. 1数组、链表、栈、队列（基础题 20 道）
2. 2哈希表、二分查找（中级题 20 道）
3. 3二叉树递归 + DFS/BFS（中级题 20 道）
4. 4动态规划经典题（进阶题 15 道）
5. 5图、并查集、贪心（冲刺题 15 道）

坚持每天 1-2 题，比一次刷很多更有效。