深入理解 并查集LRUCaChe

devtools/2025/2/27 11:38:37/

并查集&LRUCaChe

在这里插入图片描述

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

1.并查集的原理

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

举例：

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

在这里插入图片描述

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

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

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

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

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

在这里插入图片描述

可以得到并查集图形为：

在这里插入图片描述

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

在这里插入图片描述

可以得到并查集图形为：

在这里插入图片描述

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

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

3.并查集的代码实现

java">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的个数即为省份数量
java">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
java">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 ->基于访问顺序

使用案例：

java">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的实现

java">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();}}

http://www.ppmy.cn/devtools/163047.html

相关文章

【0010】HTML水平线标签详解

【0010】HTML水平线标签详解

如果你觉得我的文章写的不错&#xff0c;请关注我哟&#xff0c;请点赞、评论&#xff0c;收藏此文章&#xff0c;谢谢&#xff01; 本文内容体系结构如下&#xff1a; 一、水平线标签概述 在HTML中&#xff0c;<hr>标签用于在网页上插入一条水平线&#xff0c;其主要…
阅读更多...
网络安全复习资料

网络安全复习资料

网络安全复习资料 1.计算机网络安全是指保持网络中的硬件、软件系统正常运行&#xff0c;使他们不因自然和人为的因素而受到破坏、更改和泄露。 2.网络安全&#xff1a;物理安全&#xff0c;软件安全&#xff0c;信息安全&#xff0c;运行安全。 3.安全防范措施&#xff1a…
阅读更多...
Docker快速使用指南

Docker快速使用指南

docker pull ubuntu:22.04 //先拉取一个基础镜像&#xff0c;一般是操作系统创建一个Dockerfile&#xff0c;放在任意目录下&#xff0c;内容如下 # 使用 Ubuntu 22.04 作为基础镜像 FROM ubuntu:22.04# 设置环境变量&#xff0c;避免安装过程中出现交互提示 ENV DEBIAN_FRONT…
阅读更多...
【每日八股】Redis篇（二）：数据结构

【每日八股】Redis篇（二）：数据结构

Redis 数据类型&#xff1f; 主要有 STRING、LIST、ZSET、SET 和 HASH。 STRING String 类型底层的数据结构实现主要是 SDS&#xff08;简单动态字符串&#xff09;&#xff0c;其主要应用场景包括&#xff1a; 缓存对象&#xff1a;可以用 STRING 缓存整个对象的 JSON&…
阅读更多...
Windows 图形显示驱动开发-WDDM 3.2-自动显示切换(八)

Windows 图形显示驱动开发-WDDM 3.2-自动显示切换(八)

适配器启动时间 驱动程序启动时&#xff0c;需要响应 OS 的轮询请求。 驱动程序可以通过尝试通信来发现多路复用器是否切换到了它们&#xff0c;但这可能会很耗时或不可靠。 作为 GPU 启动序列的一部分&#xff0c;OS 会调用 DxgkDdiDisplayMuxUpdateState DDI&#xff0c;以显…
阅读更多...
广州4399游戏25届春招游戏策划管培生内推

广州4399游戏25届春招游戏策划管培生内推

【热招岗位】 游戏策划管培生、产品培训生、游戏文案策划、游戏数值策划、游戏系统策划、游戏产品运营、游戏战斗策划、游戏关卡策划 【其他岗位】产品类&#xff08;产品培训生、产品运营等&#xff09;、技术类&#xff08;开发、测试、算法、运维等&#xff09;、运营市场类…
阅读更多...
【STL学习】（6）list的模拟

【STL学习】（6）list的模拟

前言 list的底层是带头双向循环链表&#xff0c;在数据结构专栏我们使用C语言简单模拟实现过&#xff0c;这里使用C模拟实现也是大同小异的。 建议&#xff1a;阅读本文如有困难的&#xff0c;可以点击下面链接&#xff0c;复习带头双向循环链表&#xff1a; C语言实现带头双向…
阅读更多...
DeepSeek本地搭建 和 Android

DeepSeek本地搭建 和 Android

DeepSeek 搭建和 Android 文章目录 DeepSeek 搭建和 Android一、前言二、DeepSeek 本地环境ollama搭建1、软件下载网址&#xff1a;2、Ollama的安装3、配置算法模型和使用qwen2 模型使用&#xff0c; 三、Android Studio 和 DeepSeek四、其他1、Deepseek 使用小结(1) 网页版本可…
阅读更多...
最新文章

Copyright @ 2022~2023