并查集的定義

將n個(gè)不同的元素劃分成一些不相交的集合。開始時(shí)，每個(gè)元素自成一個(gè)單元素集合，然后按一定的規(guī)律將歸于同一組元素的集合合并。在此過程中要反復(fù)用到查詢某一個(gè)元素歸屬于那個(gè)集合的運(yùn)算。適合于描述這類問題的抽象數(shù)據(jù)類型稱為并查集(union find set)

并查集的抽象描述

struct UnionFindSet
屬性
數(shù)個(gè)不相交的集合,通過數(shù)組管理 vector
方法
檢查兩個(gè)元素是否屬于同一個(gè)集合 bool inSameSet(e1,e2);
尋找集合的根元素 e findEigen(e) ;
合并兩個(gè)元素所在的集合 void merge(e1,e1);
計(jì)算當(dāng)前集合個(gè)數(shù) size_t getCnt();

如何表示同一個(gè)集合的元素：
可以借助數(shù)組抽象結(jié)構(gòu)的方法對(duì)同一集合的元素進(jìn)行分類，為了方便，后續(xù)把代表某個(gè)集合的元素成為特征元素
首先把每一個(gè)元素都被映射成了一個(gè)唯一的編號(hào)id，id同時(shí)也作為數(shù)組的下標(biāo)
規(guī)定每一個(gè)下標(biāo)所對(duì)應(yīng)值為集合中其他元素的編號(hào)id，如果數(shù)組中某一個(gè)id位置的值為-x，代表它是一個(gè)特征元素,并且集合中有x個(gè)元素

![在這里插入圖片描述](https://i-blog.csdnimg.cn/direct/acbe9e49efa14b8d80c19692a2c4e07e.png

并查集具體實(shí)現(xiàn)

//此處代碼忽略了映射關(guān)系的構(gòu)建，數(shù)組下標(biāo)值就是對(duì)應(yīng)的真實(shí)元素值
class UnionFindSet
{
private:vector<int> ufs;
public:UnionFindSet(unsigned int n=0):ufs(n,-1){}  //初始狀態(tài)所有的元素都各自為一個(gè)集合，元素之間沒有任何關(guān)系unsigned int getCnt(){unsigned int cnt=0;for(int x:ufs) if(x==-1) ++cnt;return cnt;}	//統(tǒng)計(jì)ufs數(shù)組中-1的個(gè)數(shù)即可獲得集合個(gè)數(shù)unsigned int findEigen(unsigned int e){	unsigned int eigenval=e;while(ufs[eigenval]>=0) eigenval=ufs[eigenval];return eigenval;}	//迭代向上尋找，直至數(shù)組中的值為-1bool inSameSet(unsigned int e1,unsigned int e2){return findEigen(e1)==findEigen(e2);}void merge(unsigned int e1,unsigned int e2){unsigned int eigen1=findEigen(e1);unsigned int eigen2=findEigen(e2);if(eigen1!=eigen2) {ufs[eigen1]+=ufs[eigen2];ufs[eigen2]=eigen1;}//把e2所在集合的特征元素對(duì)應(yīng)的值改為e1所在集合的特征元素即可完成2個(gè)集合的合并}
};

優(yōu)化合并與查找

合并優(yōu)化：小集合合并到大集合中，做到更多的元素能在短時(shí)間內(nèi)找到特征元素

void merge(unsigned int e1,unsigned int e2)
{unsigned int eigen1=findEigen(e1);unsigned int eigen2=findEigen(e2);if(eigen1!=eigen2){if(ufs[eigen1]>ufs[eigen2]) swap(eigen1,eigen2); //統(tǒng)一規(guī)定集合eigen1的元素個(gè)數(shù)更大ufs[eigen1]+= ufs[eigen2];ufs[eigen2]=eigen1;}
}

查找優(yōu)化：最理想的情況是每一個(gè)節(jié)點(diǎn)至多一次找到所在集合的特征元素

可以考慮每一次進(jìn)行findEigen查找時(shí)對(duì)集合元素關(guān)系進(jìn)行調(diào)整，使得每一個(gè)元素在集合中更接近特征元素

unsigned int findEigen(unsigned int e) 
{unsigned int eigen = e, prev = -1;while (_ufs[eigen] >= 0) {int tmp = ufs[eigen];//向上查找if (prev>=0) ufs[prev] = tmp;prev = eigen;eigen = tmp;}return eigen;
}

上述代碼未經(jīng)測(cè)試，可能存在bug，經(jīng)測(cè)試版代碼請(qǐng)參考https://gitee.com/chxchenhaixiao/test_c/blob/master/UnionFindSet/UnionFindSet.h

LRU cache

LRU是Least Recently Used的縮寫，意思是最近最少使用，它是一種Cache替換算法
簡(jiǎn)單地說就是淘汰長(zhǎng)久未使用的數(shù)據(jù)，cache的大小是固定有限的，當(dāng)空間滿時(shí)如果還需要加入數(shù)據(jù)就必須淘汰部分先前的數(shù)據(jù)

可以把每一個(gè)數(shù)據(jù)塊通過一個(gè)雙向鏈表級(jí)聯(lián)，人為規(guī)定鏈表尾節(jié)點(diǎn)為長(zhǎng)時(shí)間未使用即將被淘汰的資源，鏈表頭節(jié)點(diǎn)為最近使用的數(shù)據(jù)，借助哈希表實(shí)現(xiàn)對(duì)各個(gè)數(shù)據(jù)塊的快速定位，達(dá)到增刪查改的時(shí)間復(fù)雜度均為O（1）

代碼實(shí)現(xiàn)：

class LRUCache {size_t _size=0; //鏈表當(dāng)前長(zhǎng)度size_t _capacity; //cache最大容量list<pair<int,int>> _list;typedef list<pair<int,int>>::iterator iterator;unordered_map<int,iterator> _map;
public:LRUCache(int capacity) :_capacity(capacity){}int get(int key) {if(!_map.count(key)) return -1;iterator it=_map[key];int val=it->second;_list.push_front(*it);_list.erase(it);_map[key]=_list.begin();return val;}void put(int key, int value) {if(_map.count(key)) //更新節(jié)點(diǎn){iterator it=_map[key];it->second=value;_list.push_front(*it);_list.erase(it);_map[key]=_list.begin();}else{if(_size<_capacity){++_size;_list.push_front({key,value});_map[key]=_list.begin();}else{auto& last=_list.back(); //獲取鏈表尾節(jié)點(diǎn)_map.erase(last.first); //刪除map中指向尾的映射關(guān)系_list.pop_back();   //刪除鏈表尾節(jié)點(diǎn)_list.push_front({key,value}); //頭插_map[key]=_list.begin(); //更新map}}}
};