题目概览请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。实现LRUCache类LRUCache(int capacity)以正整数作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中则返回关键字的值否则返回-1。void put(int key, int value)如果关键字key已经存在则变更其数据值value如果不存在则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity则应该逐出最久未使用的关键字。函数get和put必须以O(1)的平均时间复杂度运行。示例输入[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); // 缓存是 {11} lRUCache.put(2, 2); // 缓存是 {11, 22} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废缓存是 {11, 33} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废缓存是 {44, 33} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4提示1 capacity 30000 key 100000 value 10^5最多调用2 * 10^5次get和put来源146. LRU 缓存 - 力扣LeetCode解题分析方法哈希 双向链表值的获取和添加可以直接用哈希集合重点在于逐出最久未使用的关键字我们可以定义一个双向链表当有值被 get 或 put 时在头部进行添加当关键字数大于capacity时获取尾部的关键字进行移除。时间复杂度O(1)空间复杂度O(n)class LRUCache { class Node { private int key; private int val; private Node pre; private Node next; public Node(int key, int val) { this.key key; this.val val; pre new Node(); next new Node(); } public Node() { } public void setVal(int val) { this.val val; } } private MapInteger, Node MAP; private Node head, tail; private int capacity; public LRUCache(int capacity) { this.capacity capacity; MAP new HashMap(); head new Node(); tail new Node(); head.next tail; tail.pre head; } public int get(int key) { Node node MAP.get(key); if (node ! null) { moveToFirst(node); return node.val; } return -1; } private void moveToFirst(Node node) { if (head.next node) { return; } node.pre.next node.next; node.next.pre node.pre; Node temp head.next; head.next node; node.pre head; node.next temp; temp.pre node; } private Node removeLast() { Node node tail.pre; node.pre.next tail; tail.pre node.pre; return node; } public void put(int key, int value) { Node node MAP.get(key); if (node ! null) { node.setVal(value); MAP.put(key, node); moveToFirst(node); return; } if (MAP.size() capacity) { node removeLast(); MAP.remove(node.key); } node new Node(key, value); moveToFirst(node); MAP.put(key, node); } } /** * 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); */