学习周报-02-算法

前言：

本周已学习：

最大公约数、同余定理
对数器与暴力打表找规律
技巧：根据数据规模猜题解
前缀树
前缀和、差分
滑动窗口
双指针
二分答案
单调栈、单调队列
并查集
洪水填充

其中涉及一些关于数论的结论，一些经验结论，以及两个新的数据结构（前缀树、并查集），和原有数据结构的新用法（单调栈、单调队列），同时学习了如何通过构建前缀信息以快速查询，还有通过差分数组传播影响，而洪水填充是一个dfs算法，真的很符合直觉，法如其名。

最大公约数、同余定理

怎么求最大公约数和最小公倍数？- 辗转相除法

证明辗转相除法就是证明如下关系：
gcd(a, b) = gcd(b, a % b
假设a % b = r，即需要证明的关系为：
gcd(a, b) = gcd(b, r)
证明过程：
因为a % b = r，所以如下两个等式必然成立
1) a = b * q + r，q为0、1、2、3….中的一个整数
2) r = a − b * q，q为0、1、2、3….中的一个整数
假设u是a和b的公因子，则有: a = s * u, b = t * u
把a和b带入2)得到，r = s * u - t * u * q = (s - t * q) * u
这说明 : u如果是a和b的公因子，那么u也是r的因子
假设v是b和r的公因子，则有: b = x * v, r = y * v
把b和r带入1)得到，a = x * v * q + y * v = (x * q + y) * v
这说明 : v如果是b和r的公因子，那么v也是a的公因子
综上，a和b的每一个公因子也是 b和r的一个公因子，反之亦然
所以，a和b的全体公因子集合 = b和r的全体公因子集合
即gcd(a, b) = gcd(b, r)

代码实现：

    // cpp实现
    long gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    long lcm(int a, int b) {
        return a / gcd(a, b) * b;
    }

例题分析：

1
2
3

题目：魔数的数量
https://leetcode.cn/problems/nth-magical-number/

同余定理

数学上的证明就不多说了，
总之就是用在大数据需要返回mod大质数结果的情况下，
我们可以通过对每个中间结果mod也能得出答案。

除法需要逆元特殊处理。

对数器与暴力打表找规律

使用场景：入参是简单类型，出参也是简单类型。
一般而言，用最暴力的实现进行求解，并在入参不大的情况下，
打表找规律，最后把规律变为代码。

例题分析：

1	题目: 要求只有一个长度>=2的回文子串，求所有长度为n的red字符串中好串的数量

分析：我们先分析基础情况，然后暴力打表（递归暴力搜索），打印出n在前100的答案，然后观察规律
最后发现了规律：

static long long num(long long n) {
	if (n == 1) {
		return 0;
	}
	if (n == 2) {
		return 3;  // "rr", "ee", "dd"
	}
	if (n == 3) {
		return 18; // 根据规律观察得到
	}
	// 通用公式： 6 * (n + 1) % 1000000007
	const long long MOD = 1000000007LL;
	return (6LL * (n + 1)) % MOD;
}

根据数据量猜解法

C/C++运行时间1s，
java/python/go等其他语言运行时间1s~2s，
对应的常数指令操作量是 10^7 ~ 10^8，
不管什么测试平台，不管什么cpu，都是这个数量级。
所以可以根据这个基本事实，
来猜测自己设计的算法最终有没有可能在规定时间内通过
也可以自己猜测一下大概的步数。
时间复杂度的估计很多时候并不是一个入参决定，
可能是多个入参共同决定。比如O(nm), O(n+m)等
所以最关键的就是记住常数指令操作量是 10^7 ~ 10^8，
然后方法是什么复杂度就可以估计能否通过了

问题规模	logn	n	n*logn	n*根号n	n^2	2^n	n!
n <= 11	Yes	Yes	Yes	Yes	Yes	Yes	Yes
n <= 25	Yes	Yes	Yes	Yes	Yes	Yes	No
n <= 5000	Yes	Yes	Yes	Yes	Yes	No	No
n <= 10^5	Yes	Yes	Yes	Yes	No	No	No
n <= 10^6	Yes	Yes	Yes	No	No	No	No
n <= 10^7	Yes	Yes	No	No	No	No	No
n >= 10^8	Yes	No	No	No	No	No	No

例题分析：

题目1 : 最优的技能释放顺序

https://www.nowcoder.com/practice/d88ef50f8dab4850be8cd4b95514bbbd

现在有一个打怪类型的游戏，这个游戏是这样的，你有n个技能
每一个技能会有一个伤害，
同时若怪物小于等于一定的血量，则该技能可能造成双倍伤害
每一个技能最多只能释放一次，已知怪物有m点血量
现在想问你最少用几个技能能消灭掉他(血量小于等于0)
技能的数量是n，怪物的血量是m
i号技能的伤害是x[i]，i号技能触发双倍伤害的血量最小值是y[i]
1 <= n <= 10
1 <= m、x[i]、y[i] <= 10^6

n的规模暗示了可接受的算法复杂度是n的阶乘，那么很容易就能想到是全排列。

题目2：超级回文数的数目

https://leetcode.cn/problems/super-palindromes/

如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为超级回文数。
现在，给定两个正整数 L 和 R （以字符串形式表示），
返回包含在范围 [L, R] 中的超级回文数的数目。
1 <= len(L) <= 18
1 <= len(R) <= 18
L 和 R 是表示 [1, 10^18) 范围的整数的字符串

10^18，这很大啊，这就让我们不得不去想一些特殊解法
如果把题目问题看为主问题，那么求我们是不是可以先求超级回文数的开方是否回文从而逆向验证主问题呢？（这好像叫种子问题？）
如果用这个思路，规模直接下降到了sqrt（10^18）变成了10^9。
好像还是有点大了，我们能不能再次找到种子问题二，从而再度下降问题规模呢？
有点兄弟有的，我们只需要构造种子问题一的前半数据并验证即可：

1 2	对于前半部分数据：123 可以构造出回文数：12321 与 123321

此时规模又缩减sqrt（10^9) 变成了 10^5。
整理思路：

1
2
3

sd2() -> sd1() -> main()
一个满足main的问题，首先必须要满足sd1，而问题sd1必须要满足sd2。
总之，我们只需要枚举小规模的数字，然后通过链条逐渐放大即可。

