← 返回首页
一、数据结构
线性结构
- 数组:连续内存,随机访问 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))、汉明距离