题解 | #设计LRU缓存结构#

class LinkNode{
public:
int key;
int val;
LinkNode * pNext;
LinkNode * pPre;

LinkNode(int key, int val){
    this->key = key;
    this->val = val;
    pNext = NULL;
    pPre = NULL;
}

};

class Solution{
public:
/**
* lru design
* @param operators int整型vector<vector<>> the ops
* @param k int整型 the k
* @return int整型vector
*/
Solution(){
head = new LinkNode(0, 0);
tail = new LinkNode(0, 0);
head->pNext = tail;
tail->pNext = head;
}

vector<int> LRU(vector<vector<int> >& operators, int k) {
    // write code here
    this->capaticy = k;
    vector<int> ret;
    if(operators.empty()) return ret;

    for(int i = 0; i<operators.size(); i++){
        //cout<<nodeMap.size()<<i <<endl;
        int opt = operators.at(i)[0];
        if(opt == 1){
            int key = operators.at(i)[1];
            int val = operators.at(i)[2];
            Put(key,  val);
        }
        else if(opt == 2){
            int valRet = Get(operators.at(i)[1]);
            ret.push_back(valRet);
        }
    }

    return ret;
}

void Add(LinkNode *node){
    node->pPre = head;
    node->pNext = head->pNext;
    head->pNext->pPre = node;
    head->pNext = node;
}

void Remove(LinkNode *node){
    node->pPre->pNext = node->pNext;
    node->pNext->pPre = node->pPre;
}

void UpDate(LinkNode *node){
    Remove(node);
    Add(node);
}

int Get(int key){
    LinkNode * node = nodeMap[key];
    if(!node) return -1;

    UpDate(node);
    return node->val;
}

void Put(int key, int val){
    LinkNode *node = nodeMap[key];

    // 没有找到就放到头部后面
    if(!node) {
        node = new LinkNode(key, val);
        Add( node);
        nodeMap[key] = node;
        this->currCount++;
    }else{
        node->val = val;
        UpDate(node);
    }

    // 超容，删除尾部节点
    if(this->currCount > this->capaticy){
        LinkNode * node = tail->pPre;

        LinkNode * pre = tail->pPre->pPre;
        pre->pNext = tail;
        tail->pPre = pre;

        nodeMap.erase(node->key);
        free(node);
        this->currCount--;
    }
}

private:
int capaticy;
int currCount = 0;
LinkNode head;
LinkNode *tail;
map<int, LinkNode> nodeMap ;
};