公司网站一般用什么软件做微信公众号是什么平台

当前位置： 首页 > news >正文

公司网站一般用什么软件做,微信公众号是什么平台,seo技术培训沈阳,移动端是不是手机端数据结构#xff1a;并查集 并查集原理实现框架初始化合并查询获取成员路径压缩其它 总代码 并查集 在生活中#xff0c;经常会出现分组问题。比如一个班级分为多个小组#xff0c;打篮球分为两方等等。在同一个组中的所有成员#xff0c;就构成一个集合。对这种一个群体分… 数据结构并查集 并查集原理实现框架初始化合并查询获取成员路径压缩其它 总代码 并查集 在生活中经常会出现分组问题。比如一个班级分为多个小组打篮球分为两方等等。在同一个组中的所有成员就构成一个集合。对这种一个群体分为多个集合的数据结构称为并查集。 其提供两个最核心的功能 合并将两个集合合并成一个集合查询查找两个元素是否属于一个集合 因此称为并查集。 实现一个并查集并不难但是如果要实现一个高效的并查集就需要一定的设计了。本博客讲解以C实现的并查集并且尽可能在时间与空间的利用上更加高效。 原理 谈到集合在数据结构中如何维护一个集合比如一个数组一个set一棵树等等。既然要探求一个最高效的存储方式那么就要讨论如何最大化利用资源了。 如果使用一个数组来存储一个集合那么每个集合都要开辟一个数组在合并集合时还需要发生数组的合并此时又会有空间的开辟和销毁。 如果使用链式树存储集合此时合并就会很方便 红色与蓝色是两个不同的集合合并集合时只需要修改一个指针的指向即可。 但是链式结构也有问题链式结构的数据是分散的计算机每次加载节点都需要寻址效率很低。有没有方法既可以保持树结构又可以集中的存储所有数据 如果你学习过堆那么答案就呼之欲出了其实就是使用一个数组形式的树。 如图每个节点存储自己的父节点的下标根节点存储自己的下标。 其可以转化为如下三个集合 这是一种常见的并查集形式但是还可以再优化。这种形式下根节点存储自己的下标是不是可以把这块空间腾出来存储该集合的元素个数 如图根节点存储的值变为负数绝对值表示该集合的总元素个数。为什么根节点要变为负数之前已经规定了数组的元素存储自己父节点的下标如果根节点的值为一个正整数此时如何判断这是一个根节点还是普通节点存储的值是集合总元素还是父节点下标 因为数组下标没有负数所以此时就可以通过正负数判断该节点是根节点还是普通节点 负数根节点存储该集合元素总个数正数普通节点存储父节点的下标 这是一个非常高效的存储结构使用一个数组就表示了一个并查集内含多个树结构。而多棵树在一起就构成了一个森林其实并查集的本质就是一个森林。 但是至此还有一个问题这个并查集只能表示整数集合不能表示其它的string等类型所以还需要一个map维持映射关系将其他元素映射为数组下标。 实现 框架 为了提高可扩展性把并查集定义为一个类模板模板参数为并查集存储元素的类型。 template typename T class UnionFindSet { private:vectorint _ufs;mapT, int _mp; };成员变量 _ufs并查集的本体用于维护集合的关系也就是刚刚设计的那个数组_mp一个映射关系将存储的元素T映射到具体的数组下标int 初始化 初始化时并查集接收一个数组里面是独立的元素它们不构成任何集合关系。 随后要构建这些元素与下标的映射关系即初始化_mp。另 最后对于_ufs本体全部初始化为-1。 因为一开始所有元素自成一个集合都是集合的根节点而根节点存储的是集合元素的个数的负数。每个集合只有一个元素所以节点值初始化为-1。 构造函数 UnionFindSet(vectorT source): _ufs(source.size(), -1) {for (int i 0; i source.size(); i)_mp[source[i]] i; }参数接受一个数组source内部包含多个T类型元素在初始化列表种将_ufs的大小扩大到与source一致所有元素初始化为-1。 在函数体内部完成对_mp的初始化遍历source存储(source[i], i)的映射关系。 合并 合并两个集合就是将其中一个元素的根节点的父节点指针指向另一个节点的根节点如图 上图展示了蓝色集合与绿色集合的合并操作分为以下两步 将蓝色集合根节点的值加上绿色集合根节点的值-4变-7将绿色集合的根节点的值变为蓝色集合根节点的下标-3变0 既然要操作集合的根节点自然就要先找到集合的根节点写一个函数用于获取集合根节点 int findRoot(T x) {if (_mp.count(x) 0)throw runtime_error(value does not exist); // 值不存在int root _mp[x];while (_ufs[root] 0){root _ufs[root];}return root; }首先通过_mp.count(x)判断该元素是否在并查集种如果不在就抛出一个异常表示值不存在。 随后通过一个循环每次root _ufs[root]其中_ufs[root]是父节点的下标这样就可以让root往父节点走直到走到根节点此时_ufs[root]是一个负数最后跳出循环返回根节点。 找到根节点后就可以完成集合的合并操作了 void unionSet(T x1, T x2) {int root1 findRoot(x1);int root2 findRoot(x2);if (root1 root2)return;_ufs[root1] _ufs[root2];_ufs[root2] root1; }首先通过findRoot找到两个集合的根节点如果根节点相同说明两个元素本来就处于一个集合种直接返回。 随后_ufs[root1] _ufs[root2];完成了元素的加和此时root1是新根_ufs[root1]存储的是两个集合的元素总和的负数。 最后_ufs[root2] root1;修改toor2父节点完成集合的合并。 这里还有一个优化两个集合有两种合并方式 如图可以将绿色集合合并到蓝色集合下也可以将蓝色集合合并到绿色集合下。这两种方式都是合理的但是哪一种更好 在集合种查找元素时最多搜索树的高度次树高度越低那么搜索效率就越高。所以常把集合元素多的作为根。上图中因为蓝色集合元素个数多所以把绿色集合合并到蓝色集合更优也就是左边的方式。这个优化称为按秩合并。 代码优化 void unionSet(T x1, T x2) {int root1 findRoot(x1);int root2 findRoot(x2);if (root1 root2)return;// 按秩合并if (_ufs[root1] _ufs[root2]){_ufs[root1] _ufs[root2];_ufs[root2] root1;}else{_ufs[root2] _ufs[root1];_ufs[root1] root2;} }由于根节点存储的就是集合的元素个数所以可以直接拿_ufs[root]来比较两个集合的大小。如果_ufs[root1] _ufs[root2]因为根节点存储的是负数所以_ufs[root1]的绝对值更大要把root2合并到root1。 查询 并查集的第二个核心操作是判断两个元素是否在同一个集合。这其实非常简单只需要判断两个元素的根节点是否相同即可 bool inSet(T x1, T x2) {return findRoot(x1) findRoot(x2); }获取成员 该接口的作用是输入一个元素取同一集合中的其它所有元素。 刚刚讲解过判度两个元素是否在同一个集合只需要看根节点是否相同。所以此处只需要 先获取输入的根节点root遍历整个并查集判度根节点是否与root相同 vectorT getMembers(T x) {vectorT members;int root findRoot(x);for (const auto pair : _mp){if (findRoot(pair.first) root) members.push_back(pair.first);}return members; }以上代码返回一个vectorT里面是与x为同一集合的所有元素。 首先root findRoot(x)获取x的根节点。随后通过for循环遍历_mpfindRoot(pair.first)获取元素根节点再与root判等如果相等说明在同一集合此时尾插到members数组中。 路径压缩 当并查集使用久了就会出现树高度太高的问题但是并查集内部的树是多叉树如下图两个集合 这两个集合其实是同一个集合但是很明显左边的树高度低查询效率会高很多。所以并查集中常会做一个优化将树高度尽可能降低这个优化称为路径压缩。 压缩路径被实现在查找操作findRoot中因为每次查找的时候都会从树底网上遍历到根节点这是完成路径压缩的最好时机。 路径压缩的算法核心是 每次向上查找父节点时把自己提高到与父节点的同一层 如图 当前从节点4开始向上查找首先找到父节点1随后将4提升到与1的同一层。也就是中间的情况。 此时问题变成了从1开始查找根节点。找到父节点7随后将1提升到与7的同一层此时就变成了最后一种情况。 最后找到根节点为0由于0已经是根节点了不能把7提升到根节点。 实现 int findRoot(T x) {if (_mp.count(x) 0)throw runtime_error(value does not exist); // 值不存在int root _mp[x];while (_ufs[root] 0 _ufs[_ufs[root]] 0){_ufs[root] _ufs[_ufs[root]]; // 路径压缩}if (_ufs[root] 0)root _ufs[root];return root; }由于路径压缩要考虑爷爷节点是否存在所以while内部有两个条件_ufs[root] 0表示父节点存在_ufs[_ufs[root]] 0表示爷爷节点存在。 只要父节点和爷爷节点都存在那么就可以进行路径压缩_ufs[root] _ufs[_ufs[root]]其中_ufs[root] 是当前节点的值存储的是父节点的下标_ufs[_ufs[root]]是爷爷节点的下标。这个赋值将爷爷节点的下标赋值给自己此时就把爷爷节点变成了父节点完成了向上提升。 最后while循环离开的时候有可能是因为爷爷节点不存在此时root是根节点的某一个孩子所以还要root _ufs[root]往上走一层。 其它 还有一些其它的小接口都很简单 当前并查集内部有多少个集合 size_t count() {size_t size 0;for (auto num : _ufs){if (num 0)size;}return size; }输入一个集合获取该集合的元素个数 size_t size(T x) {return abs(_ufs[findRoot(x)]); }想要知道集合元素个数只需要找到根节点然后返回绝对值即可。 总代码 UnionFindSet.hpp #pragma once #include iostream #include vector #include map #include stdexceptusing namespace std;template typename T class UnionFindSet { public:UnionFindSet(vectorT source): _ufs(source.size(), -1){for (int i 0; i source.size(); i)_mp[source[i]] i;}int findRoot(T x){if (_mp.count(x) 0)throw runtime_error(value does not exist); // 值不存在int root _mp[x];while (_ufs[root] 0 _ufs[_ufs[root]] 0){_ufs[root] _ufs[_ufs[root]]; // 压缩路径root _ufs[root];}if (_ufs[root] 0)root _ufs[root];return root;}void unionSet(T x1, T x2){int root1 findRoot(x1);int root2 findRoot(x2);if (root1 root2)return;// 按秩合并if (_ufs[root1] _ufs[root2]){_ufs[root1] _ufs[root2];_ufs[root2] root1;}else{_ufs[root2] _ufs[root1];_ufs[root1] root2;}}bool inSet(T x1, T x2){return findRoot(x1) findRoot(x2);}size_t count(){size_t size 0;for (auto num : _ufs){if (num 0)size;}return size;}size_t size(T x){return abs(_ufs[findRoot(x)]);}vectorT getMembers(T x) {vectorT members;int root findRoot(x);for (const auto pair : _mp){if (findRoot(pair.first) root) members.push_back(pair.first);}return members;}private:vectorint _ufs;mapT, int _mp; };test.cpp测试代码 #include iostream #include string #include vector #include unionFindSet.hppusing namespace std;int main() {vectorstring stu { 张三, 李四, 王五, 赵六, 翠花, 小龙, 小淘, 小明 };UnionFindSetstring ufs(stu);cout ufs.count() endl;cout ufs.inSet(张三, 翠花) endl;ufs.unionSet(张三, 赵六);ufs.unionSet(王五, 小淘);ufs.unionSet(翠花, 小明);ufs.unionSet(翠花, 张三);cout ufs.inSet(张三, 翠花) endl;cout ufs.count() endl;cout ufs.size(张三) endl;auto members ufs.getMembers(张三);for (auto mem : members)cout mem ;cout endl;return 0; }