本題思路:因?yàn)樾枰涗浽氐某鋈腠樞?并且每次訪問(wèn)之后需要將該節(jié)點(diǎn)提到最前面,因此需要使用雙向鏈表(單鏈表不方便刪除操作),而為了可以在常量時(shí)間復(fù)雜度內(nèi)找到對(duì)應(yīng)的元素,我們需要使用哈希表,將每一個(gè)插入的元素在哈希表中進(jìn)行記錄.哈希表的key就是插入的key,而哈希表的value應(yīng)該對(duì)應(yīng)的是雙向鏈表的一個(gè)節(jié)點(diǎn).注意:我們可能會(huì)想,既然使用哈希表,那么雙鏈表中只需要存儲(chǔ)value就可以,為什么還需要存儲(chǔ)key呢.這個(gè)在執(zhí)行最久未使用的節(jié)點(diǎn)刪除的時(shí)候可以發(fā)現(xiàn),如果雙向鏈表中只是存儲(chǔ)了value,那么刪除的時(shí)候就不能將哈希表中的記錄刪除掉.文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-647226.html

class LRUCache {
public:
    // 定義雙向鏈表
    struct node 
    {
        int  key, value;
        struct node *left, *right;
        // k-v及左右指針的初始化
        node(int _key, int _value):key(_key), value(_value), left(NULL), right(NULL){}
    }*L, *R;
    // 定義鏈表容量以及哈希表
    int n;
    unordered_map<int, node*> hash;

    // 移除節(jié)點(diǎn)，移除的是最右端的節(jié)點(diǎn)，即尾節(jié)點(diǎn)（R）之前的那個(gè)
    void remove(node *p)
    {
        p -> right -> left = p -> left;
        p -> left -> right = p -> right;
    }

    // 新節(jié)點(diǎn)插入函數(shù)，在頭節(jié)點(diǎn)（L）之后
    void insert(node *p)
    {
        p -> right = L -> right;
        p -> left = L;
        L -> right -> left = p;
        L -> right = p;
    }

    // 新被訪問(wèn)的節(jié)點(diǎn)放在最左邊，最右端的節(jié)點(diǎn)就是待刪除結(jié)點(diǎn)，使用哈希表記錄元素是否出現(xiàn)
    LRUCache(int capacity) 
    {
        n = capacity;
        // 首尾節(jié)點(diǎn)初始化
        L = new node(-1, -1), R = new node(-1, -1);
        // 初始化之后鏈表指針賦值
        L -> right = R;
        R -> left = L;
    }
    
    int get(int key) 
    {
        // 檢查哈希表中該元素出現(xiàn)的次數(shù)
        if(hash.count(key) == 0)
            return -1;
        // 如果出現(xiàn)過(guò)，那么就把該元素插入到頭部，并且刪除該節(jié)點(diǎn)
        // 哈希表的value存的是節(jié)點(diǎn)（結(jié)構(gòu)體指針類(lèi)型）
        struct node *p = hash[key];
        remove(p);
        insert(p);
        return p -> value;
    }
    
    void put(int key, int value) 
    {
        // 如果key存在，那么只需要修改value即可
        if(hash.count(key) != 0)
        {
            auto p = hash[key];
            // struct node *p = hash[key];
            p -> value = value;
            // 每訪問(wèn)一次就需要重新刪除重新插入到頭部
            remove(p);
            insert(p);
        }
        else
        {
            // 首先判斷是不是到達(dá)容量上限
            if(hash.size() == n)
            {
                // 刪除最右邊的數(shù)據(jù)節(jié)點(diǎn)
                struct node *p = R -> left;
                remove(p);
                // 更新哈希表
                hash.erase(p -> key);
                delete p;
            }
            // 否則就直接插入新節(jié)點(diǎn)即可
            struct node *p = new node(key, value);
            insert(p);
            hash[key] = 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);
 */

到了這里，關(guān)于二刷LeetCode--146.LRU緩存(C++版本),必會(huì)題目的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！