數據結構之并查集和LRUCache

系列文章目錄

數據結構之ArrayList_arraylist o(1) o(n)-CSDN博客

數據結構之LinkedList-CSDN博客

數據結構之棧_棧有什么方法-CSDN博客

數據結構之隊列-CSDN博客

數據結構之二叉樹-CSDN博客

數據結構之優先級隊列-CSDN博客

常見的排序方法-CSDN博客

數據結構之Map和Set-CSDN博客

數據結構之二叉平衡樹-CSDN博客

數據結構之位圖和布隆過濾器-CSDN博客

系列文章目錄

前言

一、并查集

1. 并查集的原理

2. 模擬實現并查集

3. 并查集的應用

1.判斷親戚關系

2. 判斷省份的數量

3.? 等式方程的可滿足性

二、LRUCache

1. LRUCache 的原理

2. 模擬實現 LRUCache

3. LinkedHashMap

4. 基于 LinkedHashMap 實現 LRUCache

前言

本文介紹了兩種重要的數據結構：并查集和LRUCache。并查集用于高效處理集合合并與查詢操作，文章詳細講解了其原理、模擬實現方法，并給出親戚關系判斷、省份數量計算等應用實例。LRUCache是一種緩存淘汰算法，文章剖析了其哈希表+雙向鏈表的實現原理，提供了完整的模擬實現代碼，并介紹了基于LinkedHashMap的簡化實現方案。兩種數據結構在實際開發中都有廣泛應用，本文通過代碼示例和解題思路展示了它們的具體使用方法。

一、并查集

1. 并查集的原理

合并集合：選取兩個集合，兩個集合選取相同的根節點，這兩個集合就被合并了；

查詢兩個元素是否屬于同一個集合：

查詢兩個元素之間的關系時，分別查詢兩個元素的根節點；

如果根節點相同，就表示兩個元素屬于同一個集合；

如果根節點不同，表示兩個元素不屬于同一個集合；

并查集適用于頻繁合并集合，以及頻繁查詢某兩個元素是否屬于同一集合的應用場景；

2. 模擬實現并查集

elem：表示全集

數組下標表示當前節點，數組中存放的值，表示上一級節點；

例如：elem[0] = 10，表示 0 的父節點是 10；

如果 i?是根節點，則 elem[i] 須為負數，用負數表示根，負號后面的值為當前集合中元素的個數；

例如：0 是根節點，elem[0] = -10，表示 0 為根節點，且這個集合中有 10 個元素；

unionFindSet(int n)：并查集的構造方法

n 表示全集中元素的個數；

elem 中所有值都初始化為 -1，表示未合并前都是根節點，且集合中只有當前值這一個元素；

findRoot(int x): int 找 x 所屬集合的根節點

如果 x 不存在，拋異常；

循環查找 x 上級節點 elem[x]（x = elem[x]），直到 elem[x] 小于 0，即表示 x 為根節點；

union(int x1, int x2): void 合并 x1 和 x2 所在的集合

判斷 x1 和 x2 是否在同一個集合，即 x1 集合的根節點和 x2 集合的根節點是否為同一個節點；

如果是同一個節點，則表示在同一個集合，直接返回；

如果不是同一個節點（root1 表示 x1 所在集合的根節點，root2 表示 x2 所在集合的根節點）：

將 root1 集合?和 root2 集合節點的數量都累加在 root1 中，即 elem[root1] = elem[root1] + elem[root2]；

將 root2 的根節點改為 root1，即 elem[root2] = root1；

isSameUnionFindSet(int x1, int x2): boolean 判斷兩個節點是否屬于同一個集合

找 x1 和 x2 的根節點，并判斷是否為同一個節點；

如果是同一個節點，返回 true；

如果不是同一個節點，返回 false；

count(): int 計算一共有幾個集合?

遍歷 elem，返回負數的個數，即為集合的數量；

代碼實現：

