题目描述

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

实现 LRUCache 类:

  • LRUCache(int capacity)正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1
  • void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。

函数 getput 必须以 O(1) 的平均时间复杂度运行。

输入输出

1
2
3
4
5
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

代码

c++版

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

struct DLinkedNode {
int key, value;
DLinkedNode* prev;
DLinkedNode* next;
DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr){}; // 构造函数
DLinkedNode(int k, int v): key(k), value(v), prev(nullptr), next(nullptr){};

};

class LRUCache {

private:
unordered_map<int, DLinkedNode*> mp; // 哈希表
DLinkedNode *head, *tail; // 头尾节点
int size, capacity; // 链表长度,链表最大容量

public:
LRUCache(int capacity) {
size = 0;
this->capacity = capacity;
head = new DLinkedNode(); // 创建头尾节点
tail = new DLinkedNode();
head->next = tail;
tail->prev = head;
}

int get(int key) {
// 若不存在返回-1
if(mp.count(key) == 0) return -1;

// 若存在返回值, 并且移动到链表头部
DLinkedNode *node = mp[key];
moveToHead(node); // 移动到链表头

return node->value;
}

void put(int key, int value) {
// 如果存在,修改值并且移动到链表头
if (mp.count(key) == 1) {
mp[key]->value = value;
moveToHead(mp[key]);
}else{ // 不存在,检查容量,容量满足不删除,容量不满足删除
// 创建节点
DLinkedNode *node = new DLinkedNode(key, value);
mp[key] = node; // 加入mp
addHead(node);
size ++;
if(size > capacity) {
size--;
moveTail();
}
}

}

// 移动到头结点
void moveToHead(DLinkedNode *node){
moveNode(node);
addHead(node);
}
void moveNode(DLinkedNode *node){
node->prev->next = node->next; // x->y->z变为x->z
node->next->prev = node->prev; // x<-y<-z变为x<-z
}
// 添加节点到头结点
void addHead(DLinkedNode *node){
node->next = head->next;
node->next->prev = node;
node->prev = head;
head->next = node;
}
// 删除尾节点
void moveTail(){
DLinkedNode *node = tail->prev; // 尾节点
mp.erase(node->key);
moveNode(node);
delete node;
}
};

/**
* 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);
*/

go语言版

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
89
90
91
92

type DLinkedNode struct{
key, value int
prev, next *DLinkedNode
}

type LRUCache struct {
size, capacity int
head, tail *DLinkedNode
mp map[int]*DLinkedNode
}

func initDL(key int, value int) *DLinkedNode{
return &DLinkedNode{
key: key,
value: value,
}
}

func Constructor(capacity int) LRUCache {
l := LRUCache{
size: 0,
capacity: capacity,
head: initDL(0, 0),
tail: initDL(0, 0),
mp: map[int]*DLinkedNode{},
}
l.head.next = l.tail
l.tail.prev = l.head
return l
}


func (this *LRUCache) Get(key int) int {

// 不存在
if _, k := this.mp[key]; !k{
return -1
}
// 存在
node := this.mp[key]
this.moveToHead(node)
return node.value
}


func (this *LRUCache) Put(key int, value int) {
if _, k := this.mp[key]; k { // 存在
node := this.mp[key]
node.value = value
this.moveToHead(node)
}else{ // 不存在
node := initDL(key, value)
this.mp[key] = node
this.addHead(node)
this.size++
if this.size > this.capacity {
this.moveTail()
this.size--
}
}
}

// 移动到头结点
func (this *LRUCache) moveToHead(node *DLinkedNode){
this.moveNode(node);
this.addHead(node);
}
func (this *LRUCache) moveNode(node *DLinkedNode){
node.prev.next = node.next; // x->y->z变为x->z
node.next.prev = node.prev; // x<-y<-z变为x<-z
}
// 添加节点到头结点
func (this *LRUCache) addHead(node *DLinkedNode){
node.next = this.head.next;
node.next.prev = node;
node.prev = this.head;
this.head.next = node;
}
// 删除尾节点
func (this *LRUCache) moveTail(){
node := this.tail.prev; // 尾节点
delete(this.mp, node.key)
this.moveNode(node);
}

/**
* Your LRUCache object will be instantiated and called as such:
* obj := Constructor(capacity);
* param_1 := obj.Get(key);
* obj.Put(key,value);
*/