本文主要是介绍LeetCode刷题之HOT100之LRU缓存,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
2024/6/21 酷暑难耐,离开空调我将不知道能否《活着》,昨天跑步感觉全身的热无法排出去,出门那种热浪一阵一阵打过来,一点风都舍不得给我。早早的来到实验室,也没多早,九点哈哈,做题啦!
1、题目描述
2、逻辑分析
刚看到这个题目,我看了好久,看不懂啥意思,然后去看了题解以及代码,打算跳过这题的想法在脑海里飘过三四次,好长啊代码。但是我还是看完了,就是一个redis
缓存思想。该算法使用了哈希表和双链表的数据结构。LRUCache
的大致思路是使用哈希表(如 HashMap
)和双链表(Doubly Linked List
)来实现一个最近最少使用(Least Recently Used, LRU
)缓存机制。
具体思路如下:
数据结构:
使用 HashMap
来存储键值对(key-value pairs
),其中 key
是缓存项的键,value
是对应的缓存值以及该值在双链表中的节点引用。
使用双链表来维护缓存项的访问顺序。最近访问的项位于链表的头部,而最久未访问的项位于链表的尾部。
初始化:
创建一个空的双链表,包含头节点(head
)和尾节点(tail
),它们互相指向对方,形成一个循环链表。
初始化 HashMap
用于存储键值对。
get(key) 操作:
在 HashMap
中查找键(key
)对应的节点。
如果节点存在(即该键在缓存中),则将该节点从当前位置删除,并重新插入到链表的头部,以表示该键最近被访问过。
返回该节点的值。
如果节点不存在,则返回 -1 表示未找到。
put(key, value) 操作:
在 HashMap
中查找键(key
)对应的节点。
如果节点存在(即该键已经在缓存中),则更新该节点的值为新的 value
,并将该节点从当前位置删除,重新插入到链表的头部。
如果节点不存在(即该键不在缓存中),则需要创建一个新节点,将新节点插入到链表的头部,并在 HashMap
中添加键值对。
如果此时缓存已满(即缓存中元素的数量超过了设定的容量),则需要删除链表尾部的节点,并在 HashMap
中移除对应的键值对,以腾出空间。
维护双链表:
当有新节点插入到链表的头部时,需要更新头节点和新节点的 prev
和 next
指针。
当有节点从链表中删除时,需要更新该节点的前一个节点和后一个节点的 prev
和 next
指针。
通过这种方式,LRU 缓存能够快速地访问最近使用过的数据,并在必要时淘汰最久未使用的数据,从而保持缓存的有效性。
3、代码演示
public class LRUCache {// 双链表节点类class DLinkedNode {int key;int value;DLinkedNode prev;DLinkedNode next;// 构造无参数的DLinkedNode实例(通常用于初始化头尾节点)public DLinkedNode(){}// 构造带有key和value的DLinkedNode实例public DLinkedNode(int _key, int _value){key = _key; value = _value;}}// 使用HashMap存储key到DLinkedNode的映射private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();// 当前缓存中元素的数量 private int size;// 缓存的最大容量private int capacity;// 双链表的头尾节点,用于维护最近最少使用(LRU)顺序private DLinkedNode head, tail;// 构造函数,初始化LRUCachepublic LRUCache(int capacity) {this.size = 0;this.capacity = capacity;// 初始化头尾节点,它们之间互相指向,构成一个空链表head = new DLinkedNode();tail = new DLinkedNode();head.next = tail;tail.prev = head;}// 根据key获取缓存值public int get(int key) {DLinkedNode node = cache.get(key);// 如果节点不存在,返回-1 if(node == null){return -1;}// 节点存在,将访问过的节点移动到头部moveToHead(node);// 返回节点的值return node.value;}// 将key-value对放入缓存public void put(int key, int value) {DLinkedNode node = cache.get(key);// 如果节点不存在,创建一个新的节点并放入缓存if(node == null){DLinkedNode newNode = new DLinkedNode(key, value);cache.put(key, newNode);// 将新节点添加到头部addToHead(newNode);// 缓存元素数量加1size++;// 如果超过容量,删除尾部的节点if(size > capacity){DLinkedNode tail = removeTail();// 从HashMap中移除该节点 cache.remove(tail.key);// 缓存元素数量减1size--;}// 如果节点已存在,更新节点的值并移动到头部}else{node.value = value;moveToHead(node);}}// 将节点添加到双链表的头部private void addToHead(DLinkedNode node){node.prev = head;node.next = head.next;head.next.prev = node;head.next = node;}// 从双链表中移除一个节点private void removeNode(DLinkedNode node){node.prev.next = node.next;node.next.prev = node.prev;}// 将一个节点从当前位置移动到双链表的头部private void moveToHead(DLinkedNode node){removeNode(node);addToHead(node);}// 移除并返回双链表的尾部节点private DLinkedNode removeTail(){DLinkedNode res = tail.prev;removeNode(res);return res;}
}
4、复杂度分析
- 时间复杂度:
O(1)
。get和put都只需要O(1)的时间。 - 空间复杂度:
O(capacity)
。capacity为最大缓存容量。
拜拜啦,我知道这题下次见到还是不能完整敲出来滴,那就希望下下次可以叭,再见!
这篇关于LeetCode刷题之HOT100之LRU缓存的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!