【LeetCode】【算法】146. LRU缓存
LeetCode - 146.LRU缓存
题目描述
请你设计并实现一个满足 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) 的平均时间复杂度运行。
实现思路
LRU本质就是通过一个队列实现的，对于put函数和get函数，最特别的地方在于访问时需要将访问的节点挪到队尾。
- 创建ListNode以实现节点。其中包含
int key,int value,ListNode next,ListNode prev（双向指针的实现） - 在LRU类中的属性包括：
I. 虚拟头尾节点ListNode dummyHead, dummyTail;
II. HashMap用于以O(1)平均复杂度访问到目标节点Map<Integer, ListNode> map;（如果需要遍历整个链表来找目标节点，就不是O(1)的复杂度了）
III.int capacity表示链表的容量，这是题目需要指定的
IV.int listLen用于记录当前链表的长度 - 初始化LRU类，就是对上面的这些属性做一个初始化，记得虚拟头尾节点的
next属性和prev属性需要相连 - put方法思路：
I. 使用map来检查这个节点是否在链表中；
① 如果在链表中，则通过map得到这个节点，将该节点从链表中删除，并给改节点赋予新的值；
② 如果不在链表中，又分为listLen>=capacity和listLen<capacity的情况（也就是链表容量是否超过指定容量了）
情况1：链表当前容量已经达到了指定容量，需要删除最久未访问节点（队头），使用虚拟头结点dummyHead来做删除；根据给定的key和value新建一个节点
情况2：链表当前容量未达到指定容量，则链表长度++，根据给定的key和value新建一个节点
II. 利用dummyTail将该节点放到链表的最后，并更新map中的内容 - get方法思路：
I. 使用map来检查这个节点是否在链表中，不在返回-1；
II. 否则利用map来拿到这个节点，将它从链表中移除；并利用dummyTail将该节点放到链表最后，返回该节点的值
实现代码
class LRUCache {
class ListNode{
int key;
int value;
ListNode next;
ListNode prev;
public ListNode() {
}
public ListNode(int key, int value) {
this.key = key;
this.value = value;
}
}
ListNode dummyHead;
ListNode dummyTail;
Map<Integer, ListNode> map;
int capacity;
int listLen;
public LRUCache(int capacity) {
map = new HashMap<>();
dummyHead = new ListNode();
dummyTail = new ListNode();
dummyHead.next = dummyTail;
dummyTail.prev = dummyHead;
this.capacity = capacity;
this.listLen = 0;
}
public void put(int key, int value) {
ListNode listNode = null;
// 如果map里面没有这个key
if (!map.containsKey(key)){
// 如果长度已经满了，就移除一个
if (listLen >= capacity){
ListNode removeNode = dummyHead.next;
removeNode.next.prev = removeNode.prev;
removeNode.prev.next = removeNode.next;
map.remove(removeNode.key);
} else {
listLen++;
}
// 新增一个
listNode = new ListNode(key, value);
}
// 如果map里有这个key
else {
listNode = map.get(key);
// 把这个listNode从链表上删除
ListNode prev_node = listNode.prev;
ListNode next_node = listNode.next;
prev_node.next = next_node;
next_node.prev = prev_node;
listNode.value = value;
}
// 把这个listNode弄到后面去
ListNode insertPre = dummyTail.prev;
insertPre.next = listNode;
listNode.prev = insertPre;
listNode.next = dummyTail;
dummyTail.prev = listNode;
map.put(key, listNode);
}
public int get(int key) {
if (!map.containsKey(key)){
return -1;
} else {
int result = map.get(key).value;
// 拿到这个Node，移除它
ListNode listNode = map.get(key);
// 把这个listNode从链表上删除
ListNode prev_node = listNode.prev;
ListNode next_node = listNode.next;
prev_node.next = next_node;
next_node.prev = prev_node;
// 把这个listNode弄到后面去
ListNode insertPre = dummyTail.prev;
insertPre.next = listNode;
listNode.prev = insertPre;
listNode.next = dummyTail;
dummyTail.prev = listNode;
map.put(key, listNode);
return result;
}
}
}
/**
* 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);
*/