二刷LeetCode--146.LRU缓存(C++版本),必会题目-Toy模板网

这篇具有很好参考价值的文章主要介绍了二刷LeetCode--146.LRU缓存(C++版本),必会题目。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

本题思路:因为需要记录元素的出入顺序,并且每次访问之后需要将该节点提到最前面,因此需要使用双向链表(单链表不方便删除操作),而为了可以在常量时间复杂度内找到对应的元素,我们需要使用哈希表,将每一个插入的元素在哈希表中进行记录.哈希表的key就是插入的key,而哈希表的value应该对应的是双向链表的一个节点.注意:我们可能会想,既然使用哈希表,那么双链表中只需要存储value就可以,为什么还需要存储key呢.这个在执行最久未使用的节点删除的时候可以发现,如果双向链表中只是存储了value,那么删除的时候就不能将哈希表中的记录删除掉.文章来源地址https://www.toymoban.com/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;

    // 移除节点，移除的是最右端的节点，即尾节点（R）之前的那个
    void remove(node *p)
    {
        p -> right -> left = p -> left;
        p -> left -> right = p -> right;
    }

    // 新节点插入函数，在头节点（L）之后
    void insert(node *p)
    {
        p -> right = L -> right;
        p -> left = L;
        L -> right -> left = p;
        L -> right = p;
    }

    // 新被访问的节点放在最左边，最右端的节点就是待删除结点，使用哈希表记录元素是否出现
    LRUCache(int capacity) 
    {
        n = capacity;
        // 首尾节点初始化
        L = new node(-1, -1), R = new node(-1, -1);
        // 初始化之后链表指针赋值
        L -> right = R;
        R -> left = L;
    }
    
    int get(int key) 
    {
        // 检查哈希表中该元素出现的次数
        if(hash.count(key) == 0)
            return -1;
        // 如果出现过，那么就把该元素插入到头部，并且删除该节点
        // 哈希表的value存的是节点（结构体指针类型）
        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;
            // 每访问一次就需要重新删除重新插入到头部
            remove(p);
            insert(p);
        }
        else
        {
            // 首先判断是不是到达容量上限
            if(hash.size() == n)
            {
                // 删除最右边的数据节点
                struct node *p = R -> left;
                remove(p);
                // 更新哈希表
                hash.erase(p -> key);
                delete p;
            }
            // 否则就直接插入新节点即可
            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);
 */