Problem: 146. LRU 缓存
思路
使用一个双向链表来维护缓存的访问顺序，最近使用的节点在链表头部，最久未使用的节点在链表尾部。
使用一个哈希表来存储缓存中的键值对，哈希表中的键对应双向链表中的节点。
解题方法
Node类：
表示双向链表的节点，每个节点包含一个键值对以及指向前后节点的指针。
LRUCache类：
包含一个capacity表示缓存容量，map是哈希表，用于O(1)时间复杂度的查找，head和tail是虚拟头尾节点，用于方便地操作双向链表。
构造函数：
初始化缓存容量，创建一个空的哈希表，初始化双向链表的虚拟头尾节点并将它们互相连接。
get方法：
如果键存在于缓存中，则将对应的节点移动到双向链表的头部并返回节点的值。
如果键不存在，返回-1。
put方法：
如果键已经存在，先移除对应的节点。
如果缓存已满，移除双向链表尾部的节点（最久未使用的节点）。
插入新的节点到双向链表的头部。
remove方法：
从双向链表和哈希表中移除节点。
insert方法：
将新节点插入到双向链表的头部并更新哈希表。
复杂度
时间复杂度:
添加时间复杂度, 示例： O(n)O(n)O(n)
空间复杂度:
添加空间复杂度, 示例： O(n)O(n)O(n)
Code
Java
class LRUCache {
class Node{
int key, value;
Node prev;
Node next;
Node(int key, int value){
this.key = key;
this.value = value;
}
}
private int capacity; //容量
private Map<Integer, Node> map ;//存放关键字key及结点
Node head, tail;
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>();
this.head = new Node(0,0);
this.tail = new Node(0,0);
head.next = tail;
tail.prev = head;
}
/**
* 把key存到map里，并更新链表数据，key放在链表头
* @param key
* @return
*/
public int get(int key) {
if(map.containsKey(key)){
Node keyNode = map.get(key);
remove(keyNode);
insert(keyNode);
return keyNode.value;
} else {
return -1;
}
}
/**
* 移除结点
* @param node
*/
public void remove(Node node){
map.remove(node.key);
node.prev.next = node.next;
node.next.prev = node.prev;
}
public void insert(Node node){
map.put(node.key, node);
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
public void put(int key, int value) {
if(map.containsKey(key)){
remove(map.get(key));
}
if(map.size() >= capacity){
remove(tail.prev);
}
insert(new Node(key, value));
}
}
/**
* 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);
*/效果
