Разработайте структуру данных, которая соответствует ограничениям кеша наименее использовавшихся (LRU).

Реализуйте класс LRUCache:

  • LRUCache(int capacity) Инициализировать кэш LRU с положительным размером capacity.
  • int get(int key) Вернуть значение key, если ключ существует, иначе вернуть -1.
  • void put(int key, int value) Обновите значение key, если key существует. В противном случае добавьте в кеш пару key-value. Если количество ключей превышает capacity из этой операции, исключите последний использованный ключ.

Каждая из функций get и put должна выполняться со средней временной сложностью O(1).

Пример 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

Ограничения:

  • 1 <= capacity <= 3000
  • 0 <= key <= 104
  • 0 <= value <= 105
  • Максимум 2 * 105 вызовов будет сделано на get и put.

Интуиция:

Интуиция состоит в том, чтобы поддерживать кеш фиксированного размера пар ключ-значение, используя двусвязный список и неупорядоченную карту. При доступе или добавлении пары ключ-значение соответствующий узел перемещается в начало связанного списка, что делает его последним использованным элементом. Таким образом, последний использованный элемент всегда оказывается в конце списка. Когда кэш заполняется и добавляется новый элемент, он удаляет элемент в конце списка (наименее недавно использовавшийся), чтобы освободить место для нового элемента, обеспечивая сохранение свойства LRU.

Объяснение:

  1. Node Класс:
  • Это вложенный класс, представляющий узел двусвязного списка.
  • Каждый узел содержит целочисленный ключ, целочисленное значение и указатели на предыдущий и следующий узлы в связанном списке.
  1. LRUCache Класс:
  • Это основной класс LRU Cache.
  • Он имеет фиксированную емкость (cap), указанную во время его создания.
  • Он использует unordered_map<int, Node*> с именем m для хранения пар ключ-значение, где ключ — это целочисленный ключ, а значение — указатель на соответствующий Node.
  1. head и tail узлы:
  • Класс LRUCache имеет два фиктивных узла: head и tail.
  • Эти узлы действуют как стражи в двусвязном списке, помогая упростить крайние случаи и избежать работы с нулевыми указателями.
  • head — это первый узел в связанном списке, а tail — последний узел.
  1. addNode Функция:
  • Эта функция используется для добавления нового узла в начало двусвязного списка (сразу после head).
  • Он принимает Node* newnode в качестве входных данных, представляющих добавляемый узел.
  • Функция обновляет указатели нового узла, предыдущего первого узла и head, чтобы включить новый узел в качестве нового первого узла.
  1. deleteNode Функция:
  • Эта функция используется для удаления узла из двусвязного списка.
  • Он принимает Node* delnode в качестве входных данных, представляющих удаляемый узел.
  • Функция обновляет указатели предыдущего и следующего узлов, чтобы исключить удаляемый узел, эффективно удаляя его из связанного списка.
  1. get Функция:
  • Эта функция используется для извлечения значения из кеша на основе заданного ключа.
  • Если ключ существует в кэше (m.find(key) != m.end()), он извлекает соответствующий узел (resNode), извлекает его значение (ans) и выполняет следующие шаги:
  • Сотрите пару ключ-значение с неупорядоченной карты m.
  • Удалите узел из его текущей позиции в связанном списке, используя deleteNode.
  • Добавьте узел в начало связанного списка, используя addNode, сделав его последним использованным узлом.
  • Обновите карту m, чтобы сохранить ключ с последним использованным узлом.
  • Если ключ не существует в кеше, он возвращает -1.
  1. put Функция:
  • Эта функция используется для вставки или обновления пары ключ-значение в кэше.
  • Если ключ уже существует в кэше, он обновляет значение, выполняя следующие шаги:
  • Сотрите существующую пару ключ-значение с неупорядоченной карты m.
  • Удалите соответствующий узел из его текущей позиции в связанном списке, используя deleteNode.
  • Если кеш заполнен (т. е. m.size() == cap), он удаляет из кеша последний использованный узел, стирая пару ключ-значение из карты m и удаляя узел из конца связанного списка с помощью deleteNode.
  • После обработки выселения (при необходимости) он создает новый узел, используя new Node(key, value), и добавляет его в начало связанного списка, используя addNode.
  • Наконец, он обновляет карту m, чтобы сохранить ключ с новым добавленным узлом.

Код

C++

class LRUCache {
public:
    class Node{
        public: 
            int key;
            int val;
            Node* prev;
            Node* next;
            Node(int key, int val){
                this->key = key;
                this->val = val;
            }
    };
    Node* head = new Node(-1, -1);
    Node* tail = new Node(-1, -1);
    int cap;
    unordered_map<int, Node*> m;
    LRUCache(int capacity) {
        cap = capacity;
        head -> next = tail;
        tail -> prev = head;
    }
    void addNode(Node* newnode){
        Node* temp = head -> next;
        newnode -> next = temp;
        newnode -> prev = head;
        head -> next = newnode;
        temp -> prev = newnode;
    }
    void deleteNode(Node* delnode){
        Node* prevv = delnode -> prev;
        Node* nextt = delnode -> next;
        prevv -> next = nextt;
        nextt -> prev = prevv;
    }
    
    int get(int key) {
        if(m.find(key) != m.end()){
            Node* resNode = m[key];
            int ans = resNode -> val;
            m.erase(key);
            deleteNode(resNode);
            addNode(resNode);
            m[key] = head -> next;
            return ans;
        }
        return -1;
    }
    
    void put(int key, int value) {
        if(m.find(key) != m.end()){
            Node* curr = m[key];
            m.erase(key);
            deleteNode(curr);
        }
        if(m.size() == cap){
            m.erase(tail -> prev -> key);
            deleteNode(tail -> prev);
        }
        addNode(new Node(key, value));
        m[key] = head -> next;
    }
};