[算法]并查集以及优化 这是Wikipedia中对并查集的介绍：在计算机科学中，并查集（英文：Disjoint-set data structure，直译为不交集数据结构）是一种数据结构，用于处理一些不交集（Disjoint sets，一系列没有重复元素的集合）的合并及查询问题。并查集支持如下操作：查询：查询某个元素属于哪个集合，通常是返回集合内的一个“代表元素”。这个操作是为了判断两个元素是否在同一个集合之中。合并：将两个集合合并为一个。添加：添加一个新集合，其中有一个新元素。添加操作不如查询和合并操作重要，常常被忽略。由于支持查询和合并这两种操作，并查集在英文中也被称为联合-查找数据结构（Union-find data structure）或者合并-查找集合（Merge-find set）。“并查集”可以用来指代任何支持上述操作的数据结构，但是一般来说，“并查集”特指其中最常见的一种实现：不交集森林（Disjoint-set forest）。经过优化的不交集森林有线性的空间复杂度（O(n)，n为元素数目，下同），以及接近常数的单次操作平均时间复杂度(O(log*(n)),log*(n)为反阿克曼函数）)是效率最高的常见数据结构之一。并查集是用于计算最小生成树的克鲁斯克尔演算法中的关键。由于最小生成树在网络路由等场景下十分重要，并查集也得到了广泛的引用。此外，并查集在符号计算，寄存器分配等方面也有应用。{dotted startColor="#ff6c6c" endColor="#1989fa"/}基本并查集首先从最简单的开始，我们先完成并查集查询，合并和添加的操作。表示一般我们使用树的形式表达一个并查集集合。大概就像这样这里有两个集合，以0为根节点的，以5为根节点的。添加添加操作MakeSet(x)添加一个元素x，这个元素单独属于一个仅有它自己的集合。在不交集森林中，添加操作仅需将元素标记为根节点。首先，为了简单理解我这里使用一个数组表示出并查集的节点。int djs[100];我们要保留它的数据，还要保留它的根节点，所以在这里，我们简单定义成这样。MakeSet函数里对节点初始化，让root指向自己。void MakeSet(int x) { djs[x] = x; }查询在不交集森林中，每个集合的代表即是集合的根节点。查询操作Find(x)从x开始，根据节点到父节点的引用向根行进，直到找到根节点。这段代码也很简单：int Find(int x) { if(djs[x] == x) return x; return Find(djs[x]); }合并合并操作Union(x, y)把元素x所在的集合与元素y所在的集合合并为一个。合并操作首先找出节点x与节点y对应的两个根节点，如果两个根节点其实是同一个，则说明元素x与元素y已经位于同一个集合中，否则，则使其中一个根节点成为另一个的父节点。用图来说就是在将图1对以0为根节点与以3为根节点的集合合并后就会变成图2代码这样写：void Union(int x, int y) { djs[Find(y)] = djs[Find(x)]; }好了现在你已经学会并查集了，做一下这道题吧Islands优化上边这些代码好吗？他不好，因为在最坏情况下会Union成一条链，这时候Find操作是O(n)的{0,0,1,2,3,4,...}对这种情况我们肯定是要优化他的，优化肯定是从Union入手了，常见的优化方法有两种，一种是根据权重，另一种是根据树的深度，这时候情况就有点复杂了，无论是权重还是深度，显然都不是一个数组就能解决的了的，所以我们可以再引入一个数组来保存。下边以权重为例1int djs[100]; int power[100]; void MakeSet(int x) { djs[x] = x; power[x] = 1; } int Find(int x) { if(djs[x] == x) return x; return Find(djs[x]); } void Union(int x, int y) { int a = Find(y); int b = Find(x); if(power[a] < power[b]) std::swap(a,b); djs[a] = djs[b]; power[a] += power[b]; }这样就可以通过权重选择合并的树了，这时候查找达到了O(log(n))的。难道这就是极限？还记得刚开始提到的反阿克曼函数吗？它的优化可以达到什么地步呢？2^65535 的数据均摊也只需要五步就可以找到他的根节点！这就是通过路径压缩算法实现的。路径压缩对于这样的一颗树，我现在执行了查找7的根节点的操作我们在Find(7)的时候都经过了哪些节点？（7,6,5,0），如下：这时候我让这条路径所有节点的根节点都之间变成根节点0，就成了这样这时候，下次再查这条路径上的节点的根节点的时候，都只需一步就可查出结果。代码实现我选择新建vector来保存，只要修改一下Find就好了。std::vector<int> temp; int Find(int x) { temp.push_back(x); if(djs[x] == x) return x; int root = Find(djs[x]); for(int v : temp) { djs[v] = root; } temp.clear(); return root; }无论是根据权重还是根据深度，最后优化下来的结果都是O(log(n))的，权重写起来也更简单 ↩

