Leetcode—146. LRU 缓存【中等】（shared_ptr、unordered_map、list）

2024每日刷题（143）

Leetcode—146. LRU 缓存

先验知识

list & unordered_map 实现代码

struct Node{
    int key;
    int value;
    Node(int key, int value): key(key), value(value) {}
};

class LRUCache {
public:
    LRUCache(int capacity): m_capacity(capacity) {

    }
    
    int get(int key) {
        // 不存在
        const auto it = map.find(key);
        if(it == map.cend()) {
            return -1;
        }

        // 存在
        const auto& listIt = it->second;

        // 还需要更新在cache中的位置
        cache.splice(cache.begin(), cache, listIt);

        return listIt->value;
    }
    
    void put(int key, int value) {
        // 存在该元素
        if(const auto it = map.find(key); it != map.cend()) {
            const auto& listIt = it->second;
            // 需要更新map中的value
            listIt->value = value;

            // 把元素移到list前面
            cache.splice(cache.begin(), cache, listIt);
            return; 
        }

        // 不存在的情况
        // 判断cache的内存够不够
        if(cache.size() == m_capacity) {
            // 拿到cache中最后元素
            const Node& lastIt = cache.back(); 

            // erase掉map中这个元素
            map.erase(lastIt.key);

            // cache中需要pop_back()
            cache.pop_back();
        }

        // 添加新元素
        cache.emplace_front(key, value);
        map[key] = cache.begin();
    }
private:
    const int m_capacity;
    list<Node> cache;
    unordered_map<int, list<Node>::iterator> map;
};

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

运行结果

unordered_map + shared_ptr 实现代码

struct Node{
    int key;
    int value;
    shared_ptr<Node> prev;
    shared_ptr<Node> next;
    Node(int key, int value): key(key), value(value) {}
};

class LRUCache {
public:
    LRUCache(int capacity): m_capacity(capacity) {
        join(head, tail);
    }
    
    int get(int key) {
        const auto it = map.find(key);
        // 不存在
        if(it == map.cend()) {
            return -1;
        }

        // 存在
        shared_ptr<Node> &tarNode = it->second;

        // 更新其cache位置
        remove(tarNode);
        moveToHead(tarNode);
        return tarNode->value;
    }
    
    void put(int key, int value) {
        // 存在
        if(const auto it = map.find(key); it != map.cend()) {
            shared_ptr<Node>& node = it->second;

            // 更新值
            node->value = value;

            // 更新其所在cache的位置
            remove(node);
            moveToHead(node);
            return;
        }

        // 不存在
        // 先判断cache内存是否满
        if(map.size() == m_capacity) {
            // 拿到cache中最后元素
            shared_ptr<Node> lastNode = tail->prev;

            // 并删除cache中最后元素
            remove(lastNode);

            // 删除其在map中的位置
            map.erase(lastNode->key);
        }
        // cache中添加新元素
        moveToHead(make_shared<Node>(key, value));
        map[key] = head->next;
    }

    void join(shared_ptr<Node> node1, shared_ptr<Node> node2) {
        node1->next = node2;
        node2->prev = node1;
    }

    void remove(shared_ptr<Node> node) {
        join(node->prev, node->next);
    }

    void moveToHead(shared_ptr<Node> node) {
        join(node, head->next);
        join(head, node);
    }

private:
    const int m_capacity;
    shared_ptr<Node> head = make_shared<Node>(-1, -1);
    shared_ptr<Node> tail = make_shared<Node>(-1, -1);
    unordered_map<int, shared_ptr<Node>> map;
};

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

运行结果

之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持！