146. LRU缓存机制
题目：
运用你所掌握的数据结构，设计实现一个 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
LRU 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的结合体。哈希表中存着指向链表节点的指针，从而实现链表的快速查找。
解法：
struct linkedNode {
int key;
int val;
linkedNode *pre;
linkedNode *next;
linkedNode(): key(0), val(0), pre(NULL), next(NULL) {}
linkedNode(int _key, int _val): key(_key), val(_val), pre(NULL), next(NULL) {}
}; //有分号
class LRUCache {
private:
int size;
int capacity;
linkedNode *head;
linkedNode *tail;
unordered_map<int, linkedNode*> cache;
void moveToFirst(linkedNode *node) { //将非第一个节点的node拎到head后面
linkedNode *ptr = head->next;
head->next = node;
node->pre->next = node->next;
node->next->pre = node->pre;
node->pre = head;
node->next = ptr;
ptr->pre = node;
}
void insertFirstNode(linkedNode *node) { //插入一个新节点到head后面
linkedNode *ptr = head->next;
head->next = node;
node->pre = head;
node->next = ptr;
ptr->pre = node;
}
void removeLastNode() { //删除最后一个老节点
linkedNode *ptr = tail->pre;
cache.erase(ptr->key); //释放cache中的指针！
ptr->pre->next = tail;
tail->pre = ptr->pre;
delete ptr; //释放内存
}
public:
LRUCache(int _capacity) {
size = 0;
capacity = _capacity;
head = new linkedNode(); //辅助节点，不用考虑增首节点删尾节点时NULL指针
tail = new linkedNode();
head->next = tail;
tail->pre = head;
}
int get(int key) {
if (!cache.count(key)) //hash表中无此节点
return -1;
linkedNode *node = cache[key]; //O(1)找到该节点
if (head->next == node) //node就是head后第一个节点
return node->val;
moveToFirst(node); //不是首节点就拎到首节点处
return node->val;
}
void put(int key, int value) {
if (cache.count(key)) { //hash中有该key
linkedNode *node = cache[key];
node->val = value;
if (head->next != node) //不是首节点就拎到首节点处
moveToFirst(node);
return;
}
linkedNode *newNode = new linkedNode(key, value);
cache[key] = newNode; //将新节点添加到hash中
if (size == capacity) { //需要先删再增
removeLastNode();
insertFirstNode(newNode);
} else { //只插入即可
++size;
insertFirstNode(newNode);
}
}
};
/**
* 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);
*/
460. LFU缓存
题目：
请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。它应该支持以下操作：get 和 put。
get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。 put(key, value) - 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除最久未使用的键。 「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。
进阶： 你是否可以在 O(1) 时间复杂度内执行两项操作？
解法
struct setNode {
int key;
int val;
int cnt;
int time;
bool operator < (const setNode& node) const {
return cnt == node.cnt ? time < node.time : cnt < node.cnt;
}
};
class LFUCache {
private:
int size;
int capacity;
int time = 0;
unordered_map<int, setNode> cache; //val是节点
set<setNode> treeSet;
public:
LFUCache(int _capacity) {
size = 0;
capacity = _capacity;
}
int get(int key) {
if (capacity == 0)
return -1;
if (!cache.count(key)) //hash表中无此节点
return -1;
setNode node = cache[key]; //O(1)找到该节点
treeSet.erase(node);
node.cnt++;
node.time = ++time;
treeSet.insert(node);
cache[key] = node;
return node.val;
}
void put(int key, int value) {
if (capacity == 0)
return;
if (cache.count(key)) { //hash中有该key
setNode node = cache[key];
treeSet.erase(node);
node.cnt++;
node.time = ++time;
node.val = value;
treeSet.insert(node);
cache[key] = node;
return;
}
if (size == capacity) {
cache.erase(treeSet.begin()->key);
treeSet.erase(treeSet.begin());
} else {
++size;
}
setNode newNode = setNode{key, value, 1, ++time};
cache[key] = newNode;
treeSet.insert(newNode);
}
};
附录：
unordered_map 判断某个键是否存在
1：iterator find ( const key_type& key );
如果key存在，则find返回key对应的迭代器，如果key不存在，则find返回unordered_map::end。因此可以通过map.find(key) == map.end()来判断，key是否存在于当前的unordered_map中。
2：size_type count ( const key_type& key ) const;
count函数用以统计key值在unordered_map中出现的次数。实际上，c++ unordered_map不允许有重复的key。因此，如果key存在，则count返回1，如果不存在，则count返回0。