[算法题解]leetcode 318. 最大单词长度乘积 题目首先读题，题目要求两个字符串不能含有公共字母，这句话还隐含了一个意思就是我们在比较两个字符串时，可以先看两个字符串出现的字母有没有相同的，那么我们可以将字符串处理成每个字母只出现一次，再进行比较，但是进一步想，一共只有26个字母，一个int类型的数据可以储存32位的01，我们是不是可以只用一个int数据就可以表示一个字符串所包含的字符呢？我们用1表示该位置的字母出现，例如：“a”，我们可以表示为000...01，“ab”就是000...0011，明白了吗？所以我们可以这样处理当前字符n |= (1 << v - 'a')n就是该字符串处理后对应的数字，v就是s中的一个字符。处理好s之后我们还要记录下n对应的最大长度，直接用max函数即可。这里我用哈希表来实现：unordered_map<int,int> hash; for(string &s : words) { int n = 0; for(char v : s){ n |= (1 << (v - 'a')); } hash[n] = max(hash[n],(int)s.size()); }先迭代words再迭代s储存我们想要的结果，之后我们就需要实现计算最大长度积了。怎么判断两个n是否在相同的位都有1？做算数与运算即可，只有他们没有公共位含有1时结果才为0.if(hash.size()<2) return 0; int ans{}; for(auto it = hash.begin();it != hash.end();it++) { auto at = it; at++; for(;at != hash.end();at++) { if(!(it->first & at->first)) ans = max(ans,int(it->second*at->second)); } }以上就是所有内容。

[算法]堆排序 堆排序我是跟着这个视频学习然后自己实现了一下算法，视频已经讲的很清楚了，我就不多说了{bilibili bvid="BV1AF411G7cA" page=""/}{dotted startColor="#ff6c6c" endColor="#1989fa"/}建堆堆排序顾名思义，要在堆上排序，堆是一种完全二叉树，分大根堆小根堆，我们现在只讲一种，就是小根堆建堆，小根堆用自顶而下建堆法，在建堆之前我们写好上滤、下滤操作。我的实现是用数组，根节点从下标1开始，这样可以保证一个节点int(index/2)就能得到它的父节点下滤就是跟子节点比较，然后交换或者退出操作。index就是需要执行操作的下标，size就是当前堆节点数void UpToDown(int a[], unsigned int index, size_t size) // 下滤 { int maxindex; // maxindex用来储存a[index]的最大子节点 do // 既然选择执行下滤那么index一定不在最底层，所以至少执行一次下滤 { maxindex = 2 * index; if (maxindex + 1 < size && a[maxindex + 1] > a[maxindex]) // 首先得保证读数据不会内存溢出吧 maxindex++; if (a[index] < a[maxindex]) swap(a[index], a[maxindex]); else break; index = maxindex; } while (index < size / 2); }与下滤对应的是上滤，就是跟父节点比较。void DownToUp(int a[], unsigned int index) // 上滤 { int faindex = index / 2; do { if (a[index] > a[faindex]) swap(a[index], a[faindex]); else break; index /= 2; faindex = index / 2; } while (faindex > 0); }代码都很简单，就不详细说了。实现了上滤、下滤，剩下的就是建堆了，至于建大根堆还是小根堆看你自己意愿。void BuildHeap(int a[], size_t size) // 自顶而下建堆法 { if (size < 3) return; for (int i = 2; i < size; i++) { DownToUp(a, i); } }都写一下吧void BuildHeap(int a[], size_t size) // 自下而上建堆法 { for (int i = size / 2; i > 0; i--) { UpToDown(a, i, size); } }这就是堆排序前的所有操作，剩下的就是排序了，代码也很简单：堆排序void HeapSort(int a[], size_t size) { for (int i = size - 1; i > 0; i--) { swap(a[i], a[1]); UpToDown(a, 1, i); } swap(a[1], a[2]); }注意堆排序的前提是对堆排序，需要先BuildHeap的，直接排序你只能看到一堆乱七八糟的结果，然后怀疑自己写的哪有问题（别问我怎么知道的）。现在在你的main函数中写下你需要排序的数据，再试试你的代码就好了。 int a[9] = {0, 3, 5, 4, 1, 2, 0, 85, 7}; BuildHeap(a, 9); for (int i = 1; i < 9; i++) cout << a[i] << ' '; cout << endl; HeapSort(a, 9); for (int i = 1; i < 9; i++) cout << a[i] << ' ';