题目链接
LRU 缓存
文章来源:https://www.toymoban.com/news/detail-573178.html
题目描述
文章来源地址https://www.toymoban.com/news/detail-573178.html
注意点
- 如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字
- 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行
解答思路
- 如果想以O(1)的速度进行get,则需要将对应的key、value存到map中
- 如果想以O(1)的速度进行put,又因为插入的时候可能由于空间已满需要将最久未使用的关键字,元素始终都在进行移动,所以需要使用链表来存储节点
- 如果使用map存储key、value,链表中每个节点存储key、value,则在get某个节点需要将其移动到链表头部时查找该节点需要花费O(n)的时间,不满足题意,所以应该map存储的key为对应关键字的key,而存储的value应该是该key对应的链表节点
代码
class LRUCache {
class DoublyLinkedList {
int key;
int value;
DoublyLinkedList prev;
DoublyLinkedList next;
DoublyLinkedList() {}
DoublyLinkedList(int key, int value) {
this.key = key;
this.value = value;
}
}
int size;
DoublyLinkedList head;
DoublyLinkedList tail;
Map<Integer, DoublyLinkedList> map;
public LRUCache(int capacity) {
size = capacity;
map = new HashMap<>(capacity);
head = new DoublyLinkedList();
tail = new DoublyLinkedList();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
DoublyLinkedList node = map.get(key);
if (node == null) {
return -1;
}
// 将该节点移动到链表头部
removeNode(node);
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
DoublyLinkedList node = new DoublyLinkedList(key, value);
// key在链表中已存在,只更新了value值,则直接对map进行更新即可,还要将新节点移动到链表头部
if (map.containsKey(key)) {
DoublyLinkedList oldNode = map.get(key);
removeNode(oldNode);
map.put(key, node);
moveToHead(node);
return;
}
// key在链表中不存在,且链表还有多余空间,则只需要将新节点插到链表头部
if (map.size() < size) {
moveToHead(node);
map.put(key, node);
} else {
// key在链表中不存在,且链表已满,则需要删除链表尾,同时将新节点插到链表头部
map.remove(tail.prev.key);
removeNode(tail.prev);
moveToHead(node);
map.put(key, node);
}
}
public void moveToHead(DoublyLinkedList node) {
DoublyLinkedList tmp = head.next;
head.next = node;
node.prev = head;
node.next = tmp;
tmp.prev = node;
}
public void removeNode(DoublyLinkedList node) {
DoublyLinkedList prevNode = node.prev;
DoublyLinkedList nextNode = node.next;
prevNode.next = nextNode;
nextNode.prev = prevNode;
}
}
关键点
- map中存储的value为key对应的链表中的节点
- 如果能成功get到值,则需要将该节点移动到链表的头部,移动时,还要删除链表中老位置的该节点
- 在put时,如果此时链表和map中已经有该关键字,只是更新其value值,则需要更新其在链表中的节点值,同时将该节点移动到链表同步;如果没有该关键字但是链表空间足够,则只需要建一个新节点插到链表头部即可;如果没有该关键字且链表空间已满,则需要将尾部节点删掉,再将新节点插入到头部
- 在增加和删除链表节点时同时也要对map中的相应值进行更新
到了这里,关于LRU 缓存的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!