题目描述：
请你设计并实现一个满足 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) 的平均时间复杂度运行。
数据范围：
$ 1\le capacity \le 3000 $
最多调用 $ 2\times 10^5 $ 次 get 和 put
题解：
get 和 put 全需要 $ O(1) $ 的复杂度。并且 get和put 之后需要更新年龄。因此可以选择使用链表，但是为了删除和插入比较方便需要使用双向链表。同时使用虚拟头结点和虚拟尾节点构造。head->next = tail, head->pre = nullptr, tail->pre = head, tail->next = nullptr
get 和 put 之后将节点移动到末尾。超过容量时将头部结点删除。同时使用一个哈希表存 key 和链表节点的映射关系。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
| class LRUCache
{
public:
struct ListNode
{
ListNode *pre;
ListNode *next;
int key;
int val;
};
int cap;
int length;
unordered_map<int, ListNode *> mp;
ListNode *head;
ListNode *tail;
LRUCache(int capacity)
{
head = new ListNode;
tail = new ListNode;
head->next = tail;
head->val = 0;
tail->pre = head;
tail->val = 0;
head->pre = nullptr;
tail->next = nullptr;
cap = capacity;
length = 0;
}
int get(int key)
{
if (mp.count(key))
{
ListNode *p = mp[key];
erase(p);
insert(p);
return p->val;
}
else
return -1;
}
void insert(ListNode *p)
{
if (p == nullptr)
return;
if (length == cap)
{
ListNode *t = head->next;
erase(t);
delete t;
}
mp[p->key] = p;
length++;
p->next = tail;
p->pre = tail->pre;
tail->pre->next = p;
tail->pre = p;
}
void erase(ListNode *p)
{
if (p == tail || p == head)
return;
mp.erase(p->key);
length--;
p->pre->next = p->next;
p->next->pre = p->pre;
}
void put(int key, int value)
{
if (mp.count(key))
{
ListNode *p = mp[key];
p->val = value;
erase(p);
insert(p);
}
else
{
ListNode *p = new ListNode;
p->val = value;
p->key = key;
insert(p);
}
}
};
|