Java | LeetCode
Задача: 146. LRU Cache
Сложность: medium
Реализуйте класс LRUCache:
LRUCache(int capacity) - инициализирует LRU-кэш с положительным размером capacity.
int get(int key) - возвращает значение по ключу, если ключ существует, в противном случае возвращает -1.
void put(int key, int value) - обновляет значение по ключу, если ключ существует. В противном случае добавляет пару ключ-значение в кэш. Если количество ключей превышает установленную емкость после этой операции, удаляет наименее недавно использованный ключ.
Функции get и put должны выполняться за среднее время O(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]
👨💻 Алгоритм:
1⃣Метод добавления узла в конец связного списка (add):
Получите текущий узел в конце списка, это "реальный" хвост: tail.prev, обозначим его как previousEnd.
Вставьте node после previousEnd, установив previousEnd.next = node.
Настройте указатели узла: node.prev = previousEnd и node.next = tail.
Обновите tail.prev = node, делая node новым "реальным" хвостом списка.
2⃣Метод удаления узла из связного списка (remove):
Узел node должен быть удален из списка. Для этого определите узлы nextNode = node.next и prevNode = node.prev.
Чтобы удалить node, переназначьте prevNode.next = nextNode и nextNode.prev = prevNode, эффективно исключая node из списка.
Это превратит, например, последовательность A <-> B <-> C в A <-> C, где prevNode = A и nextNode = C.
3⃣Методы get и put:
get(int key): Проверьте, существует ли ключ в хэш-карте. Если нет, верните -1. Иначе, получите узел, связанный с ключом, переместите его в конец списка с помощью remove(node) и add(node). Верните node.val.
put(int key, int value): Если ключ уже существует, найдите соответствующий узел и удалите его методом remove. Создайте новый узел с key и value, добавьте его в хэш-карту и в конец списка методом add(node). Если размер кэша превышает установленную емкость после добавления, удалите самый редко используемый узел (который находится в голове списка после фиктивного узла head), затем удалите соответствующий ключ из хэш-карты.
😎 Решение:
class ListNode {
int key;
int val;
ListNode next;
ListNode prev;
public ListNode(int key, int val) {
this.key = key;
this.val = val;
}
}
class LRUCache {
int capacity;
Map<Integer, ListNode> dic;
ListNode head;
ListNode tail;
public LRUCache(int capacity) {
this.capacity = capacity;
dic = new HashMap<>();
head = new ListNode(-1, -1);
tail = new ListNode(-1, -1);
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (!dic.containsKey(key)) {
return -1;
}
ListNode node = dic.get(key);
remove(node);
add(node);
return node.val;
}
public void put(int key, int value) {
if (dic.containsKey(key)) {
ListNode oldNode = dic.get(key);
remove(oldNode);
}
ListNode node = new ListNode(key, value);
dic.put(key, node);
add(node);
if (dic.size() > capacity) {
ListNode nodeToDelete = head.next;
remove(nodeToDelete);
dic.remove(nodeToDelete.key);
}
}
public void add(ListNode node) {
ListNode previousEnd = tail.prev;
previousEnd.next = node;
node.prev = previousEnd;
node.next = tail;
tail.prev = node;
}
public void remove(ListNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
}
Ставь 👍 и забирай 📚 Базу знаний
4 · 392 ·