LeetCode 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

解答:

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
class LRUCache {
public:
// LRUCache(int capacity) : _cap(capacity) {}
LRUCache(int capacity) {
_cap = capacity;
}

int get(int key) {
auto it = _m.find(key);
if (it == _m.end()) return -1;
int val = it->second->second;
_list.splice(_list.begin(), list, it->second);
return it->second->second;
}

void put(int key, int value) {
auto it = _m.find(key);
if (it != _m.end()) {
_list.erase(it->second);
}
_list.push_front(make_pair(key, value));
_m[key] = _list.begin();

if (_list.size() > _cap) {
int key = _list.back().first;
_m.erase(key);
_list.pop_back();
}
}

private:
unordered_map<int, list<pair<int, int>>::iterator> _m;
list<pair<int, int>> _list;
int _cap;
};

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

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×