Leetcode146-LRU缓存的java实现 Leetcode146-LRU缓存的java实现

接触到的一个题目，原题应该是在leetcode。LRU简单按意思来说就是符合最近最少使用的一个队列。我们首先的理解来说，LRU缓存需要几个核心的定义。1. 容量 2. 容器 3. 操作 4. 语义。首先，容量，定义这个LRU队列的长度。而容器是底层采用什么样的数据结构来存储。因为要保证不重复，首先会想到Hash，而且应该是K-V的形式，Java相关有HashMap。对于操作来说，一个队列，需要有入队和出队，以及初始化的操作，即需要get(), set()等方法。最后一个语义，就是LRU的核心，如何去保证符合最近最少使用。按要求，需要把最近最少使用的放到队尾，最近最新使用的放到队头，引申即需要设置一个头，尾的单独标记，以及操作setHead。注意setHead是整个的难点，要详尽的考虑当前节点是否头节点，是否中间节点，是否尾节点等各种情况，操作实际内容需要是双向链表的形式，设计的核心是考虑各种异常和特殊情况。最初的版本无法通过，目前修改到Accepted，依然有些优化空间，注释有简单思路的介绍，同时代码中包括了默认的几个Case。
以下是代码：

import java.util.HashMap; /** Created by igoso on 18-1-8. case 1 ["LRUCache","put","put","get","put","put","get"] [[2],[2,1],[2,2],[2],[1,1],[4,1],[2]] -- [null,null,null,2,null,null,-1] case 2 ["LRUCache","put","put","put","put","get","get","get","get","put","get","get","get","get","get"] [[3],[1,1],[2,2],[3,3],[4,4],[4],[3],[2],[1],[5,5],[1],[2],[3],[4],[5]] -- [null,null,null,null,null,4,3,2,-1,null,-1,2,3,-1,5] */ public class LRUCacheDemo { public static void main(String[] args) { LRUCache cache = new LRUCache(2 /* capacity */); /** default case **/ //cache.put(1,1); //cache.put(2,2); //cache.put(3,3); //cache.put(4,4); //cache.get(4); //cache.get(3); //cache.get(2); //cache.get(1); //cache.put(5, 5); //cache.get(1); //cache.get(2); //cache.get(3); //cache.get(4); //cache.get(5); /** case 1**/ //cache.put(1, 1); //cache.put(2, 2); //cache.get(1); // returns 1 //cache.put(3, 3); // evicts key 2 //cache.get(2); // returns -1 (not found) //cache.put(4, 4); // evicts key 1 //cache.get(1); // returns -1 (not found) //cache.get(3); // returns 3 //cache.get(4); // returns 4/** case 2 **/ cache.put(2,1); cache.put(2,2); cache.get(2); cache.put(1,1); cache.put(4,1); cache.get(2); } }class LRUCache { private class Node { int key; int value; Node pre; Node next; public Node(int key, int value) { this.key = key; this.value = https://www.it610.com/article/value; }@Override public String toString() { return"[" + key + "," + value + "]"; } }private int capacity; private HashMap map = new HashMap<>(); private Node head = null; private Node tail = null; public LRUCache(int capacity) { this.capacity = capacity; }public int get(int key) { if (map.containsKey(key)) { Node n = map.get(key); setHead(n,false); return n.value; }return -1; }private void remove(Node node) { //是头节点 if (node.pre != null) { node.pre.next = node.next; } else { head = node.next; }//是否尾节点 if (node.next != null) { node.next.pre = node.pre; } else { tail = node.pre; }//貌似与上面条件重复,可以删除 if (node == tail) { tail = tail.pre; } }private void setHead(Node n, boolean isNew) { //如果是头，直接返回 if (head == n) { return; }//是否插入,注意在put的时候有remove 也算新节点 if (isNew) { n.next = head; n.pre = null; if (head != null) { head.pre = n; }head = n; if (tail == null) { tail = head; }if (tail == head && head.next != null) { tail = head.next; tail.next = null; } return; }//非新插入头，只修改头指针 //是尾节点 if (n.next == null) { tail = n.pre; tail.next = null; head.pre = n; //记得给原先头节点的前驱赋当前值 n.next = head; //设置新的头节点 head = n; head.pre = null; }else { //非尾节点 head.pre = n; //记得给原先头节点的前驱赋当前值 n.next.pre = n.pre; n.pre.next = n.next; n.next = head; head = n; head.pre = null; } }public void put(int key, int value) { //已经存在 //先删除，再设置为头 if (map.containsKey(key)) { Node old = map.get(key); old.value = https://www.it610.com/article/value; remove(old); setHead(old,true); } else { //不存在新建，包括设置新头和删除溢出节点 Node created = new Node(key, value); if (map.size()>= capacity) { map.remove(tail.key); remove(tail); setHead(created,true); } else { setHead(created,true); } map.put(key, created); } }@Override public String toString() { return this.map.toString(); } }

【Leetcode146-LRU缓存的java实现】以上，相对来说还是比较复杂的，以下是简单的图解，核心是对头节点和尾节点的操作和标记，每个都有双向的指针。注意头指针和尾指针的特性，头的前驱为空，尾的后驱为空，以及只有一个元素，或者两个元素的情况。
更简单的解法看这篇文章：https://www.jianshu.com/p/c7adab253186