146. LRU Cache

難度: Medium

類型: Array,Matrix,Linked List,Doubly-Linked List 

CPP程式下載: 146.cpp

Topic:

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 <= 104
• 0 <= value <= 105
• At most 2 * 105 calls will be made to get and put.

Consideration:

1. A unsorted_map to store key and double linked list's "Node*".

2. A Node structure to store key, value integers and prev, next pointers.

3. During the implementation, I finally know that Node has to store key. When we try to remove the LRU memory map, we can't get the key from the Double Linked List Node.

4. Add the latest used key, value to the head.

5. Remove the lastest used key, value from the tail.

6. When there is existed key get or value set, remove the current node and add to the tail. 

Code:

class LRUCache {

private:

    int cap;

  

    struct Node {

        int key;

        int value;

        Node* prev;

        Node* next;

        Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}

    };

    Node* head; // Dummy head

    Node* tail; // Dummy tail  

    unordered_map<int, Node*> lru_map; 

    // Helper: Remove a node from the linked list

    void remove(Node* node) {

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

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

    }

// Helper: Add a node right after the dummy head (Most Recently Used)

    void add(Node* node) {

        node->next = head->next;

        node->prev = head;

        head->next->prev = node;

        head->next = node;

    }

public:

    LRUCache(int capacity) {

        cap = capacity;

        head = new Node(-1, -1);

        tail = new Node(-1, -1);

        head->next = tail;

        tail->prev = head;        

    }

    

    int get(int key) {

        if (lru_map.find(key) == lru_map.end()) {

            return -1;

        }

        Node* node = lru_map[key];

        remove(node);

        add(node);

        return node->value;

    }

    

    void put(int key, int value) {

        if (lru_map.find(key) != lru_map.end()) {

            Node* node = lru_map[key];

            remove(node);

            node->value = value;

            add(node);

            return;

        }

        Node* newNode = new Node(key, value);

        lru_map[key] = newNode;

        add(newNode);

        if (lru_map.size() > cap) {

            Node* lru_node = tail->prev;

            remove(lru_node);

            lru_map.erase(lru_node->key);

            delete lru_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);

 */

Result:

https://leetcode.com/problems/lru-cache/submissions/1940361643/

Accepted

24 / 24 testcases passed

tendchen

submitted at Mar 07, 2026 10:51

Runtime

70ms

Beats69.18%

Memory

173.14MB

Beats68.45%