Leetcode LRUCache 双向链表+哈希

原题传送门: https://leetcode.com/problems/lru-cache/

使用双向链表+哈希来实现LRUCache问题,可以使缓存的getset操作复杂度都为O(1)

详见代码:

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
struct LNode { // 双向链表的节点
int key, val;
LNode *next, *prev;
LNode() : next(NULL), prev(NULL) {}
LNode(int key, int val) : key(key), val(val) { LNode(); }

// 将本节点从链表中脱离
void disconnect() {
if (next) next->prev = prev;
if (prev) prev->next = next;
}

// 在本节点之后插入node节点
void insert(LNode *node) {
if (next) next->prev = node;
node->next = next;
node->prev = this;
next = node;
}
};

class LRUCache {
int size, capacity;
unordered_map<int, LNode*> hashmap; // 哈希表
LNode *head, *tail; // 双向链表的头尾节点
public:
LRUCache(int capacity): size(0), capacity(capacity) {
head = new LNode;
tail = new LNode;
head->next = tail;
tail->prev = head;
}

int get(int key) {
if (hashmap.find(key) == hashmap.end()) {
return -1;
}
LNode *node = hashmap[key];
node->disconnect();
head->insert(node);
return node->val;
}

void set(int key, int value) {
LNode *node;
if (hashmap.find(key) == hashmap.end()) {
if (size < capacity) {
node = new LNode(key, value);
size++;
} else {
node = tail->prev;
node->disconnect();
hashmap.erase(node->key);
node->key = key;
node->val = value;
}
hashmap[key] = node;
head->insert(node);
} else {
node = hashmap[key];
node->disconnect();
node->val = value;
head->insert(node);
}
}
};