左神初级算法课程第七讲笔记-并查集、前缀树、贪心

并查集：初始化地时候必须要给所有样本

①非常快地查两个元素是否为一个集合②合并两个元素所在的集合为一个大集合

两个要求

list和set结构都不适合，提出并查集结构：多叉树，1指向自己，作为代表节点，这样方便查isSameSet

并查集

如果合并集合则把小的集合链到大的集合上：

集合合并

优化：在某次查找后，把所查元素到代表节点这条链上的所有节点直接连到代表节点上，所查节点后面的节点不动，依然挂在原来位置

时间复杂度：只要查询次数+合并次数逼近O(N)及以上，则单次查询或合并的平均复杂度为O(1)

岛问题：

岛问题

单cpu解法：

遍历的思路

并行计算方法：主要是处理边界处的岛数量重复问题

并行计算方法

前缀树：处理字符串，字符填在路径上而不是节点上，字符路径存在复用，否则就从新生成

前缀树

作用：查找添加的所有字符串中是否有特定字符串开头的目标字符串（例如“be”，但是单单查找是否有“be”是查不出来的），因此要在每个节点上添加信息表示有多少个字符串是以这个节点结尾的，同时每个节点再加一个数据项记录这个节点到达了几次，这样可以统计有多少个字符串以头节点到这个节点的字符串为前缀

贪心策略：不要纠结贪心策略的证明，可以通过对数器验证，过了对数器就能用

字典序：翻字典的时候保有的序列，字符串比较时，长度相同直接比，长度不等按较小字符串的位数比，可以把字符串理解为k进制的数，长度不等时较小字符串后面补0

例题：给一个字符串组成的数组，拼成一个字符串并使字典序最小，注意不能用直接排序的方式。思路就是设计一个比较器，按照这个思路对整个数组排序，然后连接所有字符串即可。设计比较器的时候要考虑传递性，不能陷入循环

贪心策略 证明贪心策略 证明过程

其中m(a)=k的a长度次方