1.題目描述

LRU(Least Recently Used)最近最少使用算法，通過淘汰最久為使用的緩存使緩存容量滿足一致性
(1) LRUCache(int capacity) 以 正整數(shù) 作為容量 capacity 初始化 LRU 緩存
(2) int get(int key) 如果關(guān)鍵字 key 存在于緩存中，則返回關(guān)鍵字的值，否則返回 -1 。
(3)void put(int key, int value) 如果關(guān)鍵字 key 已經(jīng)存在，則變更其數(shù)據(jù)值 value ；如果不存在，則向緩存中插入該組 key-value 。如果插入操作導(dǎo)致關(guān)鍵字?jǐn)?shù)量超過 capacity ，則應(yīng)該 逐出 最久未使用的關(guān)鍵字。
(4)函數(shù) get 和 put 必須以 O(1) 的平均時(shí)間復(fù)雜度運(yùn)行

成都創(chuàng)新互聯(lián)是一家專業(yè)提供沅江企業(yè)網(wǎng)站建設(shè),專注與成都網(wǎng)站設(shè)計(jì)、做網(wǎng)站、H5網(wǎng)站設(shè)計(jì)、小程序制作等業(yè)務(wù)。10年已為沅江眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站設(shè)計(jì)公司優(yōu)惠進(jìn)行中。2.例子

輸入
[“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); // 該操作會(huì)使得關(guān)鍵字 2 作廢，緩存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 該操作會(huì)使得關(guān)鍵字 1 作廢，緩存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

3.思路

(1)使用雙向鏈表，從虛擬頭節(jié)點(diǎn)插入時(shí)，尾節(jié)點(diǎn)就是最久未使用的節(jié)點(diǎn)，頭節(jié)點(diǎn)就是最新插入的節(jié)點(diǎn)。由于雙向鏈表的特性，刪除鏈表中的節(jié)點(diǎn)的時(shí)間復(fù)雜度是O(1)。
(2)構(gòu)建一個(gè)key-value結(jié)構(gòu)，可以記錄put()方法插入的鍵值，以及對(duì)應(yīng)的節(jié)點(diǎn)地址，從而方便找到雙向鏈表中的對(duì)應(yīng)節(jié)點(diǎn)，此hash表結(jié)構(gòu)為key(鍵)-value(值，對(duì)應(yīng)節(jié)點(diǎn)地址)
(3)對(duì)于get(key)方法，需要滿足獲取到get(key)的值后，將雙向鏈表的對(duì)應(yīng)節(jié)點(diǎn)刪除，并且重新從虛擬頭節(jié)點(diǎn)后加入，然后維護(hù)hash表結(jié)構(gòu)，記錄key(鍵)-value(值，對(duì)應(yīng)節(jié)點(diǎn)地址)
(4)對(duì)于put(key,value)方法，需要分類討論
1)容量未滿時(shí)，key值已經(jīng)存在時(shí)，刪除雙向鏈表中對(duì)應(yīng)節(jié)點(diǎn)，從虛擬頭節(jié)點(diǎn)后再次加入，然后維 護(hù)hash表結(jié)構(gòu)
key值不存在(新的key，value)，創(chuàng)建新的節(jié)點(diǎn)，直接從雙向鏈表中的虛擬頭節(jié)點(diǎn)后加入，維護(hù)hash表結(jié)構(gòu)
2）容量已滿，key值已經(jīng)存在時(shí)，刪除雙向鏈表中對(duì)應(yīng)節(jié)點(diǎn)，從虛擬頭節(jié)點(diǎn)后再次加入，然后維 護(hù)hash表結(jié)構(gòu)
key值不存在(新的key，value)，需要將雙向鏈表尾節(jié)點(diǎn)刪除，維護(hù)hash表中的信息(刪除過期系欸但信息)，然后創(chuàng)建新節(jié)點(diǎn)，直接從雙向鏈表中的虛擬頭節(jié)點(diǎn)后加入，維護(hù)hash表結(jié)構(gòu)(增加新節(jié)點(diǎn)信息)

4.代碼

class LRUCache {private:
    struct Node{//雙向鏈表的節(jié)點(diǎn)信息
        int key = -1;
        int val = -1;
        Node* pre = NULL;
        Node* next = NULL;
    };

    struct element{// hash表中的元素信息
        int val = -1;
        Node* addr = NULL;
    };

    Node* VirtualNode;// 鏈表的虛擬頭節(jié)點(diǎn)
    Node* tailNode; // 鏈表的尾節(jié)點(diǎn)

    int size = 0;// 記錄鏈表長(zhǎng)度
    int capacity;// 容量
    
    unordered_mapmp; // hash表
    
public:
    LRUCache(int capacity) {
        this->capacity = capacity; // 初始化容量
        this->VirtualNode = new Node(); // 初始化虛擬頭節(jié)點(diǎn)
        this->tailNode = this->VirtualNode;
    }

    void addLinkedList(Node* node){//從頭插入節(jié)點(diǎn)
        if(VirtualNode->next == NULL){VirtualNode->next = node;
            node->pre = VirtualNode;
        }else{Node* temp = VirtualNode->next;
            node->next = temp;
            node->pre = VirtualNode;

            VirtualNode->next = node;
            temp->pre = node;

        }
   
        // 維護(hù)尾指針，第一次插入的節(jié)點(diǎn)為尾指針
        if(size == 0){tailNode = node;
        }
        size++;   
    }

    void removeLinkedList(Node* node){//刪除某個(gè)節(jié)點(diǎn)，使用雙向鏈表可以找到該節(jié)點(diǎn)的前一個(gè)和后一個(gè)節(jié)點(diǎn)

        Node* preNode = node->pre;
        Node* nextNode = node->next;

        // 需要?jiǎng)h除的節(jié)點(diǎn)是尾節(jié)點(diǎn)
        if(node == tailNode){preNode->next = NULL;
            tailNode = preNode;// 維護(hù)尾節(jié)點(diǎn)
        }else{preNode->next = nextNode;
            nextNode->pre = preNode;
        }
        size--;
    }
    
    int get(int key) {// 沒有節(jié)點(diǎn)或需要查詢的節(jié)點(diǎn)已經(jīng)過期
        if( size == 0 || mp[key].val == -1){return -1;
        } 
        else{// 如果節(jié)點(diǎn)過期，需要將hash表中的val值置為-1，此時(shí)鏈表中已經(jīng)不存在該節(jié)點(diǎn)，無(wú)法完成刪除操作
            // 更新鏈表，使得尾節(jié)點(diǎn)是最近最少使用的節(jié)點(diǎn)，頭節(jié)點(diǎn)是最近使用過的節(jié)點(diǎn)
            // 刪除mp[key].addr節(jié)點(diǎn)，并且從頭插入此節(jié)點(diǎn)
            removeLinkedList(mp[key].addr);
            addLinkedList(mp[key].addr);
            return mp[key].val;
        }
    }
    
    void put(int key, int value) {
        // 鏈表長(zhǎng)度小于capacity
        if(this->size< this->capacity){// 如果key值存在過了
            if(mp[key].val != -1){// 將鏈表中的mp[key].addr節(jié)點(diǎn)刪除，重新添加
                removeLinkedList(mp[key].addr);
                addLinkedList(mp[key].addr);
                // 維護(hù)hash表，更新val
                mp[key].val = value;
            }else{//key值之前未添加過，添加新的key值
                // 創(chuàng)建新節(jié)點(diǎn)
                Node* node =  new Node;
                node->key = key;
                node->val = value;
                //向鏈表中添加新節(jié)點(diǎn)node
                addLinkedList(node);
                //維護(hù)hash表
                mp[key].val = value; 
                mp[key].addr = node;
            }  
        }else{//鏈表長(zhǎng)度超過容量

            // 如果之前key值存在過了，不產(chǎn)生新節(jié)點(diǎn)
            if(mp[key].val != -1){// 將鏈表中的mp[key].addr節(jié)點(diǎn)刪除，重新添加
                removeLinkedList(mp[key].addr);
                addLinkedList(mp[key].addr);
                //維護(hù)hash表
                mp[key].val = value; 

            }else{// 如果之前key值不存在，產(chǎn)生新節(jié)點(diǎn)

                // 維護(hù)hash表,節(jié)點(diǎn)過期
                mp[tailNode->key].val = -1;
                
                // 刪除鏈表尾部節(jié)點(diǎn)（最近最少使用）
                removeLinkedList(tailNode);

                // 創(chuàng)建新節(jié)點(diǎn)
                Node* node = new Node;
                node->key = key;
                node->val = value;
                
                // 添加新節(jié)點(diǎn)
                addLinkedList(node);

                // 維護(hù)hash表
                mp[key].val = value; 
                mp[key].addr = node;

            }
        }
    }
};

