并查集和LRUCache

柔光的暖阳◎ 2024-03-16 22:39 34阅读 0赞

**目录**

1. 并查集

1.1原理

1.2实现

1.3应用

1.3.1省份数量

1.3.2等式方程的可满足性

2.LRUCache

1.概念

2.实现

3.JDK中类似LRUCahe的数据结构LinkedHashMap

4.LRU Cache的OJ

--------------------

## 1. 并查集 ##

### 1.1原理 ###

把不同的元素划分到不想交的集合.开始时,每个元素自成一个单元集合,然后按照规律把是同一组的元素集合合并

s1=\{0,6,7,8\}，s2=\{1,4,9\}，s3=\{2,3,5\}

![94f90bd5cfd849bbaf9322a529308d95.png][]

![57dbe95bb2d84816997e838432e1db3a.png][]

结论:

1.元素下标对应集合中元素的编号 例如:array\[8\]的值0是8的父亲

2.如果有负号,负号代表根,数字代表集合的元素个数

3.如果为非负数,为父亲在数组的下标

问题:

1.查找元素属于哪个集合

根据数组表示的树形关系找根

2. 查看两个元素是否属于同一个集合

根据数组表示的树形关系找根,如果根相同表示在同一个集合

3. 将两个集合归并成一个集合

A集合改为B集合的名称,B集合数为两个集合数数之和

4. 集合的个数

遍历数组，数组中元素为负数的个数即为集合的个数

### 1.2实现 ###

public class UnionFindSet {
        public int[] elem;
    
        public  UnionFindSet(int n){
            this.elem=new int[n];
            Arrays.fill(elem,-1);
        }
        //找根
        public int findRoot(int x){
            if(x<0){
                throw  new IndexOutOfBoundsException();
            }
            while(elem[x]>0){//值为负数为根
                x=elem[x];
            }
            return x;
        }
        //判断是不是一个集合
        public boolean isSame(int x1,int x2){
            int index1=findRoot(x1);
            int index2=findRoot(x2);
            return index1==index2 ? true :false;
        }
        //合并
        public void union(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 int getCount(int x){
            int count=0;
            for(int s:elem){
                if(s<0){
                    count++;
                }
            }
            return count;
        }
        public void print(){
            for(int x:elem){
                System.out.print(x+" ");
            }
            System.out.println();
        }
    }

### 1.3应用 ###

#### 1.3.1省份数量 ####

![8eaff2e5d5384d8ebb99e8e7f774156e.png][]

把为1的合并,输出集合的个数

class Solution {
        public int findCircleNum(int[][] isConnected) {
            int len=isConnected.length;
            UnionFindSet union=new UnionFindSet(len);
            for(int i=0;i<isConnected.length;i++){
                for(int j=0;j<isConnected[0].length;j++){
                    if(isConnected[i][j]==1){
                        union.union(i,j);
                    }
                }
            }
            return union.getCount();
        }
    }
    class UnionFindSet{
        public int[] elem;
    
        public UnionFindSet(int n){
            this.elem=new int[n];
            Arrays.fill(elem,-1);
        }
    
        //找根节点
        public int find(int x){
            if(x < 0) {
                throw new IndexOutOfBoundsException("下标不合法，是负数");
            }
            while(elem[x]>=0){
                x=elem[x];
            }
            return x;
        }
    
    
        //是否在一个集合
        public boolean isSame(int x1,int x2){
            int index1=find(x1);
            int index2=find(x2);
            return index1==index2 ?true :false;
        }
        //合并
        public void union(int x1,int x2){
            int index1=find(x1);
            int index2=find(x2);
            if(index1==index2) return ;
            elem[index1]=elem[index1]+elem[index2];
            elem[index2]=index1;
        }
    
    
        //个数
        public int getCount(){
            int count=0;
            for(int i:elem){
                if(i<0){
                    count++;
                }
            }
            return count;
        }
    }

#### 1.3.2等式方程的可满足性 ####

###  ###

## ![03ca7a4b01b1425e9b7dab0df485d2a4.png][] ##

把是==的两个放到一个集合,检查!=两个的是否在一个集合,如果不在==>满足

class Solution {
        public boolean equationsPossible(String[] equations) {
            UnionFindSet UnionFindSet=new UnionFindSet(26);
            for(int i=0;i<equations.length;i++){
                if(equations[i].charAt(1)=='='){
                    UnionFindSet.unoin(equations[i].charAt(0)-'a',equations[i].charAt(3)-'a');
                }
            }
            for(int i=0;i<equations.length;i++){
                if(equations[i].charAt(1)=='!'){
                      int root1=  UnionFindSet.find(equations[i].charAt(0)-'a');
                    int root2= UnionFindSet.find(equations[i].charAt(3)-'a');
                    if(root1==root2){
                        return false;
                    }
                }
            }
            return true;
    }
    }
    
