leetcode 146/460 LRU/LFU
leetcode 146/460 LRU/LFU
题意：
- LRU
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。 - LFU
设计并实现最不经常使用（LFU）缓存的数据结构。它应该支持以下操作：get 和 put。
get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，它应该在插入新项目之前，使最不经常使用的项目无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，最近最少使用的键将被去除。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lfu-cache
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路：
- LRU
双向链表加hash，操作经过抽象就是在链表中删除元素，以及pop_front/push_back. - LFU
也是双向链表加hash，但是这次要记录频率，首先还要保留删除元素和pop_front两个操作。但是push的时候并不是push到队尾，是insert到当前频次的最后。既然如此我们就需要一个hash来维护每个频率的最后一个元素在哪里，insert的时候只需要看需要“分裂”出“新频次”维护还是直接insert到“新频次”的最后。（有点块状链表的意思）
代码：
偷懒链表没有好好写，数组模拟了一下。
class LRUCache {
public:
int ca,c;
const int Begin =0;
struct node{
int key,val,pre,nxt;
node(int _k,int _v,int _n,int _p):key(_k),val(_v),pre(_p),nxt(_n){};
};
vector list;
unordered_map H;
LRUCache(int capacity){
ca=capacity;c=0;
list.push_back(node(-1,-1,0,0));
}
void erase(int x){
list[list[x].nxt].pre=list[x].pre;
list[list[x].pre].nxt=list[x].nxt;
}
void add(int _k,int _v,int _n,int _p){
list.push_back(node(_k,_v,_n,_p));
H[_k]=list[_n].pre=list[_p].nxt=list.size()-1;
}
int get(int key) {
if(H.count(key)==0) return -1;
else{
int h_k=H[key];
int ret = list[h_k].val;
erase(h_k);
add(key,list[h_k].val,0,list[0].pre);
return ret;
}
}
void put(int key, int value) {
if(H.count(key)!=0){
int h_k=H[key];
erase(h_k);
add(key,value,0,list[0].pre);
}
else{
++c;
if(c>ca){
H.erase(list[list[0].nxt].key);
erase(list[0].nxt);
--c;
add(key,value,0,list[0].pre);
}
else{
add(key,value,0,list[0].pre);
}
}
}
};
class LFUCache {
public:
int ca,c;
const int Begin =0;
struct node{
int feq,key,val,pre,nxt;
node(int _f,int _k,int _v,int _n,int _p):feq(_f),key(_k),val(_v),pre(_p),nxt(_n){};
};
vector list;
unordered_map H,F;
LFUCache(int capacity){
ca=capacity;c=0;
list.push_back(node(0,-1,-1,0,0));
}
void erase(int x){
if(F[list[x].feq]==x){
if(list[list[x].pre].feq!=list[x].feq)F.erase(list[x].feq);
else F[list[x].feq]=list[x].pre;
}
list[list[x].nxt].pre=list[x].pre;
list[list[x].pre].nxt=list[x].nxt;
}
void add(int _f,int _k,int _v,int _n,int _p){
list.push_back(node(_f,_k,_v,_n,_p));
F[_f]=H[_k]=list[_n].pre=list[_p].nxt=list.size()-1;
}
int get(int key) {
if(H.count(key)==0) return -1;
else{
int h_k=H[key];
int ret = list[h_k].val;
int _f=list[h_k].feq+1;
if(F.count(_f))
add(_f,key,list[h_k].val,list[F[_f]].nxt,F[_f]);
else{
add(_f,key,list[h_k].val,list[F[_f-1]].nxt,F[_f-1]);
}
erase(h_k);
return ret;
}
}
void put(int key, int value) {
if(ca==0) return;
if(H.count(key)!=0){
get(key);
list[H[key]].val=value;
}
else{
++c;
if(c>ca){
if(list[0].nxt!=0)H.erase(list[list[0].nxt].key);
--c;
erase(list[0].nxt);
if(F.count(1))
add(1,key,value,list[F[1]].nxt,F[1]);
else{
add(1,key,value,list[0].nxt,0);
}
}
else{
if(F.count(1))
add(1,key,value,list[F[1]].nxt,F[1]);
else{
add(1,key,value,list[0].nxt,0);
}
}
}
}
};