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