    public class UnionFindSet {
        public int[] elem;
    
        public UnionFindSet(int n){
            this.elem=new int[n];
            Arrays.fill(elem,-1);
        }
    
        //找根
        public int find(int x){
            if(x<0){
                throw new IndexOutOfBoundsException("下标不合法，是负数");
            }
            while(elem[x]>=0){
                x=elem[x];
            }
            return x;
    
        }
    
        //是不是在一个集合
        public boolean isSame(int x1,int x2){
            int index1=find(x1);
            int index2=find(x2);
            return index1==index2 ?true:false;
        }
    
    
        //合并
        public void unoin(int x1,int x2){
            int index1=find(x1);
            int index2=find(x2);
            if(index1==index2) return;
            elem[index1]=elem[index1]+elem[index2];
            elem[index2]=index1;
        }
    }

###  ###

## 2.LRUCache ##

### 1.概念 ###

一种Cache替换算法,把最近少使用的内容替换掉

### 2.实现 ###

用双向链表和哈希表搭配

双向链表可以实现任意位置O(1)的插入和删除，使用哈希表是因为哈希表(快速定位)的增删查改也是O(1)。

![a14bcc017ec945b5b3fd91a803736851.png][]

### 3.JDK中类似LRUCahe的数据结构LinkedHashMap ###

参数说明：

1. initialCapacity 初始容量大小，使用无参构造方法时，此值默认是16

2. loadFactor 加载因子，使用无参构造方法时，此值默认是 0.75f

3. accessOrder false： 基于插入顺序 true： 基于访问顺序

示例1：当值为false的时候 基于插入顺序

LinkedHashMap<String,Integer> linkedHashMap=
            new LinkedHashMap<String,Integer>(16, (float) 0.7,false);
    linkedHashMap.put("mq",1);
    linkedHashMap.put("haha",11);
    linkedHashMap.put("hello",12);
    System.out.println(linkedHashMap);
    System.out.println("获取元素");
    System.out.println(linkedHashMap.get("haha"));
    System.out.println(linkedHashMap);

### ![336884a7c9aa46c88e194cd78023622d.png][] ###

示例2：当值为true的时候 基于访问顺序

LinkedHashMap<String,Integer> linkedHashMap=
            new LinkedHashMap<String,Integer>(16, (float) 0.7,true);
    linkedHashMap.put("mq",1);
    linkedHashMap.put("haha",11);
    linkedHashMap.put("hello",12);
    System.out.println(linkedHashMap);
    System.out.println("获取元素");
    System.out.println(linkedHashMap.get("haha"));
    System.out.println(linkedHashMap);

访问过的放到尾部

### ![4145a832d9be4adba58c4273cb4eff7a.png][] ###

###  ###

### 4.LRU Cache的OJ ###

![42be2453406f41c5a97edc4e04458f7a.png][]

public class LRUCache extends  LinkedHashMap<Integer,Integer>{
        public int capacity;
        LRUCache(int capacity){
            //true基于访问顺序
            super(capacity,0.75f,true);
            this.capacity=capacity;
    
        }
        @Override
        public Integer get(Object key) {
            return super.getOrDefault(key,-1);
        }
    
