ARTS打卡第二周
Algorithm：每周至少做一個 leetcode 的算法題
839. 相似字符串組
如果交換字符串 X 中的兩個不同位置的字母，使得它和字符串 Y 相等，那么稱 X 和 Y 兩個字符串相似荞胡。如果這兩個字符串本身是相等的种呐，那它們也是相似的太援。
例如掌桩，"tars" 和 "rats" 是相似的 (交換 0 與 2 的位置)沮明； "rats" 和 "arts" 也是相似的色乾，但是 "star" 不與 "tars"誊册，"rats"，或 "arts" 相似暖璧。
總之案怯，它們通過相似性形成了兩個關(guān)聯(lián)組：{"tars", "rats", "arts"} 和 {"star"}。注意澎办，"tars" 和 "arts" 是在同一組中嘲碱，即使它們并不相似。形式上局蚀，對每個組而言麦锯，要確定一個單詞在組中，只需要這個詞和該組中至少一個單詞相似琅绅。
給你一個字符串列表 strs扶欣。列表中的每個字符串都是 strs 中其它所有字符串的一個字母異位詞。請問 strs 中有多少個相似字符串組？
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/similar-string-groups
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有料祠。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)骆捧，非商業(yè)轉(zhuǎn)載請注明出處。
解題思路:
將相似的兩個字符串連成一個邊术陶，構(gòu)建一個父節(jié)點列表凑懂，通過相似性修改父節(jié)點列表中的值。
這些并集中有且只有一個父節(jié)點值等于自身索引梧宫。
最后遍歷一遍獲取自身索引與父節(jié)點值相等的總個數(shù)，即為相識數(shù)組的個數(shù)摆碉。
代碼:
public:
vector<int> parent;
int findParent(int index)
{
if (index == parent[index])
{
return index;
}
return findParent(parent[index]);
}
bool IsSimilarGroups(const string& strF, const string&strS)
{
if (strF.size() != strS.size())
{
return false;
}
if (strF == strS)
{
return true;
}
auto strSize = strF.size();
size_t count = 0;
for (size_t i = 0; i < strSize; i++)
{
if (strF[i] != strS[i])
{
count++;
if (count > 2)
{
break;
}
}
}
if (count >2)
{
return false;
}
return true;
}
int numSimilarGroups(vector<string>& strs) {
size_t strSize = strs.size();
parent.resize(strSize);
for (size_t i = 0; i < strSize; i++)
{
parent[i] = i;
}
for (size_t i = 0; i < strSize; i++)
{
for (size_t j = i + 1; j < strSize; j++)
{
int iIndex = findParent(i);
int jIndex = findParent(j);
if (iIndex != jIndex)
{
if (IsSimilarGroups(strs[i], strs[j]))
{
parent[iIndex] = jIndex;
}
}
}
}
int ret = 0;
for (size_t i = 0; i < strSize; i++)
{
if (parent[i] == i)
{
ret++;
}
}
return ret;
}
Review：閱讀并點評至少一篇英文技術(shù)文章
const T* ptr 和 T* const ptr的判斷
const是一個編程技術(shù)需要提升必須要熟知的一個知識點塘匣，永遠也不會過時
Tip：學習至少一個技術(shù)技巧
windows平臺下文件監(jiān)控的幾種方式:
1、ReadDirectoryChangesW : 增巷帝、刪忌卤、重命名
2、ChangeNotifyWatcher: 通過注冊窗口消息楞泼，當文件變更時驰徊，會回調(diào)消息到指定窗口
3、FindFirstChangeNotification:(為使用)
Share：分享一篇有觀點和思考的技術(shù)文章
const堕阔、enum棍厂、inline優(yōu)于#define
多多使用const
確定變量使用前首先進行初始化
重新閱讀 Effective C++，感觸會更加的深刻超陆，之后要細細梳理牺弹，爭取能夠以自己的理解寫出來