xfyyzy

Daily Algorithm

每日一个算法主题，按阶段推进。

已完成

预告

阶段0 基础与思维

  • 复杂度入门：大O记号与渐进分析
  • 常见复杂度曲线：O(1) 到 O(2^n)
  • 数学基础：等比/等差、对数与阶乘估算
  • 递归思想：用自我调用描述问题
  • 递归与数学归纳法、循环不变式
  • 常见递推关系与主定理（Master Theorem）
  • 暴力枚举与剪枝的基本套路
  • 测试用例设计与边界条件思维
  • 从伪代码到实现：如何读写算法描述

阶段1 线性结构与排序

  • 数组与顺序存储：随机访问的意义
  • 链表与指针：单链表/双链表/循环链表
  • 栈与队列：表达式求值与BFS中的应用
  • 双端队列与单调队列
  • 哈希表：拉链法与开放定址
  • 集合与映射：基于哈希/树的实现差异
  • 前缀和与差分数组
  • 双指针与滑动窗口
  • 区间处理：扫描、合并与覆盖
  • 线性查找与有序表上的二分查找
  • 插入排序与选择排序
  • 冒泡排序与稳定性讨论
  • 归并排序：分治范式经典案例
  • 快速排序：随机化与三路划分
  • 堆与堆排序：优先队列视角
  • 计数排序与桶排序
  • 基数排序：多关键字/大整数排序
  • Top-K问题：快速选择与堆选择
  • 排序算法综合对比与工程实践
  • 查找表设计：从顺序表到跳表概览

阶段2 递归、搜索与回溯

  • 树的基本概念与遍历：先序/中序/后序/层序
  • 递归与栈帧：函数调用的本质
  • 分治法模板：归并排序与快速幂
  • 二分答案与判定函数设计
  • DFS 深度优先搜索基础
  • BFS 广度优先搜索基础
  • 回溯法框架：子集、排列与组合生成
  • N 皇后与约束满足问题
  • 子集和与组合搜索中的剪枝技巧
  • 搜索顺序与启发式：从暴力到优化
  • 记忆化搜索：自顶向下的动态规划视角
  • 状态空间图与搜索树：如何建模
  • 迭代加深与双向搜索
  • 博弈搜索：极大极小与α−β剪枝
  • 分支限界法：背包与旅行商的搜索求解

阶段3 图论基础

  • 图的表示：邻接矩阵与邻接表
  • 无向图连通性与连通分量
  • 有向图中的可达性问题
  • 图中的BFS/DFS实战：最短路与拓扑排序前置
  • 拓扑排序与有向无环图（DAG）
  • 图中的环检测与有向无环性判断
  • 二分图判定：BFS/DFS 染色法
  • 并查集（Union-Find）与连通块维护
  • 最小生成树：Prim 算法
  • 最小生成树：Kruskal 算法与并查集结合
  • 无权图最短路：BFS 与层次图
  • 单源最短路：Dijkstra 算法（优先队列版）
  • 含负权边最短路：Bellman-Ford 与SPFA
  • 全源最短路：Floyd-Warshall 算法
  • DAG 上的最长/最短路径 DP
  • 强连通分量：Kosaraju/Tarjan 算法
  • 割点与桥：提升图的鲁棒性分析
  • 欧拉回路与欧拉路径：Hierholzer 算法
  • 图的连通度与生成树个数（Kirchhoff 定理概览）
  • 图论建模技巧：流量、匹配与分层图初识

阶段4 动态规划专题

  • 动态规划入门：重叠子问题与最优子结构
  • 从递归到DP：记忆化搜索与自底向上转化
  • 一维DP：斐波那契数列与台阶问题
  • 背包问题 I：0/1 背包
  • 背包问题 II：完全背包与多重背包
  • 背包问题 III：分组背包与混合背包
  • 子序列问题 I：最长上升子序列（LIS）
  • 子序列问题 II：最长公共子序列（LCS）
  • 编辑距离与字符串变换
  • 区间DP：矩阵链乘与石子合并
  • 区间DP：括号匹配与最优加括号
  • 树形DP I：树的直径与重心
  • 树形DP II：换根DP与全局量计算
  • 状态压缩DP I：子集枚举与旅行商问题 TSP
  • 状态压缩DP II：状压匹配与棋盘覆盖
  • 图上DP：DAG 上计数与最长路
  • 数位DP：统计满足条件的数的个数
  • 概率DP：期望值与马尔可夫过程入门
  • DP 优化 I：单调队列优化与斜率优化引入
  • DP 优化 II：分治优化与四边形不等式
  • DP 优化 III：凸Hull Trick 与Li Chao Tree 概览
  • 多维DP：多维状态设计与降维技巧
  • 滚动数组与空间优化
  • DP 常见坑：转移顺序、初始化与无解状态
  • DP 题型综述与建模套路总结