        @Override
        public Integer put(Integer key, Integer value) {
            return super.put(key, value);
        }
    
        @Override
        protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
            return size()>capacity;
        }
    }

public class LRUCache {
        static class DLinkNode{
            public  int key;
            public int val;
            public DLinkNode prev;
            public DLinkNode next;
    
            public DLinkNode(){
    
            }
            public DLinkNode(int key,int val){
                this.key=key;
                this.val=val;
            }
    
            @Override
            public String toString() {
                return "{ key=" + key + ", val=" + val+"} ";
            }
        }
    
        public  DLinkNode head;
        public DLinkNode tail;
        public  int usedSize;//有效数据个数
        public Map<Integer,DLinkNode>   cache;
        public int capacity;//默认容量
    
        public  LRUCache(int capacity){
            this.head=new DLinkNode();
            this.tail=new DLinkNode();
            head.next=tail;
            tail.prev=head;
            cache=new HashMap<>();
            this.capacity=capacity;
        }
    
        /**
         * 存储元素
         * 1.查找是否存储过
         * 2.没有
         * 2.1 实例化结点
         * 2.2 存储到map中
         * 2.3 将该结点移动到尾结点(新插入的)
         * 2.4 检查当前有效个数是不是超过capacity
         * 2.5 超过,去掉头结点
         * 2.6 清除缓存中的元素
         * 2.7 usedSize--
         * 3.有
         * 3.1 更新key对应的val
         * 3.2 将该结点移动到尾结点(新插入的)
         * @param key
         * @param val
         */
        public  void  put(int key,int val){
            DLinkNode node=cache.get(key);
            if(node==null){
                DLinkNode dLinkNode=new DLinkNode(key,val);
                cache.put(key,dLinkNode);
                addToTail(dLinkNode);
                usedSize++;
                if(usedSize>capacity){
                    DLinkNode dLinkNode1=removeHead();
                    cache.remove(dLinkNode1.key);//清除
                    usedSize--;
                }
            }else{
                node.val=val;
                moveToTail(node);
            }
        }
    
        /**
         * 移除当前结点到尾结点
         */
        private void moveToTail(DLinkNode node) {
            //1.删除
            node.prev.next=node.next;
            node.next.prev=node.prev;
            //2.加到尾部
            addToTail(node);
        }
    
        /**
         * 插入到尾结点
         * @param node
         */
        private void addToTail(DLinkNode node){
            tail.prev.next=node;
            node.prev=tail.prev;
            node.next=tail;
            tail.prev=node;
        }
    
        /**
         * 移除第一个结点
         * @return
         */
        private DLinkNode removeHead(){
            DLinkNode del=head.next;
            head.next=del.next;
            del.next.prev=head;
            return del;
        }
    
    
    
        /**
         * 把访问的结点放到尾巴
         * @return
         */
        public int get(int key){
            DLinkNode node=cache.get(key);
            if(node==null){
                return -1;
            }
            moveToTail(node);
            return node.val;
        }
    }

[94f90bd5cfd849bbaf9322a529308d95.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/80e6f25f4a74423c838b1c823c448b4c.png
[57dbe95bb2d84816997e838432e1db3a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/79fa13e48ecf46acb33a111c1af0548f.png
[8eaff2e5d5384d8ebb99e8e7f774156e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/5aed0286985f421cb52d888f644025d5.png
[03ca7a4b01b1425e9b7dab0df485d2a4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/3806e11f341d4c44bc724a7314c52e7c.png
[a14bcc017ec945b5b3fd91a803736851.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/f1d31f67c2bf47f3bd988ec426739263.png
[336884a7c9aa46c88e194cd78023622d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/a4487abe6e1d464195360691fce4e120.png
[4145a832d9be4adba58c4273cb4eff7a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/54e551b4b13c4cc9b4e01d43e98fcd05.png
[42be2453406f41c5a97edc4e04458f7a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/08b19d062b7c49dcb53b0fd43b8efe30.png