Nanxa的小站

2026-05-18 804 字 4 分钟

图论算法全解析（五）：二分图、桥与割点、带权并查集与全系列总结

攻克三种进阶图论技巧——二分图判定（染色 DFS/BFS）、Tarjan 算法求桥（LeetCode 1192）、带权并查集（LeetCode 399），并以全系列复盘对照表为五篇体系画上句号。

2026-05-18 853 字 5 分钟

掌握拓扑排序的两种实现方法——Kahn 算法（入度表 + BFS）与 DFS 后序遍历，理解 DAG 上 DP 的建模思路，并通过三道经典题（LeetCode 207、210、802）融会贯通。

2026-05-18 651 字 4 分钟

掌握最小生成树的两大经典算法——Kruskal（边排序 + 并查集）与 Prim（贪心 + 优先队列），并从并查集的路径压缩和按秩合并出发，理解其近乎 $O(1)$ 的均摊效率（LeetCode 1584、684）。

2026-05-18 907 字 5 分钟

系统掌握三种经典最短路径算法——Dijkstra（贪心 + 优先队列）、Bellman-Ford（DP + 负权边检测）、Floyd-Warshall（区间 DP 的全源最短路），并通过三道 LeetCode 题目（743、787、1334）建立算法选择决策树。

2026-05-18 1050 字 5 分钟

从图的两种存储方式（邻接表 vs 邻接矩阵）出发，掌握 BFS 的最短路径语义与 DFS 的连通性语义，并学习将二维网格建模为隐式图的通用套路（LeetCode 200、695、994）。

2026-05-18 734 字 4 分钟

从「下一更大元素」模式翻转为「柱状图最大矩形」模式，理解递增栈在高与宽计算中的关键作用，攻克二维扩展和贪心+单调栈的混合应用（LeetCode 84、85、402），并以全系列复盘对照表收官。

2026-05-18 552 字 3 分钟

从暴力解法的 O(n²) 瓶颈出发，理解单调栈如何利用「剔除无效候选」将复杂度降到 O(n)，掌握递增栈与递减栈的选择规则和通用代码模板，并通过三道经典题（LeetCode 496、503、739）深入下一更大元素模式。

2026-05-18 650 字 4 分钟

攻克 DP 的三种进阶技巧——状态压缩、树形 DP 与区间 DP 扩展，通过三道综合题（LeetCode 337、139、152）融会贯通，并以全系列复盘对照表为五篇体系画上句号。

2026-05-18 934 字 5 分钟

掌握双串 DP 的核心模式——最长公共子序列（LCS）、编辑距离、最长递增子序列（LIS）的 O(n log n) 优化，以及回文子串的区间 DP 建模（LeetCode 1143、300、72、5）。

2026-05-18 747 字 4 分钟

从 0/1 背包的二维定义到一维滚动数组的空间优化，深入理解完全背包的转移方程差异，并通过循环顺序的微妙变化区分「组合数」与「排列数」（LeetCode 416、322、518）。