并查集与搜索的联系

在 LeetCode 上练习时了解到,并查集 这一数据结构比较常用于解决图论方面的问题,其应用场景与搜索有很多重叠。例如,两者都可用于求无向图中连通分量 (connected component or just component)的个数。下图1中就有三个连通分量,分别以不同颜色标出: LeetCode 例题:547. 省份数量 并查集 鉴于 STL 没有实现并查集(已知 Boost 有),我们需要自己动手实现:以 vector<int> 为本体,辅以 get_root() 和 merge_set() 两个函数,即可完成。注意,此实现舍弃了性能的完整性2,追求的目标是代码量小、功能够用,适用于做题和笔试场景。 值得注意的 …

【前缀+Hash】与【双指针】的区别

注:双指针法俗称“滑动窗口”,但我不喜欢这个名称,因为这给人感觉是一个固定长度的窗口在(数组上)滑动,而实际上该方法中的“窗口”长度不是固定的,更像个手风琴或弹簧。 例题 前缀+Hash:560. 和为K的子数组 给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。 示例 1 : 1输入:nums = [1,1,1], k = 2 2输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。 题解: 1class Solution { 2public: 3 int subarraySum(vector<int>& nums, int k) { 4 …

差分数列

概念 数列 $a$,$b$ 满足以下条件: $$ \begin{align*} b_1 &= a_1\\ b_2 &= a_2 - a_1\\ &\vdots\\ b_n &= a_n - a_{n-1} \end{align*} $$ 故有: $$ \begin{align*} a_1 &= b_1\\ a_2 &= b_1 + b_2\\ &\vdots\\ a_n &= b_1 + b_2 + \cdots + b_n \end{align*} $$ 其中称 $b$ 为 $a$ 的差分(Difference Array),$a$ 为 $b$ 的前缀和(Prefix Sum Array)。两者为一组逆运算。 用法 差分数列的一个 …