算法特别篇_强大的static_注重细节的百倍优化(LeetCode_839_相似字符串组)

算法特别篇_强大的static优化

概：思来想去，果然还是有必要记录一下这见证历史的时刻！学c++也有点时间了，关于代码基础细节反面，一直没有切身体会过有多大的影响。今天借这份每日一题记录一下细节上的百倍优化。
来源：力扣（LeetCode）
链接：LeetCode_839_相似字符串组

故事开始

首先题目

我打开力扣看到了今天的每日一题，又是困难，又是并查集，大体思路并不难，不会并查集的hxd去隔壁博客康康算法特别篇_并查集思路(LeetCode_778_水位上升的泳池中游泳) 。嗯，那我先把题扔上来。

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

• 例子
  示例 1：
  输入：strs = [“tars”,“rats”,“arts”,“star”]
  输出：2
  示例 2：
  输入：strs = [“omv”,“ovm”]
  输出：1

• 提示
  1 <= strs.length <= 100
  1 <= strs[i].length <= 1000
  sum(strs[i].length) <= 2 * 104
  strs[i] 只包含小写字母。
  strs 中的所有单词都具有相同的长度，且是彼此的字母异位词。

• 备注：
  字母异位词（anagram），一种把某个字符串的字母的位置（顺序）加以改换所形成的新词。

然后AC这道题目

下来我就动手了，很快啊！直接搓了一个并查集，给他ac了，但是效率感人（如下图），我刷力扣以来第一次这么惨淡，虽然ac了，但是伤害不高羞辱性极强。我能忍吗，我不能，我得优化它。

这边先贴一下最开始用的那份代码

class UnionFind
{
public:
vector parents;
int count = 0;
UnionFind(int n)
{
count = n;
for(int i = 0;i {
parents.push_back(i);
}
}
int Find(int x)
{
if(parents[x]==x) return x;
return Find(parents[x]);
}
void marge(int x,int y)
{
if(Find(x)!=Find(y))
{
parents[Find(x)] = Find(y);
count--;
}
}
};
class Solution {
public:
int numSimilarGroups(vector& strs) {
UnionFind uf(strs.size());
for(int i = 0;i for(int j = i+1;j if(strResemble(strs[i],strs[j])) uf.marge(i,j);
return uf.count;
}
bool strResemble(string& a,string& b)
{
vector ve;
for(int i = 0;i
if(a[i]!=b[i])
{
ve.push_back(i);
}
}
if(ve.size()==0) return true;
if(ve.size()!=2) return false;
if(a[ve[0]]==b[ve[1]]&&a[ve[1]]==b[ve[0]]) return true;
return false;
}
};


接着优化我的效率