[C++]换个方式理解移动构造和拷贝构造 相信大部分初学者（当然包括我）都会对移动构造和拷贝构造有不理解的地方，或者理解有一定的误区，虽然很多人都在讲这个东西，但是自己本来就没懂，所以听着也是稀里糊涂没听明白，但是没关系，我会用最通俗易懂的例子让你理解它。首先看看这个例子：class Widget { public: Widget(); Widget(Widget &); Widget(Widget &&); private: Datatype *data; }这就是一个基本的拥有三种构造函数的类，当我们用不同的方式初始化一个该类的对象的时候，他就会根据对应的参数调用对应的构造函数，注意我说的对应！这是理解它们区别的很重要的点。接下来步入正题，让我们转换视角。把你自己抽象成data现在你就是这个Widget里的data，Widget就是承载你的物体的类，具体可能是大地或者是床，甚至是火星，或者......总之你就处在Widget上对人来说，当我们从地上上了床，这个过程对应了哪个构造函数呢？当然是一都构造了，对应代码就是：Widget floor; // floor 里的data就是现在的你，代表你现在在地上 // 现在你想上床躺会 Widget bed(std::move(floor)); // 现在把你移动到床上你从地面上移动到床上的过程就被抽象成了这样，还可以理解对吧。哦，我好像忘了定义 Widget(Widget &&) ，现在来定义它。Widget(Widget &&other) { data = other.data; // 将other.data复制给data就是你从地上到了床上 other.data = nullptr; // 将other.data置空的原因是你现在已经不在地上了 }结合注释，还是很好理解对吧。那么继续。如果是拷贝构造？现在你还是data，试想一下如果在这个过程是拷贝的呢？床上一个你，地下一个你，为了让床上有一个你，我们需要先造一个你的克隆体，因为不会凭空再出现一个你对吧，那么这个制造克隆体的开销就是拷贝构造相对移动构造的开销，当然这只是一部分。想想你为什么想上床呢？因为你不想再待在地上了对吧，所以你根本不需要大费周章克隆一个你，你自己上去不就行了吗？那什么时候需要拷贝构造呢？我们事一多的时候，不都经常想再多几个我就好了，因为这些事情都需要你，所以多几个你明显效率更高。左值右值只是为了区分那么再想我们一些情况下是要克隆一个自己，还是自己直接过去就好了，我们要对这两种情况做个区分，我们可以打标签对吧，对C++来说这个标签就是看它是左值还是右值，右值代表需要移动，左值代表需要克隆，就这样。再看我开头说的对应，可以理解了吗？就是编译器根据这个标签选择是调用拷贝构造还是移动构造。std::move();做的就是给Widget对象打上标签，代表需要移动。我不需要待在原地，那么我就移动，我就是右值，我需要一个克隆体，那么我就是左值。希望对你有帮助，如果有错误，欢迎纠正。

[Git]GitHub 无法读取远程仓库 有的时候我们不能正常使用github，不能做pull或者push或者其他什么操作，很有可能是DNS污染，一般他会提示你：{alert type="error"}ssh: connect to host github.com port 22: Connection refusedfatal: 无法读取远程仓库。请确认您有正确的访问权限并且仓库存在。{/alert}这个时候改一下hosts配置就行sudo vi /etc/hosts在文件中添加这两段：151.101.76.133 raw.githubusercontent.com 20.205.243.160 ssh.github.com再检查一下就好

[算法]并查集以及优化 这是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] << ' ';