146. LRU緩存機(jī)制

運(yùn)用你所掌握的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)和實(shí)現(xiàn)一個(gè) LRU (最近最少使用) 緩存機(jī)制。它應(yīng)該支持以下操作： 獲取數(shù)據(jù) get 和 寫入數(shù)據(jù) put 。

獲取數(shù)據(jù) get(key) - 如果關(guān)鍵字 (key) 存在于緩存中，則獲取關(guān)鍵字的值（總是正數(shù)），否則返回 -1。
寫入數(shù)據(jù) put(key, value) - 如果關(guān)鍵字已經(jīng)存在，則變更其數(shù)據(jù)值；如果關(guān)鍵字不存在，則插入該組「關(guān)鍵字/值」。當(dāng)緩存容量達(dá)到上限時(shí)，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最久未使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間。

進(jìn)階:

你是否可以在 O(1) 時(shí)間復(fù)雜度內(nèi)完成這兩種操作？

示例:

LRUCache cache = new LRUCache( 2 /* 緩存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 該操作會(huì)使得關(guān)鍵字 2 作廢
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 該操作會(huì)使得關(guān)鍵字 1 作廢
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4

解析:

使用雙向鏈表來表示最近使用的隊(duì)列（方便節(jié)點(diǎn)移動(dòng)和插入），同時(shí)使用map索引來快速訪問任意節(jié)點(diǎn)。

struct DLinkedNode{
    int key, value;
    DLinkedNode *pre, *next;
    DLinkedNode():key(0), value(0), pre(nullptr), next(nullptr){}
    DLinkedNode(int key, int value):key(key), value(value), pre(nullptr), next(nullptr){}
};

class LRUCache {
private:
    unordered_map<int, DLinkedNode*> cache;
    DLinkedNode *head, *tail;
    int size;
    int capacity;

public:
    LRUCache(int capacity):capacity(capacity),size(0) {
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->pre = head;
    }
    
    int get(int key) {
        if(!cache.count(key)) return -1;
        moveToHead(cache[key]);

        return cache[key]->value;
    }
    
    void put(int key, int value) {
        if(cache.count(key)){
            cache[key]->value = value;
            moveToHead(cache[key]);
            return;
        }
        if(size==capacity){
            DLinkedNode* cur = removeTail();
            cache.erase(cur->key);
            --size;
        }
        cache[key] = new DLinkedNode(key, value);
        moveToHead(cache[key]);++size;
       
        return;
    }

    void moveToHead(DLinkedNode *node){
        if(node->next) {//如果是舊的節(jié)點(diǎn)，需要將此節(jié)點(diǎn)原位置的前后節(jié)點(diǎn)連接起來
            node->pre->next = node->next;
            node->next->pre = node->pre;
        }
        head->next->pre = node;
        node->pre = head;
        node->next = head->next;
        head->next = node;
    }
    DLinkedNode* removeTail(){
        DLinkedNode* cur = tail->pre;
        
        tail->pre = cur->pre;
        cur->pre->next=tail;
        return cur;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */