深入理解 并查集LRUCaChe

并查集&LRUCaChe

个人主页：顾漂亮
文章专栏：Java数据结构

1.并查集的原理

在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后根据一定规律将归于同一组元素的集合合并。在此过程中要反复运用到查询某一个元素归属于哪一个集合的运算。适合于描述这类问题的抽象数据类型称为并查集，（union - find set）并查集的底层运用的是数组。

举例：

​ 1.初始情况：假设现在有10个元素（0 - 9），开始情况是每一个元素相互独立，每个元素自成一个单元素集合。

提问：为什么初始情况下数组元素全为-1？

在回答上述问题之前，我们应该先了解以下并查集的使用规则：

• 数组的下标对应集合中的元素，例如数组9下标对应的就是9这个元素
• 数组中的值如果为负数，负号表示根，数字代表该集合中元素的个数
• 数组中的值如果是非负数，代表该元素双亲结点在数组中的下标

根据上述规则，我们可以知道初始情况下10个元素，每个元素自成一个单元素集合，因此-1代表，每个单元素集合中只有一个元素，并且这个元素的根也是其本身。

​ 2.**初次合并：**将单元素集合按照下图所示规律进行合并成三个集合

可以得到并查集图形为：

3.第二次合并：将单元素集合按照下图所示规律进行合并成三个集合

可以得到并查集图形为：

2.并查集可以解决的问题

1. 查找元素属于哪一个集合
   • 根据数组表示的树形关系向上寻找，一直找到根
2. 查看两个元素是否属于同一个集合
   • 比较两个集合的根是否相同，相同属于同一个集合，反之则不属于一个集合
3. 将两个集合合并成一个集合
   • 先将两个集合的根合并
4. 集合的个数
   • 遍历数组，数组中元素为非负数的个数即为集合的个数

3.并查集的代码实现

import java.util.Arrays;public class UnionFindSet {public int[] elem;//底层为数组public UnionFindSet(int n){//初始化数组大小为nelem = new int[n];//将数组中元素初始化为-1Arrays.fill(elem,-1);}//查找根public int findRoot(int val){if(val < 0){throw new IndexOutOfBoundsException("val不合法");}while(elem[val] >= 0){val = elem[val];}return val;}//合并操作public void union(int x1, int x2){//确定两个元素根节点int index1 = findRoot(x1);int index2 = findRoot(x2);//如果两个元素属于同一个集合if(index2 == index1){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(index2 == index1){return true;}return false;}//求数组中集合的个数public int getCount(){int count = 0;for (int i = 0; i < elem.length; i++) {if(elem[i] < 0){count++;}}return count;}//打印数组public void printSet(){for (int i = 0; i < elem.length; i++) {System.out.print(elem[i] + " ");}System.out.println();}
}

4.并查集相关面试题

省份问题：

