For AI agents: the complete documentation index is available at https://tingfeng347.github.io/windwiki/llms.txt, the full documentation bundle is available at https://tingfeng347.github.io/windwiki/llms-full.txt, and this page is available as Markdown at https://tingfeng347.github.io/windwiki/terminology/algorithms-and-data-structures.md.

数据结构与算法 · 面试清单

面试权重：★★★★★　笔试与手撕环节的硬门槛；重点不是背题，而是「看到题能说出用哪个结构、复杂度是多少」。

一、复杂度分析

术语	一句话释义
时间复杂度	输入规模趋于无穷时基本操作数的增长阶，只保留最高次项并去系数
空间复杂度	除输入外额外占用的空间；递归要算栈深度
均摊复杂度	把偶发的高代价操作摊到一系列操作上，如动态数组扩容是 O(1) 均摊
最好 / 最坏 / 平均	面试要说最坏；快排最坏 O(n²)、平均 O(n log n)
常见量级排序	O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
主定理	分治复杂度的通用估算工具，如 T(n)=2T(n/2)+O(n) 得 O(n log n)
对数来源于分治	每次把问题规模减半，就出现 log n
数据规模反推复杂度	n≤10 可阶乘级、n≤20 可 2ⁿ、n≤10³ 可 O(n²)、n≤10⁵ 要 O(n log n)、n≥10⁶ 只能 O(n)

二、线性结构

术语	一句话释义
数组	连续内存、O(1) 随机访问、中间插入删除 O(n)
动态数组	容量不足时成倍扩容并拷贝，均摊 O(1) 追加
链表	结点 + 指针，插入删除 O(1)（已定位时），随机访问 O(n)
单链表 / 双链表 / 循环链表	能否反向遍历、是否有哨兵节点的区别
哑结点 Dummy Head	在头结点前加一个假节点，统一处理头插与删除的边界
快慢指针	找中点、判环、找入环节点（Floyd 判圈算法）
反转链表	三指针迭代法最稳，递归法要能说清栈深度
栈 Stack	后进先出；用于括号匹配、表达式求值、单调栈、DFS 模拟
单调栈	栈内元素单调，用于「下一个更大元素」类问题，每个元素进出一次即 O(n)
队列 Queue	先进先出；BFS、任务调度的基础
双端队列 Deque	两端进出 O(1)，滑动窗口最大值的载体
循环队列	用取模复用数组空间，判满需要牺牲一个槽或额外计数
优先队列	逻辑上按优先级出队，通常用堆实现
哈希表	均摊 O(1) 增删查，冲突用链地址法或开放寻址
哈希冲突与扩容	负载因子超过阈值即扩容并 rehash；最坏情况退化为 O(n)
一致哈希	分布式分片用，节点增减时只影响邻近区间，配合虚拟节点解决倾斜
LRU 缓存	哈希表 + 双向链表，O(1) 取用与淘汰；手撕高频题
LFU 缓存	按访问频次淘汰，需额外维护频次桶，实现比 LRU 复杂

三、树与堆

术语	一句话释义
二叉树遍历	前/中/后序（DFS，递归或显式栈）+ 层序（BFS，队列）
BST 二叉搜索树	左 < 根 < 右，中序遍历即有序序列；退化成链表时是 O(n)
平衡二叉树 AVL	严格平衡，查找稳定 O(log n)，但旋转频繁、写多时不如红黑树
红黑树	近似平衡（最长路径不超过最短的两倍），插入删除旋转少，Java TreeMap / C++ map 都用它
完全二叉树	除最后一层外都满且靠左连续，可用数组存储、是堆的结构基础
堆 Heap	完全二叉树，大顶/小顶；建堆 O(n)、插入删除 O(log n)
堆排序	建堆 + 反复取堆顶，O(n log n) 且原地，但不稳定、常数大
Top K 问题	求最大 K 个用小顶堆（维护 K 个元素，O(n log K)）；求第 K 大可用快速选择 O(n) 平均
Trie 前缀树	按字符分层，用于前缀匹配、自动补全、敏感词过滤
线段树 / 树状数组	区间查询与单点/区间修改，树状数组更短，线段树更通用
并查集 Union-Find	路径压缩 + 按秩合并，近乎 O(1) 判断连通性，用于动态连通、Kruskal
B 树 / B+ 树	多路平衡查找树，为磁盘设计；数据库索引用它减少 IO 次数
跳表 SkipList	多层链表实现有序，期望 O(log n)，实现简单、范围查询友好

四、图

术语	一句话释义
图的表示	邻接矩阵（稠密、判边 O(1)）vs 邻接表（稀疏、省空间）
DFS	递归/栈深入到底，用于连通性、拓扑排序、环检测；复杂度 O(V+E)
BFS	队列逐层扩散，用于无权图最短路、层序遍历
拓扑排序	有向无环图（DAG）的线性次序；Kahn（BFS 入度）或 DFS 后序
最短路算法	Dijkstra（非负权，堆优化 O(E log V)）、Bellman-Ford（可有负权、判负环）、Floyd（全源，O(V³)）
Dijkstra 为什么不能有负权	贪心前提是「已确定的最短距离不会再被缩短」，负边会破坏它
最小生成树	Kruskal（按边排序 + 并查集）与 Prim（按点扩张）
二分图判定	交替染色，遇到冲突即不是二分图
并查集判环	无向图中边的两端已连通则成环

