[LeetCode] 146.LRU缓存机制(LRU Cache)

题目描述

运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put

获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
写入数据 put(key, value) - 如果密钥已经存在,则变更其数据值;如果密钥不存在,则插入该组「密钥/数据值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作?

示例:

LRUCache cache = new LRUCache( 2 / 缓存容量 / );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4

解题思路

通过哈希表和双向链表来实现。哈希表用于存储目前还在缓存中的数据,双向链表用于存储数据被访问的顺序。若某数据被访问,则将该数据对应的节点移动至链表头部,若超过了缓存容量,则将链表尾部的节点以及哈希表中的数据删除。

代码

OrderedDict

Python 语言中,有一种结合了哈希表与双向链表的数据结构 OrderedDict,只需要短短的几行代码就可以完成本题。

Python 3.6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class LRUCache:

def __init__(self, capacity: int):
self.capacity = capacity
self.data = collections.OrderedDict()

def get(self, key: int) -> int:
if key not in self.data:
return -1
self.data.move_to_end(key)
return self.data[key]

def put(self, key: int, value: int) -> None:
if key in self.data:
self.data.move_to_end(key)
self.data[key] = value
if len(self.data) > self.capacity:
self.data.popitem(last=False)


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

执行用时:268 ms

内存消耗:22 MB

哈希表和双向链表自实现

Python 3.6

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
class LinkedNode():
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None


class LRUCache:

def __init__(self, capacity: int):
self.data = dict()
self.head = LinkedNode()
self.tail = LinkedNode()
self.head.next = self.tail
self.tail.prev = self.head
self.capacity = capacity
self.size = 0

def get(self, key: int) -> int:
if key not in self.data:
return -1
node = self.data[key]
self.moveToHead(node)
return node.value

def put(self, key: int, value: int) -> None:
if key not in self.data:
node = LinkedNode(key, value)
self.data[key] = node
self.addToHead(node)
self.size += 1
if self.size > self.capacity:
removed = self.removeEnd()
self.data.pop(removed.key)
self.size -= 1
else:
node = self.data[key]
node.value = value
self.moveToHead(node)

def addToHead(self, node):
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node

def moveToHead(self, node):
self.removeNode(node)
self.addToHead(node)

def removeNode(self, node):
node.prev.next = node.next
node.next.prev = node.prev

def removeEnd(self):
removed = self.tail.prev
self.removeNode(removed)
return removed



# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

执行用时:272 ms

内存消耗:22.5 MB

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
class LinkedNode {
friend class LRUCache;
public:
LinkedNode() = default;
LinkedNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) { }

private:
int key = 0;
int value = 0;
LinkedNode* prev = nullptr;
LinkedNode* next = nullptr;
};


class LRUCache {
public:
LRUCache(int _capacity) : capacity(_capacity), size(0) {
head = new LinkedNode();
tail = new LinkedNode();
head->next = tail;
tail->prev = head;
}

int get(int key) {
if (data.count(key) == 0) {
return -1;
} else {
LinkedNode* node = data[key];
moveToHead(node);
return node->value;
}
}

void put(int key, int value) {
if (data.count(key) == 0) {
LinkedNode* node = new LinkedNode(key, value);
data[key] = node;
addToHead(node);
++size;
if (size > capacity) {
LinkedNode* removed = removeEnd();
data.erase(removed->key);
--size;
}
} else {
LinkedNode* node = data[key];
node->value = value;
moveToHead(node);
}
}

void addToHead(LinkedNode* node) {
node->prev = head;
node->next = head->next;
head->next->prev = node;
head->next = node;
}

void moveToHead(LinkedNode* node) {
removeNode(node);
addToHead(node);
}

void removeNode(LinkedNode* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}

LinkedNode* removeEnd() {
LinkedNode* removed = tail->prev;
removeNode(removed);
return removed;
}

private:
unordered_map<int, LinkedNode*> data;
LinkedNode* head;
LinkedNode* tail;
int size = 0;
int capacity;
};

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

执行用时:196 ms

内存消耗:37.2 MB

参考

https://leetcode-cn.com/problems/lru-cache/solution/lruhuan-cun-ji-zhi-by-leetcode-solution/