• 求解思路：
  • 实现一个并查集
  • 如果两个城市联通，放在一个集合中
  • 返回并查集中元素小于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 < isConnected[i].length; j++){if(isConnected[i][j] == 1){//合并ufs.union(i,j);}   }}return ufs.getCount();}}class UnionFindSet {public int[] elem;//底层为数组public UnionFindSet(int n){elem = new int[n];//初始化为n大小的数组Arrays.fill(elem, -1);//将数组初始化为-1，注意，为什么初始化为-1？}//查找根public int findRoot(int val){if(val < 0){throw new IndexOutOfBoundsException("数据不合法");}//注意这个循环算法易错while(elem[val] >= 0){val = elem[val];}return val;}//合并操作public void union(int x1, int x2){int index1 = findRoot(x1);int index2 = findRoot(x2);//如果根相同，直接返回if(index2 == index1){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(index2 == index1){return true;}return false;}//求数组中集合的个数public int getCount(){int count = 0;for (int i = 0; i < elem.length; i++) {if(elem[i] < 0){count++;}}return count;}//打印数组public void printSet(){for (int i = 0; i < elem.length; i++) {System.out.print(elem[i] + " ");}System.out.println();}
}

等式方程可满足性：

• 解题思路：
  • 将"=="两边数据放入一个集合中
  • 检查"!="两边数据是否在同一个集合中，如果在返回false，如果不再返回true

class Solution {public boolean equationsPossible(String[] equations) {UnionFindSet set = new UnionFindSet(26);//一共有26个英文字母//1. 将“=”号左右元素合并成同一个集合for(int i = 0; i < equations.length; i++){if(equations[i].charAt(1) == '='){set.union(equations[i].charAt(0) - 'a', equations[i].charAt(3) - 'a');}}//2. 检查“!”左右两边是否在同一个集合中for(int i = 0; i < equations.length; i++){if(equations[i].charAt(1) == '!'){if(set.isSameSet(equations[i].charAt(0)  - 'a', equations[i].charAt(3)  - 'a')){return false;}}}return true;}
}class UnionFindSet {public int[] elem;//底层为数组public UnionFindSet(int n){elem = new int[n];//初始化为n大小的数组Arrays.fill(elem, -1);//将数组初始化为-1，注意，为什么初始化为-1？}//查找根public int findRoot(int val){if(val < 0){throw new IndexOutOfBoundsException("数据不合法");}//注意这个循环算法易错while(elem[val] >= 0){val = elem[val];}return val;}//合并操作public void union(int x1, int x2){int index1 = findRoot(x1);int index2 = findRoot(x2);//如果根相同，直接返回if(index2 == index1){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(index2 == index1){return true;}return false;}//求数组中集合的个数public int getCount(){int count = 0;for (int i = 0; i < elem.length; i++) {if(elem[i] < 0){count++;}}return count;}//打印数组public void printSet(){for (int i = 0; i < elem.length; i++) {System.out.print(elem[i] + " ");}System.out.println();}
}

LRUCaChe

1.概念解析：

1.1什么是LRU？

LRU（Last recently used）的缩写，意思是最近最少使用，是一种CaChe替换算法。

1.2什么是Cache？

狭义上：Cache是指位于CPU和主存间的快速RAM，通常它不像系统主存那样使用DRAM技术，而是用昂贵但是较为快速的SRAM技术

广义上：位于速度相差较大的两种硬件之间，用于协调两者数据传输速度差异的结构。处理CPU与主内存之间有Cache，内存与磁盘之间也有， 乃至在硬件与网络之间也有某种意义上的Cache–称为Internet临时文件夹或网络内容缓存等

Cache的内存容量有限，因此当Cache的容量用完后，而又有新的内容需要添加进来时候，就需要挑选并舍弃相应的元素，从而腾出空间来存放新的内容。LRUCaChe的替换原则就是将最近最少使用的内容替换掉

2.LRUCache的实现

其实现方式可以有很多，但是为了追求最高的效率，我们采用哈希表和双向链表来实现LRUCaChe，哈希表的增删查改是O(1)，双向链表可以实现任意位置插入删除为O(1)

2.1JDK中的LinkedHashMap

参数说明：

• initialCapacity：容量大小

• loadFacto:加载因子，使用无参构造方法时，此值默认为0.75f

• accessOrder:默认为false->基于插入顺序存放； true ->基于访问顺序

使用案例：

import java.util.LinkedHashMap;
import java.util.Map;public class LRUCache extends LinkedHashMap<Integer, Integer> {public int capacity;//容量public LRUCache(int capacity){super(capacity, 0.75f, true);//调用父类构造函数，必须放在构造函数第一行this.capacity = capacity;}public int get(int key){return super.getOrDefault(key, -1);}public void put(int key, int value){super.put(key, value);}//必须要重写上述方法@Overrideprotected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {return size() > capacity;//默认返回false，如果为true，则需要进行移除最近未使用的元素}
}

2.2LRUCaChe的实现

package LRUCache;import java.util.HashMap;
import java.util.Map;public class MyLRUCache {//双向链表节点static class LRUNode{public int val;public int key;public LRUNode prev;public LRUNode next;//给一个无参构造方法，初始化带头带尾双向链表头节点public LRUNode(){}public LRUNode(int key, int val){this.key = key;this.val = val;}//重写Object类中的方法，将双向链表节点值以字符串形式输出@Overridepublic String toString() {return "{" +"key=" + key +", val=" + val +'}';}}//需要声明一个哈希表，用来检查节点值是否存在private Map<Integer, LRUNode> cache;private int usedSize;//双向链表中有效数据的个数private int capacity;//双向链表的容量大小private LRUNode head, tail;public MyLRUCache(int capacity){this.usedSize = 0;this.capacity = capacity;cache = new HashMap<>();//实例化哈希表//伪头节点/尾节点head = new LRUNode();tail = new LRUNode();//先将链表头尾节点相连head.next = tail;tail.prev = head;}//存储元素public void put(int key, int val){//1.查找当前的key是否存储过LRUNode node = cache.get(key);//2.判断key在链表中是否存储过if (node != null){//存储过，更新节点对应的valnode.val = val;//将节点移动到末端moveToTail(node);}else{//没有存储过,新建一个节点值LRUNode cur = new LRUNode(key, val);//先插入哈希中cache.put(key, cur);//将节点添加到链表尾部addToTail(cur);usedSize++;//判断容量是否充足if(usedSize > capacity){//删除最近未使用的节点removeNode(head.next);//删除哈希表中的节点cache.remove(head.next.key);usedSize--;}}}private void addToTail(LRUNode node) {tail.prev.next = node;node.next = tail;node.prev = tail.prev;tail.prev = node;}private void moveToTail(LRUNode node) {//先删除节点removeNode(node);//将节点尾插addToTail(node);}//删除节点private void removeNode(LRUNode node) {node.prev.next = node.next;node.next.prev = node.prev;}//获取元素public int get(int key){//判断元素是否在链表中LRUNode node = cache.get(key);if(node == null) {return -1;}else{moveToTail(node);}return node.val;}public void printLRU(){LRUNode cur = head.next;while(cur != tail){System.out.print(cur);cur = cur.next;}System.out.println();}public static void main(String[] args) {MyLRUCache lruCache = new MyLRUCache(3);lruCache.put(100,10);lruCache.put(110,11);lruCache.put(120,12);lruCache.printLRU();System.out.println("获取元素");System.out.println(lruCache.get(110));System.out.println(lruCache.get(100));lruCache.printLRU();System.out.println("存放元素,会删除头节点，因为头节点是最近最少使用的: ");lruCache.put(999,99);lruCache.printLRU();}}