通过打表可以优化为直接返回列表中的记录~：

    // 预先计算的超级回文数的平方值列表
    const vector<long long> record = {
        1L, 4L, 9L, 121L, 484L, 10201L, 12321L, 14641L, 40804L, 44944L,
        1002001L, 1234321L, 4008004L, 100020001L, 102030201L, 104060401L,
        121242121L, 123454321L, 125686521L, 400080004L, 404090404L,
        10000200001L, 10221412201L, 12102420121L, 12345654321L,
        40000800004L, 1000002000001L, 1002003002001L, 1004006004001L,
        1020304030201L, 1022325232201L, 1024348434201L, 1210024200121L,
        1212225222121L, 1214428244121L, 1232346432321L, 1234567654321L,
        4000008000004L, 4004009004004L, 100000020000001L, 100220141022001L,
        102012040210201L, 102234363432201L, 121000242000121L,
        121242363242121L, 123212464212321L, 123456787654321L,
        400000080000004L, 10000000200000001L, 10002000300020001L,
        10004000600040001L, 10020210401202001L, 10022212521222001L,
        10024214841242001L, 10201020402010201L, 10203040504030201L,
        10205060806050201L, 10221432623412201L, 10223454745432201L,
        12100002420000121L, 12102202520220121L, 12104402820440121L,
        12122232623222121L, 12124434743442121L, 12321024642012321L,
        12323244744232321L, 12343456865434321L, 12345678987654321L,
        40000000800000004L, 40004000900040004L, 1000000002000000001L,
        1000220014100220001L, 1002003004003002001L, 1002223236323222001L,
        1020100204020010201L, 1020322416142230201L, 1022123226223212201L,
        1022345658565432201L, 1210000024200000121L, 1210242036302420121L,
        1212203226223022121L, 1212445458545442121L, 1232100246420012321L,
        1232344458544432321L, 1234323468643234321L, 4000000008000000004L
    };
};

前缀树

前缀树又叫字典树，英文名trie，
这个名字来源于英文单词“retrieval”（检索），因为前缀树是一种专门用于高效检索和存储字符串的数据结构。它的命名是为了突出其在信息检索中的应用。
每个样本都从头节点开始根据前缀字符或者前缀数字建出来的一棵大树，就是前缀树
前缀树的使用场景：需要根据前缀信息来查询的场景
前缀树的优点：根据前缀信息选择树上的分支，可以节省大量的时间
前缀树的缺点：比较浪费空间，和总字符数量有关，字符的种类有关
前缀树的定制：pass、end等信息
对于前缀树的建立有两种方法，
一种是通过动态结构建立前缀树，一种是通过静态数组建立。
在工程上我们一般通过动态结构来确保工程上的安全性，
而比赛中为了追求极致效率，一般我们就直接用静态数组构建前缀树。

总结就是：没有路就新建节点；已经有路了，就复用节点。

graph TD
    root((root))
    root --> a1(a)
    a1 --> p1(p)
    p1 --> p2(p)
    p2 --> l(l)
    l --> e(e)
    p2 --> app["app"]
    e --> apple["apple"]
    root --> b1(b)
    b1 --> a2(a)
    a2 --> n(n)
    n --> a3(a)
    a3 --> banana["banana"]
    n --> d(d)
    d --> band["band"]
    style app fill:#f9f,stroke:#333,stroke-width:2px
    style apple fill:#f9f,stroke:#333,stroke-width:2px
    style banana fill:#f9f,stroke:#333,stroke-width:2px
    style band fill:#f9f,stroke:#333,stroke-width:2px

例题分析：

题目1 接头密匙

https://www.nowcoder.com/practice/c552d3b4dfda49ccb883a6371d9a6932

牛牛和他的朋友们约定了一套接头密匙系统，用于确认彼此身份
密匙由一组数字序列表示，两个密匙被认为是一致的，如果满足以下条件：
密匙 b 的长度不超过密匙 a 的长度。
对于任意 0 <= i < length(b)，有b[i+1] - b[i] == a[i+1] - a[i]
现在给定了m个密匙 b 的数组，以及n个密匙 a 的数组
请你返回一个长度为 m 的结果数组 ans，表示每个密匙b都有多少一致的密匙
数组 a 和数组 b 中的元素个数均不超过 10^5
1 <= m, n <= 1000

用前缀树方法：
时间复杂度，O(a数组的数字个数 * 10) + O(b数组的数字个数 * 10)
空间复杂度，O(a数组的数字个数 * 10)，这是树上的节点数量

将数字序列的差分数组转换为字符串表示
例如原差分[1, -3, 9] -> "1#-3#9#"
这样就可以防止大量Path消耗大量内存

题目2 数组中两个数的最大异或值

https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/

给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0<=i<=j<=n
1 <= nums.length <= 2 * 10^5
0 <= nums[i] <= 2^31 - 1
前缀树做法 & 哈希表做法
时间复杂度O(n * logV)，空间复杂度O(n * logV)，V是数值范围

把x数字看作一个二进制串
得到了一个类似”00100…..001110”的东西。
所谓 x xor y 得到最大，
就是从高位向下检索，尽可能走的满足 x 与 y的当前相等位状态相反的路径。
这就是天然的前缀思路，故前缀树解法显现。

题目3 在二维字符数组中搜索可能的单词

https://leetcode.cn/problems/word-search-ii/

给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words
返回所有二维网格上的单词。单词必须按照字母顺序，通过 相邻的单元格 内的字母构成
其中“相邻”单元格是那些水平相邻或垂直相邻的单元格
同一个单元格内的字母在一个单词中不允许被重复使用
1 <= m, n <= 12
1 <= words.length <= 3 * 10^4
1 <= words[i].length <= 10

时间复杂度，O(m * n * 4^10)
不管用不用前缀树都是这个复杂度，只不过前缀树可以大量剪枝，优化常数时间
空间复杂度，O(words中所有字符串的全部字符数量)

一眼trie + dfs, 图遍历嘛，用dfs很好理解，但trie在哪？
trie在于把给定要搜索的单词作为路径放入前缀树中，
相当于dfs在搜索的时候持有一个地图，如果地图上显示没路可走了，那就直接cut。
trie妙用：
1. end属性存储字符串便于收获结果
2. 在收获答案往回退时顺便减去pass属性，如果下次再来，访问到pass属性== 0就cut

前缀和、差分

前缀和

前缀和是通过滚动求和记录当前位置累加和所构建的数组，
是一种通过保留前缀信息以减少查询时间的技巧。
所谓前缀和实际上就是区间和。
记录的是 0~~1、0~~2、0~~3直到0~~n的区间的累加和。
而由两个大小区间相减我们便可以得到所需区间的值。
例如我们如果需要4~~5区间的值，完全可以拿0~~5 - 03区间的值，
这样便剩下了45区间的值。

例题分析：构建前缀信息的技巧-解决子数组相关问题

解决如下问题，时间复杂度O(n)

题目1 : 构建前缀和数组。快速解决子数组范围求和的问题
测试链接 : https://leetcode.cn/problems/range-sum-query-immutable/
题目2 : 构建前缀和最早出现的位置。返回无序数组中累加和为给定值的最长子数组长度
测试链接 : https://www.nowcoder.com/practice/36fb0fd3c656480c92b569258a1223d5
题目3 : 构建前缀和出现的次数。返回无序数组中累加和为给定值的子数组数量
测试链接 : https://leetcode.cn/problems/subarray-sum-equals-k/
题目4 : 构建前缀和最早出现的位置。返回无序数组中正数和负数个数相等的最长子数组长度
测试链接 : https://www.nowcoder.com/practice/545544c060804eceaed0bb84fcd992fb
题目5 : 构建前缀和最早出现的位置。表现良好的最长时间段问题
测试链接 : https://leetcode.cn/problems/longest-well-performing-interval/
题目6 : 构建前缀和余数最晚出现的位置。移除的最短子数组长度，使得剩余元素的累加和能被p整除
测试链接 : https://leetcode.cn/problems/make-sum-divisible-by-p/
题目7 : 构建前缀奇偶状态最早出现的位置。每个元音包含偶数次的最长子串长度
测试链接 : https://leetcode.cn/problems/find-the-longest-substring-containing-vowels-in-even-counts/

