← 返回首页
一、数据结构
线性结构
- 数组：连续内存，随机访问 O(1)，插入删除 O(n)，适合读多写少
- 链表：单链表/双链表/循环链表，插入删除 O(1)，查找 O(n)。常考：反转、环检测（快慢指针）、合并有序链表
- 栈：LIFO，应用：括号匹配、单调栈（下一个更大元素）、表达式求值
- 队列：FIFO，双端队列 Deque，优先队列（堆实现），单调队列（滑动窗口最大值）
树结构
- 二叉树：前/中/后序遍历（递归+迭代）、层序遍历（BFS），最大深度、路径总和
- BST 二叉搜索树：左 < 根 < 右，中序遍历有序，查找/插入/删除 O(logN)~O(N)
- AVL / 红黑树：自平衡 BST，保证 O(logN)。红黑树：TreeMap/HashMap 底层
- 堆：完全二叉树，大顶堆/小顶堆，PriorityQueue 实现，TopK 问题利器
- Trie 前缀树：字符串前缀匹配、自动补全、词频统计
图结构
- 表示方式：邻接矩阵（稠密图）/ 邻接表（稀疏图）
- BFS：层序遍历，最短路径（无权图）；DFS：深度遍历，连通分量、拓扑排序
- 并查集：Union-Find，判断连通性、环检测，路径压缩+按秩合并优化
二、排序算法
- 冒泡排序：O(n²)，相邻比较交换，稳定
- 选择排序：O(n²)，每轮选最小放前面，不稳定
- 插入排序：O(n²)，近乎有序时接近 O(n)，稳定
- 归并排序：O(nlogn)，分治+合并，稳定，需额外空间 O(n)
- 快速排序：平均 O(nlogn)，最坏 O(n²)，不稳定，原地排序。优化：随机选 pivot、三路快排
- 堆排序：O(nlogn)，不稳定，原地排序，建堆 O(n)
- 计数/桶/基数排序：非比较排序，特定场景 O(n)，空间换时间
三、双指针与滑动窗口
- 对撞指针：有序数组两数之和、接雨水、盛最多水的容器
- 快慢指针：链表环检测、链表中点、删除倒数第 N 个节点
- 滑动窗口：维护窗口 [left, right]，右扩左缩。最小覆盖子串、无重复字符最长子串、字母异位词
四、二分查找
- 基本模板：
while (left <= right)，注意边界和 mid 计算防溢出 left + (right - left) / 2
- 查找左边界：找第一个 >= target 的位置（lower_bound）
- 查找右边界：找最后一个 <= target 的位置（upper_bound）
- 旋转数组：搜索旋转排序数组、寻找最小值
- 二分答案：将优化问题转化为判定问题，如分割数组的最大值、吃香蕉的速度
五、动态规划
- 核心思想：最优子结构 + 重叠子问题，状态定义 → 转移方程 → 初始条件 → 遍历顺序
- 线性 DP：爬楼梯、打家劫舍、最长递增子序列（LIS，O(nlogn) 二分优化）
- 背包问题：0-1 背包（每件选一次）/ 完全背包（无限选）/ 多重背包，空间优化为一维
- 区间 DP：戳气球、最长回文子序列
- 树形 DP：打家劫舍 III、二叉树直径
- 字符串 DP：编辑距离、最长公共子序列（LCS）、正则表达式匹配
- 股票问题：状态机 DP，持有/不持有/冷冻期，统一框架解决系列问题
六、回溯与贪心
回溯
- 本质是 DFS + 剪枝，模板：选择 → 递归 → 撤销选择
- 经典题：全排列、组合总和、子集、N 皇后、数独、括号生成
- 剪枝优化：排序后跳过重复元素、提前终止不满足条件的分支
贪心
- 每步选择局部最优，适用于具有贪心选择性质的问题
- 经典题：跳跃游戏、分发糖果、区间调度（无重叠区间）、加油站
七、高频题型速查
- 哈希表：两数之和、字母异位词分组、最长连续序列
- 单调栈：每日温度、下一个更大元素、柱状图最大矩形
- BFS 最短路：二叉树层序、岛屿数量、单词接龙
- 拓扑排序：课程表（有向无环图 DAG 判定）
- 位运算：只出现一次的数字（异或）、2 的幂（n & (n-1)）、汉明距离