阶段5 高级数据结构与图论进阶

  • 平衡二叉搜索树家族概览：AVL/红黑树/Splay/Treap
  • 红黑树插入与删除思想
  • Splay 树与伸展操作的摊还分析
  • Treap 与随机化平衡思想
  • 跳表（Skip List）与随机化搜索结构
  • 线段树基础：区间求和与区间最值
  • 线段树进阶：懒标记与区间更新
  • 树状数组（Fenwick Tree）与前缀操作
  • 稀疏表（Sparse Table）与RMQ问题
  • 可持久化数据结构：持久化栈/线段树概览
  • 树的重心与重链剖分（HLD）
  • 树上路径问题：LCA（二叉提升）算法
  • 离线算法：Tarjan LCA 与并查集在树上的应用
  • 莫队算法（Mo's Algorithm）与离线分块思想
  • 网络流建模：最大流与最小割定理
  • 最大流算法：Ford-Fulkerson 与 Edmonds-Karp
  • 最大流算法：Dinic 与分层网络
  • 最小费用最大流：SPFA/势能与费用流建模
  • 二分图最大匹配：匈牙利算法与Hopcroft-Karp
  • 一般图匹配与 Edmonds Blossom 算法概览

阶段6 字符串与文本算法

  • 字符串基础与字典序、前后缀概念
  • 朴素字符串匹配与改进策略
  • KMP 算法：部分匹配表与失配跳转
  • Z-Algorithm 与前缀函数
  • Rabin-Karp：滚动哈希与多模式匹配初步
  • Trie 树（前缀树）与字典储存
  • Aho-Corasick 自动机：多模式匹配
  • 后缀数组（Suffix Array）与排名/height 数组
  • 后缀数组构建算法（倍增法等）
  • 后缀自动机（Suffix Automaton）基础
  • 后缀树与Ukkonen算法概览
  • Manacher 算法：线性时间求最长回文子串
  • 最小表示法与字符串旋转最小字典序
  • 字符串哈希：单哈希与双哈希、防冲突技巧
  • 文本压缩算法：Huffman/LZ 家族概览

阶段7 数学与数论算法

  • 整除与余数：从欧几里得算法到扩展欧几里得
  • 快速幂与模运算技巧
  • 线性筛与素数表生成
  • 最小质因子筛与快速分解
  • 组合数计算：杨辉三角与预处理阶乘
  • 大数取模下的排列组合与逆元
  • 中国剩余定理（CRT）与同余方程组
  • 矩阵快速幂与线性递推
  • 离散对数问题与 Baby-step Giant-step
  • FFT 快速傅里叶变换：卷积加速乘法
  • NTT 数论变换与模意义下的卷积
  • Miller-Rabin 随机素性测试
  • Pollard-Rho 随机因数分解算法
  • 概率与期望在算法中的应用
  • 生成函数与计数问题概览

阶段8 计算几何、随机化与工程实践

  • 平面几何基础：向量、点积、叉积与夹角
  • 线段相交判定与常见几何误差坑
  • 凸包算法：Graham Scan 与单调链
  • 旋转卡壳：最远点对与直径问题
  • 多边形面积与点在多边形内判定
  • 随机化算法：随机快速排序与随机选择
  • 随机化数据结构：随机哈希与跳表再访
  • 流式/在线算法：滑动窗口与数据流采样
  • 外存与缓存友好算法概览（B+树/LSM 树）
  • 机器学习中的经典算法：K-Means 与梯度下降