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}

结论:

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省份数量

把为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等式方程的可满足性

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

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)。

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);

示例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);

访问过的放到尾部

4.LRU Cache的OJ

public class LRUCache extends  LinkedHashMap<Integer,Integer>{public int capacity;LRUCache(int capacity){//true基于访问顺序super(capacity,0.75f,true);this.capacity=capacity;}@Overridepublic Integer get(Object key) {return super.getOrDefault(key,-1);}@Overridepublic Integer put(Integer key, Integer value) {return super.put(key, value);}@Overrideprotected 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;}@Overridepublic 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;}
}