当前位置：首页 > news >正文

【Leetcode Top 100】146. LRU 缓存

news 来源：原创 2025/1/17 23:59:53

问题背景

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。
实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 $c a p a c i t y$ 初始化 LRU 缓存
int get(int key) 如果关键字 $k ey$ 存在于缓存中，则返回关键字的值，否则返回 $- 1$ 。
void put(int key, int value) 如果关键字 $k ey$ 已经存在，则变更其数据值 $v a l u e$ ；如果不存在，则向缓存中插入该组 $k ey - v a l u e$ 。如果插入操作导致关键字数量超过 $c a p a c i t y$ ，则应该逐出最久未使用的关键字。
函数 get 和 put 必须以 $O (1)$ 的平均时间复杂度运行。

数据约束

$\le capacity \le 3000$
$\le key \le 10000$
$\le value \le 10 ^ 5$
最多调用 $\le 10 ^ 5$ 次 get 和 put

解题过程

数据结构设计题，以积累记忆为主。
LRU 是一种典型的页面淘汰策略，显然增删改的操作频率是比较高的，这应该用链表处理。这样一来，加入新页面的操作可以看作在链表头部插入，淘汰旧页面的操作可以看作删除链表的尾节点。
为了方便找到链表的尾节点，可以选择实现一个头尾循环的双向链表结构，这样一来，统一的头节点 $d u mm y$ 的前一个节点就是尾节点。注意区别于一般的循环链表，这里双向链表是强调头尾节点的，而一般的循环链表最大的特征就是无所谓头尾，给定任意一个节点即可遍历整个链表。
还有一个问题，如果某个数据项已经存在，要求更新它的值和频率，也就是要将它的值更改为给定的新值并把这个节点移动到链表头部。但是在链表中按值查找的时间复杂度是 $O (N)$ 量级的，不符合题目要求。为此，需要再引入查询效率为 $O (1)$ 的哈希表。
综合来看，所有操作的时间复杂度是 $O (1)$ ，需要 $O (min (p u t, c a p a c i t y))$ 的额外空间（可能出现记录的页面数量少，没有达到过 $c a p a c i t y$ 的情况）。

具体实现

class LRUCache {// 自定义双向链表private static class ListNode {int key, value;ListNode pre, next;ListNode(int key, int value) {this.key = key;this.value = value;}}private final int capacity;private final ListNode dummy = new ListNode(0, 0);private final Map<Integer, ListNode> map = new HashMap<>();// 初始状态下头节点的前后指针指向自己public LRUCache(int capacity) {this.capacity = capacity;dummy.pre = dummy;dummy.next = dummy;}// 自己实现的方法一：双向链表的头插法private void pushFront(ListNode node) {node.pre = dummy; // 新节点的前驱是头节点node.next = dummy.next; // 新节点的后继是之前头节点的后继node.pre.next = node; // 新节点的前驱（就是头节点）的后继是新节点node.next.pre = node; // 新节点的后继的前驱是新节点}// 自己实现的方法二：双向链表中删除某个节点private void remove(ListNode node) {node.pre.next = node.next; // 当前节点前驱的后继是当前节点的后继node.next.pre = node.pre; // 当前节点后继的前驱是当前节点的前驱}// 自己实现的方法三：从哈希表中获取某个键对应的链表节点private ListNode getNode(int key) {// 该节点不存在则返回空if(!map.containsKey(key)) {return null;}// 存在则取出该节点，先删除，再从链表头部插入ListNode node = map.get(key);remove(node);pushFront(node);return node;}public void put(int key, int value) {// 根据相应的键取数据项，若存在则更新它的值ListNode node = getNode(key);if(node != null) {node.value = value;return;}// 若相应的数据项不存在，那么新建节点，更新哈希表并从链表头部插入node = new ListNode(key, value);map.put(key, node);pushFront(node);// 维护的页面数量超过规定值，进行淘汰if(map.size() > capacity) {// 头节点的前驱就是要淘汰的尾节点ListNode leastUsed = dummy.pre;// 从哈希表和链表中移除map.remove(leastUsed.key);remove(leastUsed);}}public int get(int key) {ListNode node = getNode(key);return node != null ? node.value : -1;}
}/*** 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);*/

问题背景

数据约束

解题过程

具体实现

相关文章：