Every day a Leetcode
题目来源：146. LRU 缓存
解法1：哈希表 + 链表
代码：
/** @lc app=leetcode.cn id=146 lang=cpp** [146] LRU 缓存*/// @lc code=start
class LRUCache
{
private:unordered_map<int, list<pair<int, int>>::iterator> hash;// 链表的链接顺序即为最近使用的新旧顺序，最新的信息在链表头节点list<pair<int, int>> cache;int size;public:LRUCache(int capacity) : size(capacity) {}int get(int key){auto it = hash.find(key);if (it == hash.end())return -1;// 将 it->second 从 cache 剪切到 cache 的开头cache.splice(cache.begin(), cache, it->second);return it->second->second;}void put(int key, int value){auto it = hash.find(key);// 如果关键字 key 已经存在if (it != hash.end()){// 变更其数据值 valueit->second->second = value;// 将 it->second 从 cache 剪切到 cache 的开头cache.splice(cache.begin(), cache, it->second);return;}// 向缓存中插入该组 key-valuecache.insert(cache.begin(), make_pair(key, value));hash[key] = cache.begin();// 如果插入操作导致关键字数量超过 capacityif (cache.size() > size){// 逐出最久未使用的关键字hash.erase(cache.back().first);cache.pop_back();}}
};/*** 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);*/
// @lc code=end
结果：
复杂度分析：
时间复杂度：O(1)。
空间复杂度：O(n)，其中 n 是节点个数。
解法2：哈希表 + 自定义双向链表
代码：
// 哈希表 + 自定义双向链表class Node
{
public:int key, value;Node *prev, *next;Node(int k = 0, int v = 0) : key(k), value(v) {}
};class LRUCache
{
private:int capacity;Node *dummy; // 哨兵节点unordered_map<int, Node *> key_to_node;// 删除一个节点（抽出一本书）void remove(Node *x){x->prev->next = x->next;x->next->prev = x->prev;}// 在链表头添加一个节点（把一本书放在最上面）void push_front(Node *x){x->prev = dummy;x->next = dummy->next;x->prev->next = x;x->next->prev = x;}Node *get_node(int key){auto it = key_to_node.find(key);if (it == key_to_node.end()) // 没有这本书return nullptr;auto node = it->second; // 有这本书remove(node); // 把这本书抽出来push_front(node); // 放在最上面return node;}public:LRUCache(int capacity) : capacity(capacity), dummy(new Node()){dummy->prev = dummy;dummy->next = dummy;}int get(int key){auto node = get_node(key);return node ? node->value : -1;}void put(int key, int value){auto node = get_node(key);if (node){ // 有这本书node->value = value; // 更新 valuereturn;}key_to_node[key] = node = new Node(key, value); // 新书push_front(node); // 放在最上面if (key_to_node.size() > capacity){ // 书太多了auto back_node = dummy->prev;key_to_node.erase(back_node->key);remove(back_node); // 去掉最后一本书delete back_node; // 释放内存}}
};
结果：
复杂度分析：
时间复杂度：O(1)。
空间复杂度：O(n)，其中 n 是节点个数。
