Leetcode146 LRU缓存
经典题，典型compund data structure思想
link
思路：
- 主要思想就是hash table + double-linked list
- 重点就是手动实现这些功能
- 因为
get和put都要求 O ( 1 ) O(1) O(1)时间内实现，所以就是要用hash table - 而要实现LRU，所以用双向链表维护最近使用
ps: code 多打几遍就熟悉了
class Node {
public:int key;int value;Node *last, *next;Node(int k = 0, int val = 0) : key(k), value(val), last(nullptr), next(nullptr) {}
};class LRUCache {
private:unordered_map<int, Node*> cache;int size;int capacity;Node *head;Node *tail;void addNode(Node *node) {node->next = head->next;head->next->last = node;node->last = head;head->next = node;}void deleteNode(Node *node) {node->last->next = node->next;node->next->last = node->last;}void move(Node *node) {deleteNode(node);addNode(node);}Node *deleteTail() {Node *node = tail->last;deleteNode(node);return node;}public:LRUCache(int capacity) : capacity(capacity), size(0) {head = new Node();tail = new Node();head->next = tail;tail->last = head;}int get(int key) {if (cache.count(key) == 0)return -1;Node *node = cache[key];move(node);return node->value;}void put(int key, int value) {if (cache.count(key) > 0) {Node *node = cache[key];node->value = value;move(node);}else {Node *node = new Node(key, value);cache[key] = node;addNode(node);++size;if (size > capacity) {Node *lastUsed = deleteTail();cache.erase(lastUsed->key);--size;delete lastUsed;}}}
};