宠物网站建设的可行性,金华在线制作网站,集团公司网站 案例,网站网络营销公司目录LRU理论题目思路代码实现一代码实现二题目来源 146. LRU 缓存
LRU理论
LRU 是 Least Recently Used 的缩写#xff0c;这种算法认为最近使用的数据是热门数据#xff0c;下一次很大概率将会再次被使用。而最近很少被使用的数据#xff0c;很大概率下一次不再用到。当缓…
目录LRU理论题目思路代码实现一代码实现二题目来源 146. LRU 缓存
LRU理论
LRU 是 Least Recently Used 的缩写这种算法认为最近使用的数据是热门数据下一次很大概率将会再次被使用。而最近很少被使用的数据很大概率下一次不再用到。当缓存容量的满时候优先淘汰最近很少使用的数据。
假设现在缓存内部数据如图所示 这里我们将列表第一个节点称为头结点最后一个节点为尾结点。(可以想象成队列)
当调用缓存获取 key1 的数据LRU 算法需要将 1 这个节点移动到头结点其余节点不变
然后我们插入一个 key8 节点此时缓存容量到达上限所以加入之前需要先删除数据。由于每次查询都会将数据移动到头结点未被查询的数据就将会下沉到尾部节点尾部的数据就可以认为是最少被访问的数据所以删除尾结点的数据。 然后我们直接将数据添加到头结点。 这里总结一下 LRU 算法具体步骤
新数据直接插入到列表头部缓存数据被命中将数据移动到列表头部缓存已满的时候移除列表尾部数据。
题目思路
实现本题的两种操作需要用到一个哈希表和一个双向链表。
代码实现一
继承java自带的LinkedHashMap
class LRUCache extends LinkedHashMapInteger,Integer{private 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.EntryInteger, Integer eldest) {return size() capacity; }
}/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj new LRUCache(capacity);* int param_1 obj.get(key);* obj.put(key,value);*/代码实现二
class LRUCache {class Node{private int key,val;private Node pre,next;private Node(int k,int v){this.key k;this.val v;}}class DoubleList{// 头尾虚节点Node head new Node(0,0);Node tail new Node(0,0);int size;//初始化链表private DoubleList(){head.next tail;tail.pre head;size 0;}//头插入void addFirst(Node n){head.next.pre n;n.next head.next;n.pre head;head.next n;size;}//删除链表的某一个元素void remove(Node n){n.pre.next n.next;n.next.pre n.pre;size--;}//删除尾结点并返回该节点Node removeLast(){Node res tail.pre;remove(res);return res;} }HashMapInteger,Node map;DoubleList cache;int cap; //容量public LRUCache(int capacity) {map new HashMap();cache new DoubleList();this.cap capacity;}public int get(int key) {if(!map.containsKey(key)){ //该节点不存在return -1;}Node res map.get(key);cache.remove(res);cache.addFirst(res);return res.val;}public void put(int key, int value) {Node n new Node(key,value);if(map.containsKey(key)){ //若该节点已经存在cache.remove(map.get(key));}else if(map.size() cap){ //该节点不存在但是cache已满Node last cache.removeLast();map.remove(last.key);}cache.addFirst(n);map.put(key,n);}
}/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj new LRUCache(capacity);* int param_1 obj.get(key);* obj.put(key,value);*/
