关于java:设计数据结构实现一个-LRUCache

这是 LeetCode 上的 「146. LRU 缓存机制」，难度为 「中等」。

使用你所把握的数据结构，设计和实现一个 LRU (最近起码应用) 缓存机制。实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1。
void put(int key, int value) 如果关键字曾经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字 - 值」。当缓存容量达到下限时，它应该在写入新数据之前删除最久未应用的数据值，从而为新的数据值留出空间。

进阶：你是否能够在工夫复杂度内实现这两种操作？

示例：

 输出
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输入
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提醒：

1 <= capacity <= 3000
0 <= key <= 3000
0 <= value <=
最多调用 3 * 次 get 和 put

LRU 是一种非常常见的页面置换算法。

将 LRU 翻译成大白话就是：当不得不淘汰某些数据时（通常是容量已满），抉择最久未被应用的数据进行淘汰。

题目让咱们实现一个容量固定的 LRUCache。如果插入数据时，发现容器已满时，则先依照 LRU 规定淘汰一个数据，再将新数据插入，其中「插入」和「查问」都算作一次“应用”。

能够通过 🌰 来了解，假如咱们有容量为的 LRUCache 和测试键值对 [1-1,2-2,3-3]，将其依照程序进行插入 & 查问：

插入 1-1，此时最新的应用数据为 1-1
插入 2-2，此时最新应用数据变为 2-2
查问 1-1，此时最新应用数据为 1-1
插入 3-3，因为容器曾经达到容量，须要先淘汰已有数据能力插入，这时候会淘汰 2-2，3-3 成为最新应用数据

键值对存储方面，咱们能够应用「哈希表」来确保插入和查问的复杂度为。

另外咱们还须要额定保护一个「应用程序」序列。

咱们冀望当「新数据被插入」或「产生键值对查问」时，可能将以后键值对放到序列头部，这样当触发 LRU 淘汰时，只须要从序列尾部进行数据删除即可。

冀望在复杂度内调整某个节点在序列中的地位，很天然想到双向链表。

具体的，咱们应用哈希表来存储「键值对」，键值对的键作为哈希表的 Key，而哈希表的 Value 则应用咱们本人封装的 Node 类，Node 同时作为双向链表的节点。

插入：查看以后键值对是否曾经存在于哈希表：
没达到容量：插入哈希表，并将以后键值对所对应的 Node 节点调整到链表头部（refresh 操作）
已达到容量：先从链表尾部找到待删除元素进行删除（delete 操作），而后再插入哈希表，并将以后键值对所对应的 Node 节点调整到链表头部（refresh 操作）
如果存在，则更新键值对，并将以后键值对所对应的 Node 节点调整到链表头部（refresh 操作）
如果不存在，则查看哈希表容量是否曾经达到容量：
查问：如果没在哈希表中找到该 Key，间接返回；如果存在该 Key，则将对应的值返回，并将以后键值对所对应的 Node 节点调整到链表头部（refresh 操作）

一些细节：

为了缩小双向链表左右节点的「判空」操作，咱们事后建设两个「哨兵」节点 head 和 tail。

代码：

class LRUCache {
    class Node {
        int k, v;
        Node l, r;
        Node(int _k, int _v) {
            k = _k;
            v = _v;
        }
    }
    int n;
    Node head, tail;
    Map<Integer, Node> map;
    public LRUCache(int capacity) {
        n = capacity;
        map = new HashMap<>();
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.r = tail;
        tail.l = head;
    }
    
    public int get(int key) {if (map.containsKey(key)) {Node node = map.get(key);
            refresh(node);
            return node.v;
        } 
        return -1;
    }
    
    public void put(int key, int value) {
        Node node = null;
        if (map.containsKey(key)) {node = map.get(key);
            node.v = value;
        } else {if (map.size() == n) {
                Node del = tail.l;
                map.remove(del.k);
                delete(del);
            }
            node = new Node(key, value);
            map.put(key, node);
        }
        refresh(node);
    }
 
    // refresh 操作分两步：// 1. 先将以后节点从双向链表中删除（如果该节点自身存在于双向链表中的话）// 2. 将以后节点增加到双向链表头部
    void refresh(Node node) {delete(node);
        node.r = head.r;
        node.l = head;
        head.r.l = node;
        head.r = node;
    }
 
    // delete 操作：将以后节点从双向链表中移除
    // 因为咱们事后建设 head 和 tail 两位哨兵，因而如果 node.l 不为空，则代表了 node 自身存在于双向链表（不是新节点）void delete(Node node) {if (node.l != null) {
            Node left = node.l;
            left.r = node.r;
            node.r.l = left;
        }
    }
}

工夫复杂度：各操作均为
空间复杂度：

这是咱们「刷穿 LeetCode」系列文章的第 No.146 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先将所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

关于java:设计数据结构实现一个-LRUCache

题目形容

根本剖析

双向链表

最初