LeetCode 146 LRU緩存機制

題目描述

運用你所掌握的資料結構，設計和實作一個 LRU (最近最少使用) 緩存機制 。實作 LRUCache 類：

LRUCache(int capacity) 以正整數作為容量 capacity 初始化 LRU 緩存

int get(int key) 如果關鍵字 key 存在于緩存中，則傳回關鍵字的值，否則傳回 -1 。

void put(int key, int value) 如果關鍵字已經存在，則變更其資料值；如果關鍵字不存在，則插入該組「關鍵字-值」。當緩存容量達到上限時，它應該在寫入新資料之前删除最久未使用的資料值，進而為新的資料值留出空間。

進階：你是否可以在 O(1) 時間複雜度内完成這兩種操作？

示例：

輸入

[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]

[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

輸出

[null, null, null, 1, null, -1, null, -1, 3, 4]

解釋

LRUCache lRUCache = new LRUCache(2);

lRUCache.put(1, 1); // 緩存是 {1=1}

lRUCache.put(2, 2); // 緩存是 {1=1, 2=2}

lRUCache.get(1); // 傳回 1

lRUCache.put(3, 3); // 該操作會使得關鍵字 2 廢棄，緩存是 {1=1, 3=3}

lRUCache.get(2); // 傳回 -1 (未找到)

lRUCache.put(4, 4); // 該操作會使得關鍵字 1 廢棄，緩存是 {4=4, 3=3}

lRUCache.get(1); // 傳回 -1 (未找到)

lRUCache.get(3); // 傳回 3

lRUCache.get(4); // 傳回 4

清華作業系統視訊

由于出棧入棧時間複雜度比較高，是以使用雙連結清單來存儲頁面，hash表來儲存鍵值對。

• 當插入新入的頁面時需要判斷該頁面是否在雙連結清單中存在，如果存在删除該頁面并插入到連結清單最前面，插入的時候雙連結清單超過了cache給定的cache的大小，那麼需要删除最後的頁面，需要删除雙連結清單中最後一個頁面且hash表中對應的鍵值對也要删除。
• 當通路一個頁面時，如果該頁面不存在，那麼傳回-1，如果該頁面存在需要傳回該頁面的值，需要注意的是通路了該頁面需要删除該頁面并且放到雙連結清單最前面。因為通路一個頁面意味着該頁面也是被操作過的。

class LRUCache {
public:
    struct Node{
        int key,val;
        Node *left,*right;
        Node(int _key,int _val):key(_key),val(_val),left(NULL),right(NULL){}
    }*L,*R;
    unordered_map<int,Node*> hash;
    int n;
    LRUCache(int capacity) {
        n = capacity;
        L = new Node(-1,-1),R = new Node(-1,-1);
        L->right=R,R->left=L;//初始情況隻有左右兩個節點，需要互相指向對方
    }
    void remove(Node *p)
    {
        p->left->right=p->right;
        p->right->left=p->left;    
    }
    void insert(Node *p)
    {
        p->right=L->right;
        p->left=L;
        L->right->left=p;
        L->right=p;
    }

    int get(int key) {
    //如果得到節點需要将節點删除移動到連結清單首部
        if(hash.count(key)==0) return -1;
        auto p = hash[key];
        remove(p);
        insert(p);
        return p->val;
    }
    
    void put(int key, int value) {
    //要找的節點存在，則修改值，移除節點，插入到連結清單首部
        if(hash.count(key))
        {
            auto p = hash[key];
            p->val=value;
            remove(p);
            insert(p);
        }
        else 
        {
        //超出容量之後删除尾部的節點，并且删除hash表中的節點
            if(hash.size()==n) 
            {
                auto p = R->left;
                remove(p);
                hash.erase(p->key);
                delete p;
            }
            //反之建立節點，hash中建立節點，且插入到連結清單首部
            auto p = new Node(key,value);
            hash[key]=p;
            insert(p);
        }
    }
};

/**
 * 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);
 */