LeetCode 146 - LRU Cache

Difficulty: medium

Problem Description

English (LRU Cache)

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Example 1:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

Constraints:

• 1 <= capacity <= 3000
• 0 <= key <= 10^4
• 0 <= value <= 10^5
• At most 2 * 10^5 calls will be made to get and put.

Chinese (LRU 缓存)

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
  函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

• 1 <= capacity <= 3000
• 0 <= key <= 10000
• 0 <= value <= 10^5
• 最多调用 2 * 10^5 次 get 和 put

Solution

C++

class LRUCache {
private:
    struct ListNode {
        int key{0};
        int value{0};
        ListNode* prev{nullptr};
        ListNode* next{nullptr};
    };

public:
    LRUCache(int capacity) : m_size(0), m_capacity(capacity) {
        m_head = new ListNode;
        m_tail = new ListNode;
        m_head->next = m_tail;
        m_tail->prev = m_head;
    }

    int get(int key) {
        auto it = m_node_by_key.find(key);
        if (it == m_node_by_key.end()) {
            return -1;
        }

        ListNode* node = it->second;
        extract_node(node);
        place_node_at_first(node);

        return node->value;
    }

    void put(int key, int value) {
        auto it = m_node_by_key.find(key);
        if (it != m_node_by_key.end()) {  // find it and replace its value
            ListNode* node = it->second;
            extract_node(node);
            node->value = value;
            place_node_at_first(node);
            return;
        }

        if (m_size >= m_capacity) {
            // retire the least recently used element
            ListNode* oldest = m_tail->prev;
            extract_node(oldest);
            m_node_by_key.erase(oldest->key);
            delete oldest;
            --m_size;
        }

        // insert a new node
        ListNode* new_node = new ListNode;
        new_node->key = key;
        new_node->value = value;
        place_node_at_first(new_node);
        m_node_by_key[key] = new_node;
        ++m_size;
    }

private:
    void extract_node(ListNode* node) {
        ListNode* prev = node->prev;
        ListNode* next = node->next;

        node->prev = nullptr;
        node->next = nullptr;

        prev->next = next;
        next->prev = prev;
    }

    void place_node_at_first(ListNode* node) {
        node->prev = m_head;
        node->next = m_head->next;

        m_head->next->prev = node;
        m_head->next = node;
    }

    int m_size;
    int m_capacity;

    ListNode* m_head;
    ListNode* m_tail;
    unordered_map<int, ListNode*> m_node_by_key;
};

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