Data Structures & Algorithm
自动关联目录:Data Structures & Algorithm
这里记录的是解题方法,不是"把 STL 用熟"。核心是三类能力:
- 看出问题的结构(能归约到哪个模型)
- 选对工具(哪种数据结构/算法能支撑所需的操作)
- 估出复杂度(能不能过,卡在哪个常数上)
如果算法思路清楚但总在 C++ 容器、标准算法或 API 上卡住,先查 LeetCode C++ 标准库速查。
两条主线
数据结构回答"数据怎么组织",算法回答"步骤怎么安排"。实际解题时两者纠缠在一起。
| 主线 | 关注点 | 本目录对应 |
|---|---|---|
| 基础算法思想 | 枚举、二分、贪心、分治、倍增、前缀和 | Basic Algorithm |
| 线性结构 | 数组、链表、栈、队列、单调结构 | Linear |
| 树形结构 | 二叉/多叉树、树形遍历与统计 | Tree |
| 图论 | 建图、遍历、最短路、连通性 | Graph |
| 字符串 | 匹配、哈希、自动机 | String |
| 哈希 | 散列、冲突处理 | Hash |
| 动态规划 | 状态设计与转移 | Dynamic Programming |
| 杂项 | 复杂度分析、位运算、离散化等 | Misc |
| C++ 标准库速查 | 容器、算法、数值工具、核心 API、刷题模板 | LeetCode C++ 标准库速查 |
复杂度:唯一的硬约束
做题时先估量级,再选方法:
| 可接受复杂度 | 典型算法 | |
|---|---|---|
| 状态压缩、暴搜 + 剪枝 | ||
| Floyd、区间 DP | ||
| 朴素 DP、双重循环 | ||
| 排序、线段树、堆、二分 | ||
| 单调栈/队列、双指针、线性 DP | ||
| 或 | 数学、倍增、快速幂 |
注意常数: 的排序和 的平衡树,常数可以差 5 倍。 的规模下,快排 10 ms,红黑树 50 ms,哈希表 15 ms——能排序就别用平衡树。
解题的通用流程
1. 读题,明确:输入规模?求什么(最值/计数/判定/构造)?
2. 暴力怎么写?(先把暴力写清楚,它是后续优化的参照系)
3. 暴力慢在哪?(重复计算?无效枚举?)
4. 针对性的优化手段:
- 重复计算 → 记忆化 / DP
- 无效枚举 → 二分 / 双指针 / 单调性剪枝
- 需快速查询 → 哈希 / 前缀和 / 数据结构
- 需维护区间 → 线段树 / 树状数组 / 分块
5. 边界检查:空输入、n=1、最大值、重复元素先写暴力这一步不能省。很多"想不出来"其实是暴力都没想清楚。
常见思维模式
| 模式 | 适用特征 | 典型手段 |
|---|---|---|
| 缩小规模 | 问题可拆成同类子问题 | 分治、DP、递归 |
| 枚举 + 判定 | 答案可验证 | 二分答案、枚举 + check |
| 维护不变量 | 需在线处理 | 数据结构、增量维护 |
| 转化视角 | 原问题难,换个等价形式好做 | 建模成图、对偶、补集 |
| 先排序 | 元素间有顺序关系 | 排序后双指针、贪心 |
| 预处理换查询 | 多次查询 | 前缀和、倍增、离线处理 |
参考
- OI Wiki——中文最好的竞赛算法百科
- CP-Algorithms——按主题组织,代码质量高
- 《算法导论》(CLRS)——理论严谨
- 《算法(第 4 版)》(Sedgewick)——工程视角,图多
许可协议:CC BY
作者:Davids
本文链接:https://hustjjd.github.io/73b8421c.html
更新于:2026年11月16日