题解 | 设计LFU缓存结构

  #include <iostream>
  using namespace std;
 struct mylist
    {
        int val;
        int key;
        int coust;
        mylist* next;
        mylist* prev;

        mylist(int val, int key) :val(val), key(key), coust(0), next(nullptr), prev(nullptr) {}
    };

    struct myhash
    {
        int val;
        int key;

        mylist* lists;
        myhash* next;

        myhash(int val, int key, mylist* lists) :val(val), key(key), lists(lists), next() {}

    };
class Solution1 {
public:

    vector<myhash*>hashheep;
    int capacity;
    int size;

    mylist* head;
    mylist* end;

     Solution1(int capacity) {
        // write code here
        this->capacity = capacity;
        hashheep.resize(capacity, nullptr);
        size = 0;
        head = new mylist(0, 0);
        end = new mylist(0, 0);
        head->next = end;
        head->prev = nullptr;
        end->prev = head;
        end->next = nullptr;
    }
   
    int Key(int key)
    {
        return (unsigned) key % capacity;
    }
    void setLRU(mylist* newliasts) {
    newliasts->coust++;
    mylist* cur = head->next;
    // 找到第一个频率 > 新节点频率的节点（相同频率的节点，新节点应插入其前面，保持 LRU）
    while (cur != end && cur->coust <= newliasts->coust) {
        cur = cur->next;
    }
    // 插入到 cur 之前
    newliasts->prev = cur->prev;
    newliasts->next = cur;
    cur->prev->next = newliasts;
    cur->prev = newliasts;
    }
    void clearhashlist(int key)
    {
        int a = Key(key);
        myhash* munny = new myhash(0, 0, nullptr);
        munny->next = hashheep[a];
        myhash* temp = munny->next;
        myhash* prevs = munny;
        while (temp && temp->key != key) {
            temp = temp->next;
            prevs = prevs->next;
        }
        if (!temp) {delete munny; return; }
        if (temp == hashheep[a])hashheep[a] = hashheep[a]->next;
        mylist* cap = temp->lists->next;
        mylist* cad = temp->lists->prev;
        temp->lists->next = nullptr;
        temp->lists->prev = nullptr;
        cad->next = cap;
        cap->prev = cad;
        delete temp->lists;
        prevs->next = temp->next;
        delete temp;

        size--;
        delete munny;

    }
    myhash* gethash(int key)
    {
        int a = Key(key);
        myhash* temp = hashheep[a];
        while (temp && temp->key != key) {
            temp = temp->next;
        }
        if (!temp)return nullptr;

        mylist* cap = temp->lists->next;
        mylist* cad = temp->lists->prev;
        temp->lists->next = nullptr;
        temp->lists->prev = nullptr;
        cad->next = cap;
        cap->prev = cad;
        setLRU(temp->lists);
        return temp;
    }
    void addhash(int key, int value, mylist* lists)
    {
        int a = Key(key);
        myhash* newhash = new myhash(value, key, lists);
        if (!hashheep[a])
        {
            hashheep[a] = newhash;
            size++;
        }
        else {
            myhash* node = hashheep[a];
            newhash->next = node;
            hashheep[a] = newhash;
            size++;
        }
    }
    void addlists(int key, int value)
    {
        myhash* a = gethash(key);
        if (a)
        {
            a->val = value;
            a->lists->val = value;
        }
        else if (size < capacity)
        {
            mylist* newliasts = new mylist(value, key);
            setLRU(newliasts);
            addhash(key, value, newliasts);
            return;
        }
        else if (size >= capacity) {

            if (end->prev != head)
            {
                clearhashlist(head->next->key);
                mylist* newliasts = new mylist(value, key);
                setLRU(newliasts);
                addhash(key, value, newliasts);
            }
        }
    }

};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * lfu design
     * @param operators int整型vector<vector<>> ops
     * @param k int整型 the k
     * @return int整型vector
     */
       vector<int> LFU(vector<vector<int> >& operators, int k) {
        // write code here
        Solution1 c(k);

        vector<int> ret;
        myhash* rets = nullptr;
        
        for (auto a : operators)
        {   if(a.size() == 3)
           {
            int val = a[2];
            int key = a[1];
           c. addlists(key, val);
           }
          else {
            int keys  =a[1];
            rets=c.gethash(keys);
             if(rets)ret.push_back(rets->val);
             else ret.push_back(-1);
           }


        }
       
        return ret;
    }

};