146. LRU Cache

题目描述

146. LRU Cache

哈希表+双向链表

详见代码和注释：

class LRUCache {
private:
    int capacity_{0};
    int size_{0};
    struct Node{
        int key{0};
        int val{0};
        Node* pre{nullptr};
        Node* next{nullptr};
        Node(int k,int v,Node* pr,Node* nex)
            :key(k),val(v),pre(pr),next(nex){}
    };

    Node* head_{nullptr};
    Node* tail_{nullptr};
    //使用哈希表让查找的时间复杂度降为O(1)
    unordered_map<int,Node*> data_;

public:
    LRUCache(int capacity):capacity_(capacity) {
        //题目保证传入大于0的capacity,非法值没考虑
    }
    
    int get(int key) {
        if(data_.contains(key)){
            Node* node = data_[key];
            setHead(node);
            return node->val;
        }
        return -1;
    }
    
    void put(int key, int value) {
        if(data_.contains(key)){
            data_[key]->val = value;
            setHead(data_[key]);
        }else{
            if(capacity_ > 0 && size_ == capacity_){//缓存已满
                Node* to_delete_LRU_node = tail_;//需要删除尾结点,tail_结点就是Least Recently Used Node
                tail_ = tail_->pre;//有可能tail_和head_是同一个结点，tail_->pre是nullptr
                if(tail_){
                    //to_delete_LRU_node的前面还有结点
                    tail_->next = nullptr;
                }else{
                    //to_delete_LRU_node的前面已经没有结点,to_delete_LRU_node和head_指向同一个结点
                    //下面会通过to_delete_LRU_node销毁头结点,需要将head_设置为nullptr,不能让head_指向不存在的内存
                    head_ = nullptr;
                }
                data_.erase(to_delete_LRU_node->key);
                delete to_delete_LRU_node;
                size_--;
            }
            Node* newnode = new Node(key,value,nullptr,head_);
            if(head_){
                head_->pre = newnode;
            }else{
                //如果头结点head_不存在,那么尾结点tail_也一定不存在
                tail_ = newnode;
            }
            head_ = newnode;
            data_[key] = newnode;
            size_++;
        }
    }
private:
    //将node设置为链表的头结点,输入的node不为nullptr
    void setHead(Node* node)
    {
        if(node != head_)
        {
            if(node == tail_){
                //node是尾结点的话,node前一个结点需要作为新的尾结点tail
                tail_ = tail_->pre;
            }
            // if(node->pre) 判断是多余的,node不是头结点,那么node的前一个结点一定不是nullptr
                node->pre->next = node->next;
            if(node->next){//node的下一个结点可能不存在
                node->next->pre = node->pre;
            }
            node->pre = nullptr;
            node->next = head_;

            //前面的条件保证了此处head_一定不为nullptr
            head_->pre = node;
            head_ = node;
        }
    }
};

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

几组测试用例：

["LRUCache","put","put","get","put","get","put","get","get","get"]

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

["LRUCache","put","put","get","put","get","put","get","get","get"]

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

["LRUCache","put","get","put","get","get"]

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