数据结构之并查集和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;}
}