文档目录
第一阶段到第三阶段总结
第一阶段(双指针与滑动窗口):
快慢指针 → 检测环、找链表中间点
对撞指针 → 有序数组的两数/三数问题
滑动窗口 → 所有"连续子数组/子串"问题
核心思想:一次遍历 O(N),不用嵌套循环 O(N²)
第二阶段(并发算法):
交替打印 → cv 阻塞 vs atomic 自旋的选择
哲学家就餐 → 限制并发人数防死锁
MPSC 阻塞队列 → 日志系统、生产者-消费者模式
LRU 缓存 → list + unordered_map,O(1) 操作
核心思想:理解同步原语的开销和适用场景
第三阶段(树形结构):
BFS 层序遍历 → 队列模板,右视图、之字形变体
红黑树 → 节点散落、缓存不友好、小数据快
B+ 树 → 块内连续、磁盘友好、范围查询高效
跳表 → 概率平衡、实现简单、范围查询好
核心思想:不同数据结构选择取决于存储介质和访问模式