可見在向LinkedList中加入元素后，都需要維護(hù)hash表，所以代碼可以調(diào)整，并且使用stl中的list結(jié)構(gòu)代替自己編寫的雙向鏈表，從而減少代碼量

class LRUCache {private:
    struct element{// hash表中的元素信息
        int val = -1;
        list::iterator addr;
    };

    listLinkedList;//使用雙向鏈表
    // int size = 0;// 記錄鏈表長(zhǎng)度，由于list.size()函數(shù)的時(shí)間復(fù)雜度是O(N),可以通過維護(hù)一個(gè)size()值減少此處的時(shí)間消耗
    int capacity;// 容量
    unordered_mapmp; // hash表
    
public:
    LRUCache(int capacity) {this->capacity = capacity; // 初始化容量
    }
    
    int get(int key) {// 沒有節(jié)點(diǎn)或需要查詢的節(jié)點(diǎn)已經(jīng)過期
        if( LinkedList.size() == 0 || mp[key].val == -1){return -1;
        } 
        else{// 如果節(jié)點(diǎn)過期，需要將hash表中的val值置為-1，此時(shí)鏈表中已經(jīng)不存在該節(jié)點(diǎn)，無(wú)法完成刪除操作
            // 更新鏈表，使得尾節(jié)點(diǎn)是最近最少使用的節(jié)點(diǎn)，頭節(jié)點(diǎn)是最近使用過的節(jié)點(diǎn)
            // 刪除mp[key].addr節(jié)點(diǎn)，并且從頭插入此節(jié)點(diǎn)
            LinkedList.erase(mp[key].addr);
            LinkedList.push_front(key);
            mp[key].addr = LinkedList.begin();
            return mp[key].val;
        }
    }
    
    void put(int key, int value) {// 鏈表長(zhǎng)度小于capacity
        if(LinkedList.size()< this->capacity){// 如果key值存在過了
            if(mp[key].val != -1){// 將鏈表中的mp[key].addr節(jié)點(diǎn)刪除，重新添加
                LinkedList.erase(mp[key].addr);
                LinkedList.push_front(key);
            }else{//key值之前未添加過，添加新的key值
                //向鏈表中添加新節(jié)點(diǎn)node
                LinkedList.push_front(key);
            } 

        }else{//鏈表長(zhǎng)度超過容量
            // 如果之前key值存在過了，不產(chǎn)生新節(jié)點(diǎn)
            if(mp[key].val != -1){// 將鏈表中的mp[key].addr節(jié)點(diǎn)刪除，重新添加
                LinkedList.erase(mp[key].addr);
                LinkedList.push_front(key);
            }else{// 如果之前key值不存在，產(chǎn)生新節(jié)點(diǎn)
                // 維護(hù)hash表,節(jié)點(diǎn)過期
                mp[LinkedList.back()].val = -1;
                // 刪除鏈表尾部節(jié)點(diǎn)（最近最少使用）
                LinkedList.pop_back();
                // 添加新節(jié)點(diǎn)
                LinkedList.push_front(key);
            }
        }
        // 維護(hù)hash表，更新val
        mp[key].val = value;
        mp[key].addr = LinkedList.begin();
    }
};

注：list結(jié)構(gòu)的list.size()方法的時(shí)間復(fù)雜度為O(n)，因?yàn)槠鋬?nèi)部調(diào)用了distance()方法計(jì)算了所有元素的個(gè)數(shù)，因此可以使用size變量得到雙向鏈表得長(zhǎng)度

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

名稱欄目：LRU緩存實(shí)現(xiàn)-創(chuàng)新互聯(lián)
文章地址：http://weahome.cn/article/ccicii.html