public class UnionFindSet {public int[] elem;public UnionFindSet(int n){this.elem = new int[n];Arrays.fill(this.elem, -1);}public int findRoot(int x) {if(x < 0){throw new PosOutOfBoundsException("輸入的下標不合法，是負數！");}while(this.elem[x] >= 0){x = this.elem[x];}return x;}public boolean isSameUnionFindSet(int x1, int x2){int index1 = findRoot(x1);int index2 = findRoot(x2);if(index1 == index2){return true;}else{return false;}}public void union(int x1, int x2){int index1 = findRoot(x1);int index2 = findRoot(x2);if(index1 == index2){return;}this.elem[index1] = this.elem[index1] + this.elem[index2];this.elem[index2] = index1;}public int count(){int count = 0;for(int i = 0; i < this.elem.length; i++){if(this.elem[i] < 0) count++;}return count;}
}

3. 并查集的應用

1.判斷親戚關系

假設親戚的所有親戚也是親戚，有 10 個人，分別用 0 ~ 9 表示，。已知 0 和 6，7，8 是親戚關系，1 和 4，9是親戚關系，2 和 3，5 是親戚關系，判斷 6 和 9 是否是親戚關系，如果 8 和 1 締結了親戚關系，6 和 9 是否也有了親戚關系？

使用并查集判斷如下：

    public static void main(String[] args) {UnionFindSet unionFindSet = new UnionFindSet(10);unionFindSet.union(0, 6);unionFindSet.union(0, 7);unionFindSet.union(0, 8);unionFindSet.union(1, 4);unionFindSet.union(1, 9);unionFindSet.union(2, 3);unionFindSet.union(2, 5);System.out.println(unionFindSet.isSameUnionFindSet(6, 9));unionFindSet.union(8, 1);System.out.println(unionFindSet.isSameUnionFindSet(6, 9));}

運行結果：

2. 判斷省份的數量

有?n?個城市，其中一些彼此相連，另一些沒有相連。如果城市?a?與城市?b?直接相連，且城市?b?與城市?c?直接相連，那么城市?a?與城市?c?間接相連。

省份?是一組直接或間接相連的城市，組內不含其他沒有相連的城市。

給你一個?n x n?的矩陣?isConnected?，其中?isConnected[i][j] = 1?表示第?i?個城市和第?j?個城市直接相連，而?isConnected[i][j] = 0?表示二者不直接相連。

返回矩陣中?省份?的數量。

思路：

模擬實現并查集，利用并查集的思想，將相鄰的城市放到同一個集合，最終返回集合的數量即可；

class Solution {public int findCircleNum(int[][] isConnected) {int n = isConnected.length;UnionFindSet ufs = new UnionFindSet(n);for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){if(isConnected[i][j] == 1){ufs.union(i, j);}}}return ufs.count();}
}class UnionFindSet {public int[] elem;public UnionFindSet(int n){this.elem = new int[n];Arrays.fill(this.elem, -1);}public int findRoot(int x) {if(x < 0){return -1;}while(this.elem[x] >= 0){x = this.elem[x];}return x;}public boolean isSameUnionFindSet(int x1, int x2){int index1 = findRoot(x1);int index2 = findRoot(x2);if(index1 == index2){return true;}else{return false;}}public void union(int x1, int x2){int index1 = findRoot(x1);int index2 = findRoot(x2);if(index1 == index2){return;}this.elem[index1] = this.elem[index1] + this.elem[index2];this.elem[index2] = index1;}public int count(){int count = 0;for(int i = 0; i < this.elem.length; i++){if(this.elem[i] < 0) count++;}return count;}
}

3.? 等式方程的可滿足性

給定一個由表示變量之間關系的字符串方程組成的數組，每個字符串方程?equations[i]?的長度為?4，并采用兩種不同的形式之一："a==b"?或?"a!=b"。在這里，a 和 b 是小寫字母（不一定不同），表示單字母變量名。

只有當可以將整數分配給變量名，以便滿足所有給定的方程時才返回?true，否則返回?false。

示例 1：

輸入：["a==b","b!=a"]
輸出：false
解釋：如果我們指定，a = 1 且 b = 1，那么可以滿足第一個方程，但無法滿足第二個方程。沒有辦法分配變量同時滿足這兩個方程。