差分数组

差分实际上是在前缀和技巧的基础上传播影响的技巧
例如你想要在数组上对 n~m区间加上一个数 x，其他区间不变。
实际上你只需要在差分数组上在n位置加上x，而在m + 1位置减去 x，然后使用前缀和构建数组后你会发现，n位置上的影响会自动传播，覆盖n ~ 结尾的区间，所以也就是为什么我们需要在m + 1 的位置减去x，这样可以覆盖掉来自n位置对m ~ 结尾的影响。
对于二维也是如此。

一维差分：太简单了，没有理解难度。不支持边操作、边查询。

等差数列差分问题描述：
一开始1n范围上的数字都是0。接下来一共有m个操作。
每次操作：lr范围上依次加上首项s、末项e、公差d的数列
最终1~n范围上的每个数字都要正确得到

等差数列差分的过程：
每个操作调用set方法
所有操作完成后在arr上生成两遍前缀和，即调用build方法
arr里就是最终1~n范围上的每个数字

例题分析：

题目1

航班预订统计测试链接：https://leetcode.cn/problems/corporate-flight-bookings/

这里有 n 个航班，它们分别从 1 到 n 进行编号。
有一份航班预订表 bookings ，
表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi]
意味着在从 firsti 到 lasti 
包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。
请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。

标准差分做法，建立差分数组，然后通过前缀和技巧收集答案。

题目2

等差数列差分模版测试链接：https://www.luogu.com.cn/problem/P4231

一开始1~n范围上的数字都是0，一共有m个操作，每次操作为(l,r,s,e,d)
表示在l~r范围上依次加上首项为s、末项为e、公差为d的数列
M个操作做完之后，统计1~n范围上所有数字的最大值和异或和
1 <= n <= 10^7
1 <= m <= 3 * 10^5
1 <= l <= r <= n

题目3

等差数列差分经典题目测试链接 : https://www.luogu.com.cn/problem/P5026

1
2
3

一群人落水后求每个位置的水位高度
问题描述比较复杂，见测试链接
注意：这道题OFFSET的设计，可以避免大量的边界讨论

如果把一般差分对后续区间的影响看做一条直线，那么等差数列差分便是一条斜线线。

二维前缀和

为什么我们要构建二维前缀和？
目的是预处理出一个结构，以后每次查询二维数组任何范围上的累加和都是O(1)的操作

1 根据原始状况，生成二维前缀和数组sum，
   sum[i][j]: 代表左上角(0,0)到右下角(i,j)这个范围的累加和
   sum[i][j] += sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1];
2 查询左上角(a,b)到右下角(c,d)这个范围的累加和
   sum[c][d] - sum[c][b-1] - sum[a-1][d] + sum[a-1][b-1];
3 实际过程中往往补第0行、第0列来减少很多条件判断。
  当然也可以不补。根据个人习惯决定。

二维差分

在二维数组中，如果经历如下的过程
1 批量的做如下的操作，每个操作都有独立的a、b、c、d、v
void add(a, b, c, d, v) : 左上角(a,b)到右下角(c,d)范围上，每个数字+v，怎么快速处理？
2 操作做完后，如何正确得到二维数组中每个位置的值？

这就是二维差分的主要工作，add时候快速处理，最后build得到每个位置的值，修改操作必须集中在一起，不能边修改边查询。
1）add方法实现，比较巧妙！
2）build方法实现，和处理前缀和类似
3）真实数据用一圈0包裹起来，可以减少很多边界讨论

例题分析：

题目1

二维前缀和模版
https://leetcode.cn/problems/range-sum-query-2d-immutable/

题目2

边框为1的最大正方形
测试链接 : https://leetcode.cn/problems/largest-1-bordered-square/

1
2
3

给你一个由若干 0 和 1 组成的二维网格 grid
请你找出边界全部由 1 组成的最大 正方形 子网格
并返回该子网格中的元素数量。如果不存在，则返回 0。

就是整个正方形扣掉中间那一块计算出来的值是不是等于边界全由一组成的值就行。

题目3

二维差分模版
https://www.nowcoder.com/practice/50e1a93989df42efb0b1dec386fb4ccc
https://www.luogu.com.cn/problem/P3397

题目4

用邮票贴满网格图
测试链接 : https://leetcode.cn/problems/stamping-the-grid/

给你一个 m * n 的二进制矩阵 grid
每个格子要么为 0 （空）要么为 1 （被占据）
给你邮票的尺寸为 stampHeight * stampWidth
我们想将邮票贴进二进制矩阵中，且满足以下 限制 和 要求 ：
覆盖所有空格子，不覆盖任何被占据的格子
可以放入任意数目的邮票，邮票可以相互有重叠部分
邮票不允许旋转，邮票必须完全在矩阵内
如果在满足上述要求的前提下，可以放入邮票，请返回 true ，否则返回 false

遍历所有可能放置邮票的左上角位置 (i, j)
计算 (i, j) 到 (i + stampHeight - 1, j + stampWidth - 1) 这个区域的和
计算 cnt 的前缀和，用于快速查询某个区域是否有邮票
检查所有的 0 是否都被覆盖

题目5

重要！包含离散化技巧！

最强祝福力场
测试链接 : https://leetcode.cn/problems/xepqZ5/

小扣在探索丛林的过程中，无意间发现了传说中"落寞的黄金之都"
而在这片建筑废墟的地带中，小扣使用探测仪监测到了存在某种带有「祝福」效果的力场
经过不断的勘测记录，小扣将所有力场的分布都记录了下来
forceField[i] = [x,y,side] 
表示第 i 片力场将覆盖以坐标 (x,y) 为中心，边长为 side 的正方形区域。
若任意一点的 力场强度 等于覆盖该点的力场数量
请求出在这片地带中 力场强度 最强处的 力场强度
注意：力场范围的边缘同样被力场覆盖。

由于本题可能要我们处理类似1.5、0.5之类的值，但是我们期望继续使用整型处理，
这里使用离散化技巧，我们可以让所有的坐标倍增一个倍数，类似于整体拉长整个坐标，于是我们就可以发现，原来的不好处理的数字现在落到了好处理的坐标上，而且所有的相对位置都没有发生改变。
有种分辨率变大的感觉~

