响应式网站建设品牌全网天下,无法解析您网站的域名.,免费网站维护,网站多条件筛选 html题目链接
LRU 缓存
题目描述 注意点
如果插入操作导致关键字数量超过 capacity #xff0c;则应该 逐出 最久未使用的关键字函数 get 和 put 必须以 O(1) 的平均时间复杂度运行
解答思路
如果想以O(1)的速度进行get#xff0c;则需要将对应的key、value存到map中如果想…题目链接
LRU 缓存
题目描述 注意点
如果插入操作导致关键字数量超过 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;MapInteger, 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中的相应值进行更新
