经典算法思想总结(含 LeetCode 题目推荐)
经典题的价值是覆盖可复用思想,而非提供待背答案。二分利用单调性缩小范围;分治把问题拆成独立子问题再合并;回溯枚举决策树;贪心做可证明安全的局部选择;动态规划缓存重复状态;DFS 与 BFS 负责遍历隐式或显式图。
训练时可按“识别—实现—证明—变式”推进。看到有序数组,先问能否二分或双指针;看到连续区间,考虑滑动窗口、前缀和;看到前 K 个,比较堆和快速选择;看到连通关系,考虑 DFS、BFS、并查集;看到最少次数,判断是否是无权最短路或 DP;看到所有组合,则画回溯树。
每题先给出暴力解和复杂度,再定位瓶颈。例如重复查询区间和,可用前缀和把单次查询从 O(n) 降为 O(1),代价是 O(n) 预处理与空间;重复求同一递归状态,可记忆化;每次扫描极值,可用堆或单调结构。优化必须说明利用了何种约束。
复盘记录应包含:题目模型、关键不变量、易错边界、时间空间复杂度,以及如果条件变化方案会怎样。隔几天脱离答案重写,比连续刷相似题更能检验迁移能力。
误区是以题号替代知识结构、只追求最优代码、忽略数据规模提示,以及把模板当作正确性证明。小结:经典题应成为概念索引。能用自己的话说明为什么排除某些状态、为什么不会漏解,才真正掌握算法思想。
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 Dai Wei!
评论