本题就是通过构建二维差分数组，计算叠加每次立场的强度，然后最后找到最大强度即可。
但是坑点在于数字很大，n会来到10^9的规模，怎么办呢？
这时候就要处理数据，
我们可以记录每一个点x坐标所在位置
例如1、73、103、1009、114514
然后将其映射到：1、2、3、4、5,同理处理y坐标。
这样我们就发现我们可以省下很多没用到的坐标。

滑动窗口

滑动窗口：维持左、右边界都不回退的一段范围，来求解很多子数组（串）的相关问题
滑动窗口的关键：找到范围和 答案指标 之间的单调性关系（类似贪心）
滑动过程：滑动窗口可以用简单变量或者结构来维护信息
求解大流程：求子数组在每个位置开头或结尾情况下的答案（开头还是结尾在于个人习惯）

例题分析：

题目1

累加和大于等于target的最短子数组长度
测试链接 : https://leetcode.cn/problems/minimum-size-subarray-sum/

1
2
3

给定一个含有 n 个正整数的数组和一个正整数 target
找到累加和 >= target 的长度最小的子数组并返回其长度
如果不存在符合条件的子数组返回0

维持一个累加和大于 target的滑窗，然后沿途记录滑窗size的最大值即可。

题目2

无重复字符的最长子串
测试链接 : https://leetcode.cn/problems/longest-substring-without-repeating-characters/

1	给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

维持一个不重复字符的滑窗，沿途收集最大size。

题目3

最小覆盖子串
测试链接 : https://leetcode.cn/problems/minimum-window-substring/

1 2	给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

维持一个含有t中所有字符的滑窗（可以用used数组实现），然后记录最小size即可

题目4

加油站
测试链接 : https://leetcode.cn/problems/gas-station/

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，
从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升
你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周
则返回出发时加油站的编号，否则返回 -1
如果存在解，则 保证 它是 唯一 的。

环形数组滑窗：

如果总油量不小于总消耗量，则一定有解。
当 currentSum < 0 时，说明此前的起始点不可行，更新 startIndex。
最终返回 startIndex 作为起点，或者返回 -1 表示无法绕一圈。

题目5

测试链接 : https://leetcode.cn/problems/replace-the-substring-for-balanced-string/

替换子串得到平衡字符串
有一个只含有'Q','W','E','R'四种字符，且长度为n的字符串，n一定为4的整数倍
假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」
给你一个这样的字符串s，请通过「替换一个子串」的方式，
使原字符串s变成一个「平衡字符串」
子串可以替换成由'Q','W','E','R'四种字符组成的任何样子
请返回待替换子串的最小可能长度
如果原字符串自身就是一个平衡字符串，则返回0

要点：不够四分之一要补足，够了四分之一就不用关了。

题目6

K个不同整数的子数组
测试链接 : https://leetcode.cn/problems/subarrays-with-k-different-integers/

给定一个正整数数组 nums和一个整数 k，返回 nums 中 「好子数组」 的数目。
如果 nums 的某个子数组中不同整数的个数恰好为 k
则称 nums 的这个连续、不一定不同的子数组为 「好子数组 」。
例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。
子数组 是数组的 连续 部分。

维护cnt数组辅助记录出现次数信息，在入窗时检测次数合法性。

题目7

至少有K个重复字符的最长子串
测试链接 : https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/

1
2
3

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串
要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度
如果不存在这样的子字符串，则返回 0。

每次要求子串必须含有 require 种字符，每种字符都必须>=k次，这样的最长子串是多长
collect : 窗口中一共收集到的种类数
satisfy : 窗口中达标的种类数(次数>=k)

双指针

设置两个指针的技巧，其实这种说法很宽泛，似乎没什么可总结的
1）有时候所谓的双指针技巧，就单纯是代码过程用双指针的形式表达出来而已。
没有单调性（贪心）方面的考虑
2）有时候的双指针技巧包含单调性（贪心）方面的考虑，牵扯到可能性的取舍。
对分析能力的要求会变高。其实是先有的思考和优化，然后代码变成了双指针的形式。
3）所以，双指针这个“皮”不重要，分析题目单调性（贪心）方面的特征，这个能力才重要。

常见的双指针类型：
1）同向双指针
2）快慢双指针
3）从两头往中间的双指针
4）其他

例题分析：

题目1

按奇偶排序数组II
测试链接 : https://leetcode.cn/problems/sort-array-by-parity-ii/

给定一个非负整数数组 nums。nums 中一半整数是奇数 ，一半整数是偶数
对数组进行排序，以便当 nums[i] 为奇数时，i也是奇数
当 nums[i] 为偶数时， i 也是 偶数
你可以返回 任何满足上述条件的数组作为答案
不同的说法，同一个题：
给定一个数组arr，请把arr调整成 奇数都在奇数位置 或者 偶数都在偶数位置

第一眼我们可能会想到，可以开一个辅助数组，然后遍历原数组，
将对应的数放在对应位置上。
双指针则是优化了空间，我们其实不需要开这个数组，
我们可以一个指针固定看数组最后一位的偶数位，
然后以另一指针指向奇数位，如果位置上已经奇数则跳下一个奇数位，如果位置上是偶数则发货至偶数位，偶数位指针往前跳。

题目2

寻找重复数
测试链接 : https://leetcode.cn/problems/find-the-duplicate-number/

给定一个包含 n + 1 个整数的数组 nums ，
其数字都在 [1, n] 范围内（包括 1 和 n）
可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

实际上本题可以转换为图的连通分量求环
直接使用经典双指针算法：Floyd 判环法，寻找相遇点。

题目3

接雨水
测试链接 : https://leetcode.cn/problems/trapping-rain-water/

1 2	给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水

经典接雨水。
接雨水的本质就是对于某一个柱子i，会有一个水线，
而水线来自左右区间的极值较小值，
所蓄的水量则为高度减去水线。
我们可以构建两个数组用于存储左->右区间的极值和左<-右区间的极值，用于快速查询。
而双指针妙就妙在优化掉了这两个辅助数组。
双指针一个指向1位置，另一个指向末尾减去2的位置，然后分别设定极值为0位置和末尾位置的值。对于左右指针，左指针的左极值是真实的，而右区间极值是待定的，反之则反。
可以看出，如果左指针的左极值要成为计算水线的值，那么左指针就可以马上收获答案，反之则反。
这样就不需要额外维护两个数组了。

题目4

救生艇
测试链接 : https://leetcode.cn/problems/boats-to-save-people/

给定数组 people
people[i]表示第 i 个人的体重 ，船的数量不限
每艘船可以承载的最大重量为 limit
每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit
返回 承载所有人所需的最小船数
扩展：
再增加一个要求，如果两人一船那么体重之和必须是偶数，又该怎么做？（大厂真考过）

注意到排序不会影响答案，果断排序。
排完序之后，直接贪心算法，尽量大匹配尽量小。
如果两者匹配之后能坐下一艘船就坐，坐不下就让大的坐。
转换为代码就是两枚指针，l指向开头，r指向末尾，
左右指针不断的用以上逻辑往中间移动即可。
最后结束循环再判断一下l == r ? 如果相等就意味着还有一个没被分配，
为其单独分配一艘船，ans++即可。

