题目形容

这是 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);    // 返回 1lRUCache.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);    // 返回 3lRUCache.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 原题链接和其余优选题解。