Leetcode—146. LRU 缓存【中等】（shared

07-16 220阅读

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 cache;
    unordered_map 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 prev;
    shared_ptr 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 &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 = it->second;
            // 更新值
            node->value = value;
            // 更新其所在cache的位置
            remove(node);
            moveToHead(node);
            return;
        }
        // 不存在
        // 先判断cache内存是否满
        if(map.size() == m_capacity) {
            // 拿到cache中最后元素
            shared_ptr lastNode = tail->prev;
            // 并删除cache中最后元素
            remove(lastNode);
            // 删除其在map中的位置
            map.erase(lastNode->key);
        }
        // cache中添加新元素
        moveToHead(make_shared(key, value));
        map[key] = head->next;
    }
    void join(shared_ptr node1, shared_ptr node2) {
        node1->next = node2;
        node2->prev = node1;
    }
    void remove(shared_ptr node) {
        join(node->prev, node->next);
    }
    void moveToHead(shared_ptr node) {
        join(node, head->next);
        join(head, node);
    }
private:
    const int m_capacity;
    shared_ptr head = make_shared(-1, -1);
    shared_ptr tail = make_shared(-1, -1);
    unordered_map 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);
 */