题目5

盛最多水的容器
测试链接 : https://leetcode.cn/problems/container-with-most-water/

给定一个长度为 n 的整数数组 height
有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水
返回容器可以储存的最大水量
说明：你不能倾斜容器

思路是这样的，左右指针往开头结尾一放，往中间走，谁小移动谁，移动时记录极值。
至于为什么，实际上是大的被待定了，它期望小的往下走能遇到更大的。

题目6

供暖器
测试链接 : https://leetcode.cn/problems/heaters/

冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
在加热器的加热半径范围内的每个房屋都可以获得供暖。
现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置
请你找出并返回可以覆盖所有房屋的最小加热半径。
说明：所有供暖器都遵循你的半径标准，加热的半径也一样。

也是先排序，然后两个数组分别放置指针指向开头。
然后往后匹配，每个房屋都尽可能的匹配能遇到的最往右的最短距离取暖器，并在其中记录最远距离。

题目7

缺失的第一个正数
测试链接 : https://leetcode.cn/problems/first-missing-positive/

1
2
3

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
玩概念了！

我们把整个区间分为
(整理区) l (待定区) r (垃圾区)
l的左边，都是做到i位置上放着i+1的区域
永远盯着l位置的数字看，看能不能扩充(l++)
最好的状况下，认为1~r是可以收集全的，每个数字收集1个，不能有垃圾
有垃圾呢？预期就会变差(r–)
在所有元素都被整理完毕之后（垃圾去往垃圾区，期望元素进入整理区）
答案自然就出现了。

二分答案

二分答案法
1）估计最终答案可能的范围是什么，可以定的粗略，反正二分不了几次
2）分析问题的答案和给定条件之间的单调性，大部分时候只需要用到自然智慧
3）建立一个check函数，当答案固定的情况下，判断给定的条件是否达标
4）在最终答案可能的范围上不断二分搜索，每次用check函数判断，直到二分结束，找到最合适的答案
核心点：分析单调性、建立check函数
为什么要这样做？很多时候我们面对的问题没有一个确切的目标不好求，
但是如果我们有了一个确切目标，例如例题一中我们假设能够达到速度k，
你会发现我们就很好去设计代码验证答案。

这个技巧常用且重要，一定要引起重视，非常的美、精妙！

例题分析：

题目1

爱吃香蕉的珂珂
测试链接 : https://leetcode.cn/problems/koko-eating-bananas/

珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉
警卫已经离开了，将在 h 小时后回来。
珂珂可以决定她吃香蕉的速度 k （单位：根/小时)
每个小时，她将会选择一堆香蕉，从中吃掉 k 根
如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉
珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）

经典二分答案
(…不能满足…)…ans…(…能满足…)

题目2

分割数组的最大值(画匠问题)
测试链接 : https://leetcode.cn/problems/split-array-largest-sum/

1
2
3

给定一个非负整数数组 nums 和一个整数 m
你需要将这个数组分成 m 个非空的连续子数组。
设计一个算法使得这 m 个子数组各自和的最大值最小。

一样的，只是check函数的设计需要巧妙设计。
if (check(nums, mid) <= k)作为核心点

int check(vector<int> &nums, int limit) {
	int part = 1, sum = 0;
	for (int num : nums) {
		if (num > limit) {
			return INT_MAX;"如果num都比limit大那就没有讨论的必要了。"
		}
		if (sum + num  > limit) {
			part++;
			sum = num;
		} else {
			sum += num;
		}
	}
	return part;
}

题目3

机器人跳跃问题
测试链接 : https://www.nowcoder.com/practice/7037a3d57bbd4336856b8e16a9cafd71

机器人正在玩一个古老的基于DOS的游戏，游戏中有N+1座建筑，从0到N编号，从左到右排列
编号为0的建筑高度为0个单位，编号为i的建筑的高度为H(i)个单位
起初， 机器人在编号为0的建筑处
每一步，它跳到下一个（右边）建筑。假设机器人在第k个建筑，且它现在的能量值是E
下一步它将跳到第个k+1建筑
它将会得到或者失去正比于与H(k+1)与E之差的能量
如果 H(k+1) > E 那么机器人就失去H(k+1)-E的能量值
否则它将得到E-H(k+1)的能量值
游戏目标是到达第个N建筑，在这个过程中，能量值不能为负数个单位
现在的问题是机器人以多少能量值开始游戏，才可以保证成功完成游戏

bool check(vector<int> &buildings, long long e) {
    int max = *max_element(buildings.begin(), buildings.end());
    for (auto building : buildings) {
        e -= building - e;
        if (e >= max) break;"有坑，tmd如果不提前退出long long都能给你爆了"
        if (e <= 0) return false;
    }
    return true;
}

题目4

找出第K小的数对距离
测试链接 : https://leetcode.cn/problems/find-k-th-smallest-pair-distance/

数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。
给你一个整数数组 nums 和一个整数 k
数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length
返回 所有数对距离中 第 k 小的数对距离。

if (check(nums, mid) >= k)

int check(vector<int> &nums, int distace) {
	int ans = 0;
	for (int l = 0, r = 0; l < nums.size(); l++) {
		while (r + 1 < nums.size() && nums[r + 1] - nums[l] <= distace) {
			r++;
		}
		ans += r - l;
	}
	return ans;
}

题目5

同时运行N台电脑的最长时间
测试链接 : https://leetcode.cn/problems/maximum-running-time-of-n-computers/

你有 n 台电脑。给你整数 n 和一个下标从 0 开始的整数数组 batteries
其中第 i 个电池可以让一台电脑 运行 batteries[i] 分钟
你想使用这些电池让 全部 n 台电脑 同时 运行。
一开始，你可以给每台电脑连接 至多一个电池
然后在任意整数时刻，你都可以将一台电脑与它的电池断开连接，
并连接另一个电池，你可以进行这个操作 任意次
新连接的电池可以是一个全新的电池，也可以是别的电脑用过的电池
断开连接和连接新的电池不会花费任何时间。注意，你不能给电池充电。
请你返回你可以让 n 台电脑同时运行的 最长 分钟数。
开始玩概念了：“碎片拼接”！很秒！难想！

难点在于考虑到碎片电池的使用策略，实际上也就是贪心算法的范畴了。

    bool check(vector<int> &batteries, long long limit, int n) {
        long long fullUse = 0, sum = 0;
        for (auto &battery : batteries) {
            if (battery >= limit) {
                fullUse++;
            } else {
                sum += battery;
            }
        }
        return sum >= (n - fullUse) * limit;
    }

题目6

计算等位时间

给定一个数组arr长度为n，表示n个服务员，每服务一个客人的时间
给定一个正数m，表示有m个人等位，如果你是刚来的人，每个客人都遵循有空位就上的原则
请问你需要等多久？
假设m远远大于n，比如n <= 10^3, m <= 10^9，该怎么做是最优解？