示例 2：

輸入：["b==a","a==b"]
輸出：true
解釋：我們可以指定 a = 1 且 b = 1 以滿足滿足這兩個方程。

思路：

模擬實現并查集，遍歷 equations 數組，將具有等式關系的都放到同一個集合；

再遍歷?equations 數組，依次檢查具有不等關系的元素，看是否在同一個集合；

如果在同一個集合，則不可能成立，因為具有相等關系才會在一個集合，此時返回 false，

如果所有具有不等關系的元素都不在同一個集合，返回 true；

class Solution {public int[] elem = new int[26];public int findRoot(int x){while(elem[x] >= 0){x = elem[x];}return x;} public void merge(int x1, int x2){int index1 = findRoot(x1);int index2 = findRoot(x2);if(index1 == index2) return;elem[index1] = elem[index1] + elem[index2];elem[index2] = index1;}public boolean isSameSet(int x1, int x2){int index1 = findRoot(x1);int index2 = findRoot(x2);if(index1 == index2){return true;}return false;}public boolean equationsPossible(String[] equations) {int n = equations.length;Arrays.fill(elem, -1);for(int i = 0; i < n; i++){String t = equations[i];if(t.charAt(1) == '='){merge(t.charAt(0) - 'a', t.charAt(3) - 'a');}}for(int i = 0; i < n; i++){String t = equations[i];if(t.charAt(1) == '!'){boolean flag = isSameSet(t.charAt(0) - 'a', t.charAt(3) - 'a');if(flag) return false;}}return true;}
}

二、LRUCache

1. LRUCache 的原理

LRU Cache 是 least recently used cache 的縮寫；

LRU Cache 是高速緩存使用的一種數據結構，高速緩存價格昂貴，容量有限；因此當緩存的資源滿了之后，再插入新資源時，就會淘汰最早使用的資源，保留最近使用的資源；

LRUCache 底層是一個哈希表加雙向鏈表的結構：

存入資源時會先存到鏈表的尾巴節點，如果超出最大緩存容量，會刪除頭結點的資源；

查詢資源時，不僅會將查詢的資源返回，還會將這個資源重新放到鏈表的尾巴節點；

哈希表的作用就是查詢某個資源會在 O(1) 的時間復雜度內查詢到，鏈表的作用是保證資源的順序（最近使用的順序），且插入刪除時間復雜度也是 O(1)；

2. 模擬實現 LRUCache

DLinkedNode：資源節點類，包含 key，val，prev，next 屬性，還有構造方法，作用參考哈希表和雙向鏈表；

head：頭結點，不存實際的資源；

tail：尾巴節點，不存實際的資源；

head 和 tail 的作用：方便雙向鏈表進行插入和刪除操作，不會出現空節點異常；

usedSize：當前保存的數據的數量；

cache：哈希表，用于保存 key 和 DLinkedNode 的映射關系，用于解決雙向鏈表查詢時間復雜度 O(N) 的問題；

capacity：緩存的最大容量；

public class MyLRUCache {static class DLinkedNode{public int key;public int val;public DLinkedNode prev;public DLinkedNode next;public DLinkedNode(){}public DLinkedNode(int key, int val){this.key = key;this.val = val;}}public DLinkedNode head;public DLinkedNode tail;public int usedSize;public Map<Integer, DLinkedNode> cache;public int capacity;// 方法// ......
}

MyLRUCache(int capacity) 初始化頭節點，尾巴節點，保存數據的數量，最大容量；

注意：一定要將頭節點和尾巴節點連起來，防止首次插入節點時出現空指針異常；

put(int key, int val): void 插入節點；

思路：

插入節點時，要檢查節點是否已經存在；

節點不存在，現在哈希表中增加節點，在雙向鏈表的尾巴節點插入，注意 usedSize++；

插入后，注意判斷當前節點的數量是否查過最大能緩存的數量；

如果超過了，要在哈希表中刪除節點，在雙向鏈表中刪除頭節點連接的第一個資源，注意 usedSize--；

