LeetCode-146. LRU 缓存

题目来源
146. LRU 缓存

LRU理论

LRU 是 Least Recently Used 的缩写，这种算法认为最近使用的数据是热门数据，下一次很大概率将会再次被使用。而最近很少被使用的数据，很大概率下一次不再用到。当缓存容量的满时候，优先淘汰最近很少使用的数据。

假设现在缓存内部数据如图所示：
这里我们将列表第一个节点称为头结点，最后一个节点为尾结点。(可以想象成队列)

当调用缓存获取 key=1 的数据，LRU 算法需要将 1 这个节点移动到头结点，其余节点不变

然后我们插入一个 key=8 节点，此时缓存容量到达上限，所以加入之前需要先删除数据。由于每次查询都会将数据移动到头结点，未被查询的数据就将会下沉到尾部节点，尾部的数据就可以认为是最少被访问的数据，所以删除尾结点的数据。

然后我们直接将数据添加到头结点。

这里总结一下 LRU 算法具体步骤：

• 新数据直接插入到列表头部
• 缓存数据被命中，将数据移动到列表头部
• 缓存已满的时候，移除列表尾部数据。

题目思路

实现本题的两种操作，需要用到一个哈希表和一个双向链表。

代码实现一

继承java自带的LinkedHashMap

class LRUCache extends LinkedHashMap<Integer,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.Entry<Integer, 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;} }HashMap<Integer,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);*/