leetcode 146/460 LRU/LFU

题意：

1. LRU
   运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
   获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
   写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
   
   
   

2. LFU
   设计并实现最不经常使用（LFU）缓存的数据结构。它应该支持以下操作：get 和 put。
   get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
   put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，它应该在插入新项目之前，使最不经常使用的项目无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，最近最少使用的键将被去除。
   

   来源：力扣（LeetCode）
   链接：https://leetcode-cn.com/problems/lfu-cache
   著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

1. LRU
   双向链表加hash，操作经过抽象就是在链表中删除元素，以及pop_front/push_back.
2. 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<node> list;    unordered_map<int,int> 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<node> list;    unordered_map<int,int> 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);                }            }        }    }};

来源：https://www.icode9.com/content-4-541451.html