LRU，LFU算法
1、LRU 缓存
题意解释
请为LRU缓存设计一个数据结构。支持两种操作：get和set。
get(key): 如果key在缓存中，则返回key对应的值（保证是正的）；否则返回-1；put(key, value): 如果key在缓存中，则更新key对应的值；否则插入(key, value)，如果缓存已满，则先删除上次使用时间最老的key。
思路
(双链表+哈希)
使用一个双链表和一个哈希表：
- 双链表存储一个节点被使用（get或者put）的时间戳，且按最近使用时间从左到右排好序，最先被使用的节点放在双链表的第一位，因此双链表的最后一位就是最久未被使用的节点；
- 哈希表存储
key对应的链表中的节点地址,用于key-value的增删改查；
初始化：
n是缓存大小；- 双链表和哈希表都为空；
get(key)：
首先用哈希表判断key是否存在：
- 如果key不存在，则返回-1；
- 如果key存在，则返回对应的value，同时将key对应的节点放到双链表的最左侧；
put(key, value)：
首先用哈希表判断key是否存在：
- 如果key存在，则修改对应的value，同时将key对应的节点放到双链表的最左侧；
- 如果key不存在：
- 如果缓存已满，则删除双链表最右侧的节点（上次使用时间最老的节点），更新哈希表；
- 否则，插入(key, value)：同时将key对应的节点放到双链表的最左侧，更新哈希表；
时间复杂度分析：双链表和哈希表的增删改查操作的时间复杂度都是 O(1)，所以get和put操作的时间复杂度也都是O(1) 。
对应的双链表的几种操作
1、删除p节点
p->right->left = p->left; p->left->right = p->right;
2、在L节点之后插入p节点
p->right = L->right; p->left = L; L->right->left = p; L->right = p;
时间复杂度分析：双链表和哈希表的增删改查操作的时间复杂度都是 ，所以get和set操作的时间复杂度也都是 。
C++代码
class LRUCache { public: //定义双链表 struct Node{ int key,value; Node* left ,*right; Node(int _key,int _value): key(_key),value(_value),left(NULL),right(NULL){} }*L,*R;//双链表的最左和最右节点，不存贮值。 int n; unordered_map<int,Node*>hash; void remove(Node* p) { p->right->left = p->left; p->left->right = p->right; } void insert(Node *p) { p->right = L->right; p->left = L; L->right->left = p; L->right = p; } LRUCache(int capacity) { n = capacity; L = new Node(-1,-1),R = new Node(-1,-1); L->right = R; R->left = L; } int get(int key) { if(hash.count(key) == 0) return -1; //不存在关键字 key auto p = hash[key]; remove(p); insert(p);//将当前节点放在双链表的第一位 return p->value; } void put(int key, int value) { if(hash.count(key)) //如果key存在，则修改对应的value { auto p = hash[key]; p->value = value; remove(p); insert(p); } else { if(hash.size() == n) //如果缓存已满，则删除双链表最右侧的节点 { auto p = R->left; remove(p); hash.erase(p->key); //更新哈希表 delete p; //释放内存 } //否则，插入(key, value) auto p = new Node(key,value); hash[key] = p; insert(p); } } };
2、LFU 缓存
题意解释
请为LFU缓存设计一个数据结构。支持两种操作：get和set。
get(key): 如果key在缓存中，则返回key对应的值；否则返回-1；put(key, value): 如果key在缓存中，则更新key对应的值；否则插入(key, value)，如果缓存已满，则先删除使用频率最小的key，如果有多个key具有相同的使用频率，则应该删除最久未使用的key。
C++代码
class LFUCache { public: struct Node { Node *left, *right; int key, val; Node(int _key, int _val) { key = _key, val = _val; left = right = NULL; } }; struct Block { Block *left, *right; Node *head, *tail; int cnt; Block(int _cnt) { cnt = _cnt; left = right = NULL; head = new Node(-1, -1), tail = new Node(-1, -1); head->right = tail, tail->left = head; } ~Block() { delete head; delete tail; } void insert(Node* p) { p->right = head->right; head->right->left = p; p->left = head; head->right = p; } void remove(Node* p) { p->left->right = p->right; p->right->left = p->left; } bool empty() { return head->right == tail; } }*head, *tail; int n; unordered_map<int, Block*> hash_block; unordered_map<int, Node*> hash_node; void insert(Block* p) { // 在p的右侧插入新块，cnt是p->cnt + 1 auto cur = new Block(p->cnt + 1); cur->right = p->right; p->right->left = cur; p->right = cur; cur->left = p; } void remove(Block* p) { p->left->right = p->right; p->right->left = p->left; delete p; } LFUCache(int capacity) { n = capacity; head = new Block(0), tail = new Block(INT_MAX); head->right = tail, tail->left = head; } int get(int key) { if (hash_block.count(key) == 0) return -1; auto block = hash_block[key]; auto node = hash_node[key]; block->remove(node); if (block->right->cnt != block->cnt + 1) insert(block); block->right->insert(node); hash_block[key] = block->right; if (block->empty()) remove(block); return node->val; } void put(int key, int value) { if (!n) return; if (hash_block.count(key)) { hash_node[key]->val = value; get(key); } else { if (hash_block.size() == n) { auto p = head->right->tail->left; head->right->remove(p); if (head->right->empty()) remove(head->right); hash_block.erase(p->key); hash_node.erase(p->key); delete p; } auto p = new Node(key, value); if (head->right->cnt > 1) insert(head); head->right->insert(p); hash_block[key] = head->right; hash_node[key] = p; } } }; /** * Your LFUCache object will be instantiated and called as such: * LFUCache* obj = new LFUCache(capacity); * int param_1 = obj->get(key); * obj->put(key,value); */
