Data Structures & Algorithm

自动关联目录:Data Structures & Algorithm

这里记录的是解题方法,不是"把 STL 用熟"。核心是三类能力:

  1. 看出问题的结构(能归约到哪个模型)
  2. 选对工具(哪种数据结构/算法能支撑所需的操作)
  3. 估出复杂度(能不能过,卡在哪个常数上)

如果算法思路清楚但总在 C++ 容器、标准算法或 API 上卡住,先查 LeetCode C++ 标准库速查。

两条主线

数据结构回答"数据怎么组织",算法回答"步骤怎么安排"。实际解题时两者纠缠在一起。

主线关注点本目录对应
基础算法思想枚举、二分、贪心、分治、倍增、前缀和Basic Algorithm
线性结构数组、链表、栈、队列、单调结构Linear
树形结构二叉/多叉树、树形遍历与统计Tree
图论建图、遍历、最短路、连通性Graph
字符串匹配、哈希、自动机String
哈希散列、冲突处理Hash
动态规划状态设计与转移Dynamic Programming
杂项复杂度分析、位运算、离散化等Misc
C++ 标准库速查容器、算法、数值工具、核心 API、刷题模板LeetCode C++ 标准库速查

复杂度:唯一的硬约束

做题时先估量级,再选方法:

nn可接受复杂度典型算法
n≤20n \le 20O(2n)O(2^n)状态压缩、暴搜 + 剪枝
n≤100n \le 100O(n3)O(n^3)Floyd、区间 DP
n≤1000n \le 1000O(n2)O(n^2)朴素 DP、双重循环
n≤105n \le 10^5O(nlog⁡n)O(n \log n)排序、线段树、堆、二分
n≤106n \le 10^6O(n)O(n)单调栈/队列、双指针、线性 DP
n≥109n \ge 10^9O(log⁡n)O(\log n) 或O(1)O(1)数学、倍增、快速幂

注意常数:O(nlog⁡n)O(n \log n) 的排序和O(nlog⁡n)O(n \log n) 的平衡树,常数可以差 5 倍。10510^5 的规模下,快排 10 ms,红黑树 50 ms,哈希表 15 ms——能排序就别用平衡树。

解题的通用流程

1. 读题,明确:输入规模?求什么(最值/计数/判定/构造)?
2. 暴力怎么写?(先把暴力写清楚,它是后续优化的参照系)
3. 暴力慢在哪?(重复计算?无效枚举?)
4. 针对性的优化手段:
   - 重复计算    → 记忆化 / DP
   - 无效枚举    → 二分 / 双指针 / 单调性剪枝
   - 需快速查询  → 哈希 / 前缀和 / 数据结构
   - 需维护区间  → 线段树 / 树状数组 / 分块
5. 边界检查:空输入、n=1、最大值、重复元素

先写暴力这一步不能省。很多"想不出来"其实是暴力都没想清楚。

常见思维模式

模式适用特征典型手段
缩小规模问题可拆成同类子问题分治、DP、递归
枚举 + 判定答案可验证二分答案、枚举 + check
维护不变量需在线处理数据结构、增量维护
转化视角原问题难,换个等价形式好做建模成图、对偶、补集
先排序元素间有顺序关系排序后双指针、贪心
预处理换查询多次查询前缀和、倍增、离线处理

参考

  • OI Wiki——中文最好的竞赛算法百科
  • CP-Algorithms——按主题组织,代码质量高
  • 《算法导论》(CLRS)——理论严谨
  • 《算法(第 4 版)》(Sedgewick)——工程视角,图多