请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。
这是一道大厂面试高频出现的算法题，难度为⭐️⭐️⭐️，属于中等，老铁们来一起看看这个题该怎么解？
1. 原题再现
没有废话，翠花，上酸菜！
2. 具体实现
为了实现一个满足 LRU （最近最少使用）缓存约束的数据结构，我们需要一个能够快速访问、更新和删除的数据结构，V 哥想到了用哈希表，因为哈希表提供了快速的查找能力，但是它不能保持元素的顺序；而双向链表可以保持元素的顺序，并且可以在 O(1) 时间复杂度内进行插入和删除操作。因此， V哥采用结合使用哈希表和双向链表来实现LRU缓存。
以下是 Java 代码实现：
import java.util.HashMap;
class Node {
int key;
int value;
Node prev;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
public class LRUCache {
private HashMap<Integer, Node> cache;
private Node head, tail;
private int capacity;
private int count;
public LRUCache(int capacity) {
this.capacity = capacity;
this.cache = new HashMap<>();
this.head = new Node(0, 0);
this.tail = new Node(0, 0);
this.head.next = this.tail;
this.tail.prev = this.head;
this.count = 0;
}
public int get(int key) {
Node node = cache.get(key);
if (node == null) {
return -1;
}
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
Node node = cache.get(key);
if (node == null) {
Node newNode = new Node(key, value);
cache.put(key, newNode);
addNode(newNode);
count++;
if (count > capacity) {
Node toDel = popTail();
cache.remove(toDel.key);
count--;
}
} else {
node.value = value;
moveToHead(node);
}
}
private void addNode(Node node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void moveToHead(Node node) {
removeNode(node);
addNode(node);
}
private Node popTail() {
Node res = tail.prev;
removeNode(res);
return res;
}
}
使用示例：
public class Main {
public static void main(String[] args) {
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
System.out.println(lRUCache.get(1)); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
System.out.println(lRUCache.get(2)); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
System.out.println(lRUCache.get(1)); // 返回 -1 (未找到)
System.out.println(lRUCache.get(3)); // 返回 3
System.out.println(lRUCache.get(4)); // 返回 4
}
}
输出结果应该与题目中的示例输出一致。这个实现使用了哈希表来快速查找节点，同时使用双向链表来维护节点的顺序和实现快速插入和删除操作。这样，我们就可以在 O(1) 的时间复杂度内完成 get 和 put 操作。
实现过程和步骤如下：
- 定义一个 Node 类，用于双向链表的节点，包含 key、value 以及前驱和后继节点的引用。
- 在 LRUCache 类中，定义一个 capacity 表示缓存的最大容量，一个 count 表示当前缓存中的节点数量，一个 cache 哈希表用于存储键和节点的映射，以及 head 和 tail 虚拟节点用于简化双向链表的操作。
- 实现 get 方法，首先在哈希表中查找键对应的节点，如果节点不存在，返回 -1。如果节点存在，则将该节点移动到链表的头部，表示最近被使用，然后返回节点的值。
- 实现 put 方法，如果键在哈希表中不存在，创建一个新的节点，并将其添加到链表的头部，同时添加到哈希表中。如果插入后节点数量超过了容量，则需要移除链表尾部的节点，并从哈希表中删除对应的条目。如果键已经存在，则更新对应的节点值，并将其移动到链表头部。
- addNode 方法用于将节点添加到链表头部，removeNode 方法用于从链表中移除节点，moveToHead 方法用于将节点移动到链表头部，popTail 方法用于移除链表尾部的节点。
- 在 Main 类的 main 方法中，我们创建了一个 LRUCache 实例，并执行了一系列的 put 和 get 操作来演示其功能。
V哥认为这个实现确保了 get 和 put 操作的平均时间复杂度为O(1)。get 操作直接通过哈希表查找节点，而 put 操作中，无论是更新现有节点还是添加新节点，都涉及到对双向链表的操作，这些操作的时间复杂度都是 O(1)。当缓存达到容量上限时，put 操作会移除最久未使用的节点，这也是 O(1) 时间复杂度的操作。
3. 小结一下
V哥的这个实现的关键在于维护一个双向链表，它可以帮助我们快速地访问、更新和删除最近最少使用的节点，同时使用哈希表来提供快速的查找能力。这样，我们就可以在 O(1) 的时间复杂度内完成所有的缓存操作。哈哈干净利索，回答完毕。