谷歌的面试，这个题连考了2个月

check函数检验当来到时刻n时，服务员们能给多少位人开始服务。

题目7

刀砍毒杀怪兽问题

怪兽的初始血量是一个整数hp，给出每一回合刀砍和毒杀的数值cuts和poisons
第i回合如果用刀砍，怪兽在这回合会直接损失cuts[i]的血，不再有后续效果
第i回合如果用毒杀，怪兽在这回合不会损失血量，但是之后每回合都损失poisons[i]的血量
并且你选择的所有毒杀效果，在之后的回合会叠加
两个数组cuts、poisons，长度都是n，代表你一共可以进行n回合
每一回合你只能选择刀砍或者毒杀中的一个动作
如果你在n个回合内没有直接杀死怪兽，意味着你已经无法有新的行动了
但是怪兽如果有中毒效果的话，那么怪兽依然会不停扣血，直到血量耗尽的那回合死掉
返回至少多少回合怪兽会死掉
数据范围 : 1<=n<=10^5；1<=hp<=10^9；1<=cuts[i]、poisons[i]<=10^9

真实大厂算法笔试题

check检验来到n回合时能否斩杀怪物，当然以贪心思维去设计检验机制。

单调栈、单调队列

单调栈、单调队列都是以维护结构单调性的方式，保存答案的可能性。

单调栈

单调栈最经典的用法是解决如下问题：
每个位置都求：
0）当前位置的左侧比当前位置的数字小，且距离最近的位置在哪
1）当前位置的右侧比当前位置的数字小，且距离最近的位置在哪
或者
每个位置都求：
0）当前位置的左侧比当前位置的数字大，且距离最近的位置在哪
1）当前位置的右侧比当前位置的数字大，且距离最近的位置在哪

用单调栈的方式可以做到：求解过程中，单调栈所有调整的总代价为O(n)，单次操作的均摊代价为O(1)

除了单调栈最经典的用法之外，在很多问题里单调栈还可以维持求解答案的可能性
1）单调栈里的所有对象按照规定好的单调性来组织
2）当某个对象进入单调栈时，
会从栈顶开始依次淘汰单调栈里对后续求解答案没有帮助的对象
3）每个对象从栈顶弹出的时结算当前对象参与的答案，随后这个对象不再参与后续求解答案的过程
4）其实是先有对题目的分析！进而发现单调性，然后利用单调栈的特征去实现

例题分析：

题目1

单调栈最经典用法的模版
测试链接 : https://www.nowcoder.com/practice/2a2c00e7a88a498693568cef63a4b7bb

题目2

每日温度
测试链接 : https://leetcode.cn/problems/daily-temperatures/

1
2
3

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer
其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后
如果气温在这之后都不会升高，请在该位置用 0 来代替。

经典到不能再经典的单调栈标准题目。

题目3

子数组的最小值之和
测试链接 : https://leetcode.cn/problems/sum-of-subarray-minimums/

1 2	给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。由于答案可能很大，因此返回答案模 10^9 + 7

注意这道题答案很大，要求取模

很好理解，维持大压小，来到破坏单调性的位置意味着收获答案，然后逐层收集即可。

题目4

柱状图中最大的矩形
测试链接 : https://leetcode.cn/problems/largest-rectangle-in-histogram

1 2	给定 n 个非负整数，用来表示柱状图中各个柱子的高度每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积

对于 i号柱子 他能往左右伸展的最大距离取决于他左右能碰到的第一个小于他的柱子，
这一点就是破题关键。

题目5

最大矩形
测试链接 : https://leetcode.cn/problems/maximal-rectangle/

1 2	给定一个仅包含 0 和 1 、大小为 rows * cols 的二维二进制矩阵找出只包含 1 的最大矩形，并返回其面积

利用 压缩矩阵 的技巧，转化为.lc.84. 柱状图中最大的矩形问题

题目6

最大宽度坡
测试链接 : https://leetcode.cn/problems/maximum-width-ramp/

1 2	给定一个整数数组 A，坡是元组 (i, j)，其中 i < j 且 A[i] <= A[j] 这样的坡的宽度为 j - i，找出 A 中的坡的最大宽度，如果不存在，返回 0

~~难点在于怎么想到用单调栈~~
本质上还是维护答案的候选者，淘汰不可能成为答案的候选。
在此基础上寻找尽可能长的坡

题目7

去除重复字母保证剩余字符串的字典序最小
测试链接 : https://leetcode.cn/problems/remove-duplicate-letters/

1
2
3

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次
需保证 返回结果的字典序最小
要求不能打乱其他字符的相对位置

额外维护一个词频表和一个入栈表。

根据词频表和入栈表已经题目要求决定当前栈顶字母是否能被弹出，能被弹出的字母应当是后续仍然可以遍历到的，且字典序大于当前待入栈字母字典序的。
如果一个字母已经入栈，那么就不能再入栈了。

题目8

大鱼吃小鱼问题
测试链接 : https://www.nowcoder.com/practice/77199defc4b74b24b8ebf6244e1793de

给定一个数组arr，每个值代表鱼的体重
每一轮，每条鱼都会吃掉右边离自己最近比自己体重小的鱼，每条鱼向右找只吃一条
但是吃鱼这件事是同时发生的，也就是同一轮在A吃掉B的同时，A也可能被别的鱼吃掉
如果有多条鱼在当前轮找到的是同一条小鱼，那么在这一轮，这条小鱼同时被这些大鱼吃
请问多少轮后，鱼的数量就固定了
比如 : 8 3 1 5 6 7 2 4
第一轮 : 8吃3；3吃1；5、6、7吃2；4没有被吃。数组剩下 8 5 6 7 4
第二轮 : 8吃5；5、6、7吃4。数组剩下 8 6 7
第三轮 : 8吃6。数组剩下 8 7
第四轮 : 8吃7。数组剩下 8
过程结束，返回4

依然是维护答案的可能性。
从右往左看，维护一个信息，当这个鱼被吃时，至少需要过了多少回合，后面吃掉他的鱼继承他的回合数。

题目9

统计全1子矩形的数量
测试链接 : https://leetcode.cn/problems/count-submatrices-with-all-ones/

1 2	给你一个 m * n 的矩阵 mat，其中只有0和1两种值请你返回有多少个子矩形的元素全部都是1

两个技巧：1. 矩阵压缩、2. 从上往下滚动计算==即我们来到i行时，只关注以i行为底边的矩形

然后问题就又转化为.lc.84. 柱状图中最大的矩形问题

单调队列

单调队列最经典的用法是解决如下问题：
滑动窗口在滑动时，r++代表右侧数字进窗口，l++代表左侧数字出窗口
这个过程中，想随时得到当前滑动窗口的最大值或者最小值
窗口滑动的过程中，单调队列所有调整的总代价为O(n)，单次操作的均摊代价为O(1)

