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里面没有这个keyif (!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里有这个keyelse {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);*/