leetcode-146.LRU缓存（易理解）

为了实现一个满足 LRU（最近最少使用）缓存约束的数据结构，我们需要在 (O(1)) 时间复杂度内完成 get 和 put 操作。这通常可以通过结合使用哈希表和双向链表来实现：

• 哈希表：用于在 (O(1)) 时间复杂度内实现对缓存中元素的快速访问。
• 双向链表：用于维护缓存中元素的顺序，以便在缓存容量超出限制时能够快速定位并移除最久未使用的元素。

以下是 LRUCache 类的实现：

import java.util.HashMap;
import java.util.Map;class LRUCache {private class Node {int key;int value;Node prev;Node next;Node(int key, int value) {this.key = key;this.value = value;}}private final int capacity;private final Map<Integer, Node> cache;private final Node head;private final Node tail;public LRUCache(int capacity) {this.capacity = capacity;this.cache = new HashMap<>();this.head = new Node(0, 0);this.tail = new Node(0, 0);head.next = tail;tail.prev = head;}public int get(int key) {Node node = cache.get(key);if (node == null) {return -1;}// Move the accessed node to the headmoveToHead(node);return node.value;}public void put(int key, int value) {Node node = cache.get(key);if (node == null) {// Create a new nodeNode newNode = new Node(key, value);cache.put(key, newNode);addNode(newNode);if (cache.size() > capacity) {// Pop the tailNode tail = popTail();cache.remove(tail.key);}} else {// Update the valuenode.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 = node.prev;Node next = node.next;prev.next = next;next.prev = prev;}private void moveToHead(Node node) {removeNode(node);addNode(node);}private Node popTail() {Node res = tail.prev;removeNode(res);return res;}public static void main(String[] args) {LRUCache lruCache = new LRUCache(2);lruCache.put(1, 1);lruCache.put(2, 2);System.out.println(lruCache.get(1)); // 返回 1lruCache.put(3, 3); // 该操作会使得关键字 2 作废System.out.println(lruCache.get(2)); // 返回 -1 (未找到)lruCache.put(4, 4); // 该操作会使得关键字 1 作废System.out.println(lruCache.get(1)); // 返回 -1 (未找到)System.out.println(lruCache.get(3)); // 返回 3System.out.println(lruCache.get(4)); // 返回 4}
}

解释

1. Node 类：用于表示双向链表中的节点，包含 key 和 value，以及前驱和后继节点的引用。
2. 构造函数：初始化缓存容量、哈希表、以及双向链表的头尾虚拟节点。
3. get 方法：检查缓存中是否存在指定键，若存在则将该节点移动到链表头部（表示最近使用），并返回其值；否则返回 -1。
4. put 方法：插入新键值对时，若键已存在则更新值并移动到链表头部；若键不存在则创建新节点并插入链表头部，若超出容量则移除链表尾部节点（最久未使用）。
5. 辅助方法：
   • addNode：在链表头部插入节点。
   • removeNode：从链表中移除节点。
   • moveToHead：将节点移动到链表头部。
   • popTail：移除并返回链表尾部节点。

这种设计确保了所有操作的平均时间复杂度为 (O(1))。