除了单调队列最经典的用法之外，在很多问题里单调队列还可以维持求解答案的可能性
1）单调队列里的所有对象按照规定好的单调性来组织
2）当某个对象从队尾进入单调队列时，
会从队头或者队尾依次淘汰单调队列里，对后续求解答案没有帮助的对象
3）每个对象一旦从单调队列弹出，可以结算此时这个对象参与的答案，
随后这个对象不再参与后续求解答案的过程
4）其实是先有对题目的分析！进而发现单调性，然后利用单调队列的特征去实现

例题分析：

题目1

滑动窗口最大值（单调队列经典用法模版）
测试链接 : https://leetcode.cn/problems/sliding-window-maximum/

1
2
3

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧
你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。

题目2

绝对差不超过限制的最长连续子数组
测试链接 : https://leetcode.cn/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/

给你一个整数数组 nums ，和一个表示限制的整数 limit
请你返回最长连续子数组的长度
该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit
如果不存在满足条件的子数组，则返回 0

题目3

接取落水的最小花盆
测试链接 : https://www.luogu.com.cn/problem/P2698

老板需要你帮忙浇花。给出 N 滴水的坐标，y 表示水滴的高度，x 表示它下落到 x 轴的位置
每滴水以每秒1个单位长度的速度下落。你需要把花盆放在 x 轴上的某个位置
使得从被花盆接着的第 1 滴水开始，到被花盆接着的最后 1 滴水结束，之间的时间差至少为 D
我们认为，只要水滴落到 x 轴上，与花盆的边沿对齐，就认为被接住
给出 N 滴水的坐标和 D 的大小，请算出最小的花盆的宽度 W

先排个序。
感觉很像滑窗）

题目4

和至少为K的最短子数组
测试链接 : https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/

1
2
3

给定一个数组arr，其中的值有可能正、负、0
给定一个正数k
返回累加和>=k的所有子数组中，最短的子数组长度

注意：本题用到构建前缀和的技巧

要点在于构建了前缀和之后可以很方便的查询区间和。

题目5

满足不等式的最大值
测试链接 : https://leetcode.cn/problems/max-value-of-equation/

给你一个数组 points 和一个整数 k
数组中每个元素都表示二维平面上的点的坐标，并按照横坐标 x 的值从小到大排序
也就是说 points[i] = [xi, yi]
并且在 1 <= i < j <= points.length 的前提下，xi < xj 总成立
请你找出 yi + yj + |xi - xj| 的 最大值，
其中 |xi - xj| <= k 且 1 <= i < j <= points.length
题目测试数据保证至少存在一对能够满足 |xi - xj| <= k 的点。

要点在于分析题目，将限制条件拆成(Yl - Xl) + (Yr + Xr)==即左端点的YX差加上右端点的YX和。

题目6

你可以安排的最多任务数目
测试链接 : https://leetcode.cn/problems/maximum-number-of-tasks-you-can-assign/

给你 n 个任务和 m 个工人。每个任务需要一定的力量值才能完成
需要的力量值保存在下标从 0 开始的整数数组 tasks 中，
第i个任务需要 tasks[i] 的力量才能完成
每个工人的力量值保存在下标从 0 开始的整数数组workers中，
第j个工人的力量值为 workers[j]
每个工人只能完成一个任务，且力量值需要大于等于该任务的力量要求值，即workers[j]>=tasks[i]
除此以外，你还有 pills 个神奇药丸，可以给 一个工人的力量值 增加 strength
你可以决定给哪些工人使用药丸，但每个工人 最多 只能使用 一片 药丸
给你下标从 0 开始的整数数组tasks 和 workers 以及两个整数 pills 和 strength
请你返回 最多 有多少个任务可以被完成。

注意：本题大思路用到二分答案法

大思路是二分答案，而check函数的实现则同时利用了贪心思路和单调队列（好像只用到了队列性质。。。）。

bool check(int tl, int tr, int wl, int wr, int s, int pills) {
	h = t = 0;  // 重置双端队列
	int cnt = 0; // 已经使用药丸的数量
	// i: 工人下标，j: 任务下标
	for (int i = wl, j = tl; i <= wr; i++) {
		// 不吃药情况下，工人 workers[i] 能够完成的任务
		for (; j <= tr && tasks[j] <= workers[i]; j++) {
			dequeArr[t++] = j;
		}
		if (h < t && tasks[dequeArr[h]] <= workers[i]) {
			// 当前工人无需吃药即可完成任务，分配队列头部任务
			h++;
		} else {
			// 允许使用药丸，尝试扩展任务区间
			for (; j <= tr && tasks[j] <= workers[i] + s; j++) {
				dequeArr[t++] = j;
			}
			if (h < t) {
				// 分配该任务，但需要使用药丸
				cnt++;
				t--;  // 这里选择队尾任务（难度更高的任务）
			} else {
				return false;
			}
		}
	}
	return cnt <= pills;
}

并查集

并查集的使用是如下的场景
1）一开始每个元素都拥有自己的集合，在自己的集合里只有这个元素自己
2）find(i)：查找i所在集合的代表元素，代表元素来代表i所在的集合
3）boolean isSameSet(a, b)：判断a和b在不在一个集合里
4）void union(a, b)：a所在集合所有元素与 b所在集合所有元素合并成一个集合
5）各种操作单次调用的均摊时间复杂度为O(1)
并查集的小扩展
可以定制信息：并查集目前有多少个集合，以及给每个集合打上标签信息

神奇优化：为什么并查集是O(1)的操作？

并查集的两个优化，都发生在find方法里
1）扁平化（路径压缩）（一定要做）
2）小挂大（可以不做，原论文中是秩的概念，可以理解为粗略高度或者大小）

并查集时间复杂度的理解
作为如此简单、小巧的结构，
感性理解单次调用的均摊时间复杂度为O(1)即可，其实为α(n)，反阿克曼函数。
当n=10^80次方即可探明宇宙原子量，α(n)的返回值也不超过6，那就可以认为是O(1)
并查集的发明者Bernard A. Galler和Michael J. Fischer，
从1964年证明到1989年才证明完毕。

例题分析：

题目1

并查集模版(牛客)
测试链接 : https://www.nowcoder.com/practice/e7ed657974934a30b2010046536a5372

路径压缩 + 小挂大

题目2

并查集模版(洛谷)
测试链接 : https://www.luogu.com.cn/problem/P3367

用递归函数实现路径压缩
一般情况下小挂大的优化可以省略的写法

题目3

情侣牵手
测试链接 : https://leetcode.cn/problems/couples-holding-hands/

n对情侣坐在连续排列的 2n 个座位上，想要牵到对方的手
人和座位由一个整数数组 row，表示其中 row[i] 是坐在第 i 个座位上的人的ID
情侣们按顺序编号，第0对是 (0, 1)，第1对是 (2, 3)，以此类推
返回 最少交换座位的次数，以便每对情侣可以并肩坐在一起
每次交换可选择任意两人，让他们站起来交换座位

