設計一個LRU緩存結構

題意

設計LRU緩存結構，該結構在構造時确定大小，假設大小為K，并有如下兩個功能

• set(key, value)：将記錄(key, value)插入該結構
• get(key)：傳回key對應的value值

[要求]

• set和get方法的時間複雜度為O(1)
• 某個key的set或get操作一旦發生，認為這個key的記錄成了最常使用的
• 當緩存的大小超過K時，移除最不經常使用的記錄，即set或get最久遠的

若opt=1，接下來兩個整數x, y，表示set(x, y)

若opt=2，接下來一個整數x，表示get(x)，若x未出現過或已被移除，則傳回-1對于每個操作2，輸出一個答案

題解

#include <unordered_map>
struct DListNode{
    int key, val;
    DListNode* next;
    DListNode* pre;
    DListNode(int key, int value): key(key), val(value), pre(nullptr), next(nullptr){}
};

class DList{
private:
    DListNode* head;
    DListNode* tail;
    int _capacity;
    int _size;
public:
    DList(int capacity){
        head = tail = nullptr;
        this->_capacity = capacity;
        this->_size = 0;
    }

    void push_front(DListNode* dListNode){
        if(this->_size == 0){
            head = dListNode;
            tail = dListNode;
        }
        dListNode->next = head;
        dListNode->pre = nullptr;
        head->pre = dListNode;
        head = dListNode;
        _size++;
        //if(_size > _capacity){
        //    this->pop_back();
        //}
    }

    DListNode* pop_back(){
        DListNode* tmp = tail;
        tail = tail->pre;
        tail->next = nullptr;
        _size--;
        return tmp;
    }

    int size(){
        return this->_size;
    }

    int capacity(){
        return this->_capacity;
    }

    void remove(DListNode* dListNode){

        if(dListNode == head){
            head = dListNode->next;
            head->pre = nullptr;
        }

        if(dListNode == tail){
            tail = dListNode->pre;
            tail->next = nullptr;
        }

        dListNode->pre->next = dListNode->next;
        dListNode->next->pre = dListNode->pre;

        _size--;
    }

};

class Solution {
private:
    unordered_map<int, DListNode*> m;
    DList* dList;
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        dList = new DList(k);
        vector<int> res;
        int len = operators.size();
        for(int i=0; i < len; i++){
            int op = operators[i][0];
            if(op == 1){
                set(operators[i][1], operators[i][2]);
            }
            else{
                res.push_back(get(operators[i][1]));
            }
        }
        return res;
    }

    void set(int key, int value){
        DListNode* dListNode = new DListNode(key, value);
        if(m.find(key) == m.end()){
            if(dList->size() == dList->capacity()){
                DListNode* dListNode = dList->pop_back();
                m.erase(dListNode->key);
            }
            dList->push_front(dListNode);
            m.insert(make_pair(key, dListNode));
        }
        else{
            dList->remove(m.at(key));
            dList->push_front(dListNode);
            m.insert(make_pair(key, dListNode));
        }
    }
    int get(int key){
        if(m.find(key) == m.end()){
            return -1;
        }
        else{
            int val = m.at(key)->val;
            set(key, val);
            return val;
        }
    }
};
           

自測可以，但是無法通過，日後再看