五、排序与查找

术语	一句话释义
冒泡 / 选择 / 插入	O(n²)；插入排序对近乎有序的数据接近 O(n)
希尔排序	分组插入排序，逐步缩小增量，O(n^1.3) 左右
归并排序	分治，稳定，O(n log n)，但需要 O(n) 额外空间（链表排序首选）
快速排序	分区 + 递归，原地且常数小；随机化选基准或三数取中避免最坏 O(n²)
堆排序	原地 O(n log n)，不稳定
计数 / 桶 / 基数排序	非比较排序，O(n+k)，适用于值域有限或整数键
排序稳定性	相等元素相对顺序不变；归并、插入、冒泡稳定，快排、堆排、选择不稳定
二分查找	有序区间折半，O(log n)；注意 `mid = left + (right - left) / 2` 防溢出与边界
二分答案	答案具有单调性时，对答案做二分再写 check，是「最小化最大值」类题的套路
快速选择 QuickSelect	快排分区的副产品，平均 O(n) 求第 K 大

六、算法思想

术语	一句话释义
双指针	有序数组求两数之和、三数之和、去重、滑动窗口类问题的通用套路
滑动窗口	维护一个可变区间的状态，右扩左缩，把 O(n²) 降到 O(n)
前缀和 / 差分	前缀和 O(1) 求区间和；差分 O(1) 做区间加，最后还原
分治 Divide and Conquer	拆分 → 递归求解 → 合并，代表是归并排序与快排
贪心 Greedy	每步取局部最优；能用必须证明「局部最优可推出全局最优」，否则要用 DP
回溯 Backtracking	DFS 枚举 + 剪枝 + 撤销选择，用于全排列、组合、子集、N 皇后
剪枝	提前排除不可能的分支：排序后提前终止、记忆化、可行性上下界
动态规划 DP	有重叠子问题与最优子结构时，用状态 + 转移 + 边界求解
DP 解题四步	定义状态 → 写转移方程 → 定初值与边界 → 定遍历顺序
记忆化搜索	递归 + 缓存，是 DP 的自顶向下写法，思维负担小
01 背包 / 完全背包	每件物品取或不取 / 可取无限次；01 背包容量维度必须逆序以复用上一行
最长公共子序列 LCS	双序列 DP 的样板题，`dp[i][j]` 表示前 i、前 j 个的最优解
编辑距离	双序列 DP，插入/删除/替换三种转移取最小
状态压缩 DP	用位运算表示集合状态，适用于 n ≤ 20 的集合类问题
位运算技巧	`n & (n-1)` 消掉最低位的 1、`n & -n` 取最低位 1、异或可找出只出现一次的数

七、高频手撕题清单

术语	一句话释义
LRU / LFU	哈希 + 双向链表/频次桶，考察数据结构组合能力
反转链表 / K 个一组反转	指针操作与边界处理的试金石
环形链表与入环点	快慢指针，相遇后一头回到起点再同步走即入环点
合并两个有序链表 / 数组	双指针归并，或原地从后往前填充避免覆盖
链表排序	归并 + 快慢指针找中点，O(n log n) 且 O(1) 空间
两数之和 / 三数之和	哈希或排序 + 双指针，注意去重
最长无重复子串	滑动窗口 + 哈希记录上次出现位置
接雨水 / 最大矩形	单调栈与双指针的经典应用
Top K / 数组第 K 大	小顶堆或快速选择
二叉树层序与锯齿遍历	BFS 队列 + 每层长度控制
二叉树最近公共祖先	后序遍历回传结果；BST 版本可按值比较
二叉树最大路径和	树形 DP，返回「单边最大」、用全局变量更新「拐弯最大」
LRU 之外的缓存设计	限流器（令牌桶/滑动窗口）、环形缓冲区
字符串类高频题	最长回文子串（中心扩展/Manacher）、字符串解码（栈）、单词拆分（DP）
矩阵与图类高频题	岛屿数量（BFS/DFS/并查集）、腐烂橘子（多源 BFS）、课程表（拓扑排序/判环）
设计类题	用两个栈实现队列、O(1) 取最小值的栈、时间轮 / 限流器设计

八、面试表达要点

术语	一句话释义
先沟通再写码	明确输入输出、边界、数据规模与是否允许修改输入，再动手
先说思路与复杂度	面试官更在意推导过程；上来直接写码容易走偏
暴力解法打底	先给出可解方案与复杂度，再逐步优化，不要沉默太久
边界用例自查	空输入、单元素、极值、重复元素、溢出，是 bug 的高发区
过一遍代码	写完用样例手动走一遍，比说「写完了」更能拿到评分
数据规模决定算法	10⁵ 就不能写 O(n²)，这是最常见的隐性扣分点

参考资料

《代码随想录》题解体系
Thomas H. Cormen 等《算法导论》
站点内《数据结构与算法》课程笔记