将所有情侣对（先不管配不配对）视为单元素集合。
然后合并所有未配对集合。

题目4

相似字符串组
测试链接 : https://leetcode.cn/problems/similar-string-groups/

如果交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等
那么称 X 和 Y 两个字符串相似
如果这两个字符串本身是相等的，那它们也是相似的
例如，"tars" 和 "rats" 是相似的 (交换 0 与 2 的位置)；
"rats" 和 "arts" 也是相似的，但是 "star" 不与 "tars"，"rats"，或 "arts" 相似
总之，它们通过相似性形成了两个关联组：{"tars", "rats", "arts"} 和 {"star"}
注意，"tars" 和 "arts" 是在同一组中，即使它们并不相似
形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。
给你一个字符串列表 strs列表中的每个字符串都是 strs 中其它所有字符串的一个字母异位词。
返回 strs 中有多少字符串组

开始时每个字符串都是单元素集合，然后根据相似关系例如：
{str1->str2->str3}，
以此构建关联集合。

题目5

岛屿数量
测试链接 : https://leetcode.cn/problems/number-of-islands/

1
2
3

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成
此外，你可以假设该网格的四条边均被水包围

注意：本题还可以用洪水填充算法求解

没啥好说的，将所有相邻的1合并为一个集合就行，最后统计剩下的集合数就好。

题目6

移除最多的同行或同列石头
测试链接 : https://leetcode.cn/problems/most-stones-removed-with-same-row-or-column/

n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头
如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头
给你一个长度为 n 的数组 stones ，
其中 stones[i] = [xi, yi] 表示第 i 块石头的位置
返回 可以移除的石子 的最大数量。

我们需要统计来到 (i , j) 位置时，当前位置是否已经有了石头？有则合并。
所以额外维护一个行列石头最早出现表就行

题目7

找出知晓秘密的所有专家
链接测试 : https://leetcode.cn/problems/find-all-people-with-secret/

给你一个整数 n ，表示有 n 个专家从 0 到 n - 1 编号
另外给你一个下标从 0 开始的二维整数数组 meetings
其中 meetings[i] = [xi, yi, timei]，表示专家 xi 和专家 yi 在时间 timei 要开一场会
一个专家可以同时参加 多场会议 。最后，给你一个整数 firstPerson
专家 0 有一个 秘密 ，最初，他在时间 0 将这个秘密分享给了专家 firstPerson
接着，这个秘密会在每次有知晓这个秘密的专家参加会议时进行传播
更正式的表达是，每次会议，如果专家 xi 在时间 timei 时知晓这个秘密
那么他将会与专家 yi 分享这个秘密，反之亦然。秘密共享是 瞬时发生 的
也就是说，在同一时间，一个专家不光可以接收到秘密，还能在其他会议上与其他专家分享
在所有会议都结束之后，返回所有知晓这个秘密的专家列表，你可以按 任何顺序 返回答案

先给会议序列按照来到时刻排序，然后合并同时刻的集合，标记被传染的集合，未被传染的集合拆分回原样。

题目8

好路径的数目
测试链接 : https://leetcode.cn/problems/number-of-good-paths/

给你一棵 n 个节点的树（连通无向无环的图）
节点编号从0到n-1，且恰好有n-1条边
给你一个长度为 n 下标从 0 开始的整数数组 vals
分别表示每个节点的值。同时给你一个二维整数数组 edges
其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边
好路径需要满足以下条件：开始和结束节点的值相同、 路径中所有值都小于等于开始的值
请你返回不同好路径的数目
注意，一条路径和它反向的路径算作 同一 路径
比方说， 0 -> 1 与 1 -> 0 视为同一条路径。单个节点也视为一条合法路径

关键在于边处理顺序：
将待处理边按照关联点权值的max按从小大大排序，
然后合并同权集合时结算答案，不同权集合则不结算。
这样的顺序可以保证我们再处理到类似 {max: 1} ~ {max: 2} ~ {max: 1}时，不会重复计算。

题目9

尽量减少恶意软件的传播 II
测试链接 : https://leetcode.cn/problems/minimize-malware-spread-ii/

给定一个由 n 个节点组成的网络，一定是无向图，用 n * n 个邻接矩阵 graph 表示
在节点网络中，只有当 graph[i][j] = 1 时，节点 i 能够直接连接到另一个节点 j。
一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，
且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。
这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。
假设 M(initial) 是在恶意软件停止传播之后，
整个网络中感染恶意软件的最终节点数。
我们可以从 initial 中删除一个节点，
并完全移除该节点以及从该节点到任何其他节点的任何连接。
请返回移除后能够使 M(initial) 最小化的节点。
如果有多个节点满足条件，返回索引 最小的节点 。initial 中每个整数都不同

先合并所有正常点。
然后根据正常集合链接的传染源判断答案。

洪水填充

洪水填充是一种很简单的技巧，设置路径信息进行剪枝和统计，类似感染的过程
路径信息不撤销，来保证每一片的感染过程可以得到区分
看似是暴力递归过程，其实时间复杂度非常好，遍历次数和样本数量的规模一致

例题分析：

题目1

岛屿数量
测试链接 : https://leetcode.cn/problems/number-of-islands/

1
2
3

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成
此外，你可以假设该网格的四条边均被水包围

没啥好说的，标准靶场）
就是遇到 ‘1’ 就洪水填充为 ‘0’，然后计数。

题目2

被围绕的区域
测试链接 : https://leetcode.cn/problems/surrounded-regions/

1 2	给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域并将这些区域里所有的 'O' 用 'X' 填充。

~~我tm的把O看成0了。~~
一样的，先把边界处的O洪水填充标注为F
然后遍历将 O 改 X， F 改 O 就行。

题目3

最大人工岛
测试链接 : https://leetcode.cn/problems/making-a-large-island/

1
2
3

给你一个大小为 n * n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。
返回执行此操作后，grid 中最大的岛屿面积是多少？
岛屿 由一组上、下、左、右四个方向相连的 1 形成

只是比前面的题目多了要求，你需要额外计算洪水填充填了多少格子，可以放在洪水填充中计算，也可以后面遍历一遍统计。

题目4

打砖块
测试链接 : https://leetcode.cn/problems/bricks-falling-when-hit/

有一个 m * n 的二元网格 grid ，其中 1 表示砖块，0 表示空白
砖块 稳定（不会掉落）的前提是：
一块砖直接连接到网格的顶部，或者
至少有一块相邻（4 个方向之一）砖块 稳定 不会掉落时
给你一个数组 hits ，这是需要依次消除砖块的位置
每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消失
然后其他的砖块可能因为这一消除操作而 掉落
一旦砖块掉落，它会 立即 从网格 grid 中消失（即，它不会落在其他稳定的砖块上）
返回一个数组 result ，其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。
注意，消除可能指向是没有砖块的空白位置，如果发生这种情况，则没有砖块掉落。

这道题的精髓在于 时间回溯。
从后往前逆向分析，然后配合洪水填充标记砖块。