如果節點已經存在了，更新節點的 val，并在雙向鏈表中，將該節點放到尾巴節點的位置；

get(int key): int 返回節點對應的 val；

節點不存在，返回 -1;

節點存在，返回節點的 val，返回之前注意將節點放到雙向鏈表尾巴節點的位置；

addToTail(DLinkedNode node)：在雙向鏈表的尾巴節點的位置插入節點 node；

removeHead(): DLinkedNode 刪除頭節點相連的節點，并返回該節點；

remove(DLinkedNode node): void 在雙向鏈表中刪除節點 node；

moveToTail(DLinkedNode node): void 在雙向鏈表中刪除 node，并將 node 放在雙向鏈表尾巴節點的位置；

    public MyLRUCache(int capacity){this.head = new DLinkedNode();this.tail = new DLinkedNode();this.head.next = this.tail;this.tail.prev = this.head;cache = new HashMap<>();this.capacity = capacity;this.usedSize = 0;}public void put(int key, int val){// 1. 插入的時候要判斷節點是否已經存在DLinkedNode node = cache.getOrDefault(key, null);if(node == null){// 3. 如果不存在，就插入哈希表DLinkedNode cur = new DLinkedNode(key, val);cache.put(key, cur);// 4. 將它放在隊尾addToTail(cur);this.usedSize++;// 5. 判斷容量是否超了if(usedSize > capacity){// 6. 刪除頭結點DLinkedNode t = removeHead();cache.remove(t.key);}}else{// 2. 如果存在，就要更新對應 key 的值node.val = val;moveToTail(node);}}public int get(int key){DLinkedNode node = cache.get(key);if(node == null){return -1;}moveToTail(node);return node.val;}private void addToTail(DLinkedNode node){DLinkedNode prev = this.tail.prev;prev.next = node;node.prev = prev;node.next = this.tail;this.tail.prev = node;}private DLinkedNode removeHead(){DLinkedNode dLinkedNode = this.head.next;DLinkedNode next = dLinkedNode.next;this.head.next = next;next.prev = this.head;return dLinkedNode;}private void moveToTail(DLinkedNode node){remove(node);addToTail(node);}private void remove(DLinkedNode node){DLinkedNode prev = node.prev;DLinkedNode next = node.next;prev.next = next;next.prev = prev;}

3. LinkedHashMap

JDK?中可以使用 LinkedHashMap 實現 LRUCache；

構造方法：

initialCapacity： 初始容量；

loadFactor：哈希表的負載因子；

accessOrder：

true：每次查詢或者新增后，都會將該節點放在雙向鏈表的尾巴節點的位置；

false：會按照默認順序存放，默認為 false；

    public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {super(initialCapacity, loadFactor);this.accessOrder = accessOrder;}

afterNodeInsertion(boolean evict): void 插入節點后是否要刪除插入最早的節點；

    void afterNodeInsertion(boolean evict) { // possibly remove eldestLinkedHashMap.Entry<K,V> first;if (evict && (first = head) != null && removeEldestEntry(first)) {K key = first.key;removeNode(hash(key), key, null, false, true);}}

removeEldestEntry(Map.Entry<K, V> eldest): boolean 是否刪除最老的節點，默認為 false；

    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {return false;}

使用 LinkedHashMap 實現 LRUCache 一定要重寫這個方法；

4. 基于 LinkedHashMap 實現 LRUCache

基于 LinkedHashMap 實現需要指定容量，重寫 put() 和 get() 方法；

重寫 removeEldestEntry()：當數據量超出指定容量后，會刪除最老的數據；?

public class LRUCacheOnLinkedHashMap extends LinkedHashMap<Integer, Integer> {public int capacity;public LRUCacheOnLinkedHashMap(int capacity){this.capacity = capacity;}@Overridepublic Integer put(Integer key, Integer value) {return super.put(key, value);}@Overridepublic Integer get(Object key) {return super.get(key);}@Overrideprotected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {return size() > capacity;}
}