算法

1972年，Robert Tarjan发表了一篇不到五页的论文，提出了一个用单次深度优先搜索求解强连通分量的算法。这个算法不仅解决了有向图的核心问题，其核心思想——发现时间戳与追溯值的配合——后来被证明能够统一解决割点、桥检测、2-SAT可满足性等四大图论难题。Donald Knuth称其为"我最喜欢的实现之一"。 ...

给定一个长度为100万的数组和一个大小为k的滑动窗口，要求输出窗口每次移动后的最大值。最直观的做法是：对每个窗口位置，遍历窗口内的所有元素找出最大值——总的时间复杂度是$O(n \times k)$。当k接近n时，这退化成了$O(n^2)$。 ...

假设你需要从一个装满金条的宝库中选择带走一些金条，但背包容量有限。每根金条有重量和价值，如何在不超过背包容量的前提下，使带走的价值最大？这个看似简单的选择问题，实际上蕴含着动态规划最核心的思想——如何在约束条件下做出最优决策。 ...

1994年，新西兰奥克兰大学的 Peter M. Fenwick 在《Software: Practice and Experience》期刊上发表了一篇题为"A new data structure for cumulative frequency tables"的论文。这篇看似平淡无奇的论文，却发明了一个代码量极小却威力巨大的数据结构——树状数组（Binary Indexed Tree，简称 BIT），也被称为 Fenwick Tree。 ...

给定一棵二叉树，找出其直径——这条路径可能穿过根节点，也可能完全在某个子树中。当你第一次看到 LeetCode 543 这道题时，可能会想：从根节点出发，找到最深的左节点和最深的右节点，把两条路径连起来不就是答案吗？但这个直觉会出错——直径可能根本不经过根节点。 ...

假设你需要在一段百万字的文本中搜索一个关键词。最直观的方法是：将关键词与文本的每个位置逐一比较——时间复杂度 $O(nm)$，其中n是文本长度，m是关键词长度。当文本达到百万级别时，这个算法可能需要数秒甚至更长。 ...

假设你需要统计小于1000万的整数中有多少个素数。最直观的想法是：对每个数逐一判断是否为素数——时间复杂度 $O(n\sqrt{n})$，当数据量达到千万级别时，程序可能需要运行数秒甚至数分钟。但如果换一个思路：用一个布尔数组标记所有合数，剩下的就是素数——时间复杂度骤降至 $O(n \log \log n)$，千万级数据量下只需几十毫秒。 ...