Задача: 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), затем удалите соответствующий ключ из хэш-карты. 😎 Решение: public class Node { public int key { get; set; } public int value { get; set; } public Node next { get; set; } public Node prev { get; set; } public Node(int key, int value) { this.key = key; this.value = value; } } public class LRUCache { private int capacity; private Dictionary<int, Node> dic; private Node head; private Node tail; public LRUCache(int capacity) { this.capacity = capacity; dic = new Dictionary<int, Node>(); head = new Node(-1, -1); tail = new Node(-1, -1); head.next = tail; tail.prev = head; } public int Get(int key) { if (!dic.ContainsKey(key)) { return -1; } Node node = dic[key]; Remove(node); Add(node); return node.value; } public void Put(int key, int value) { if (dic.ContainsKey(key)) { Node oldNode = dic[key]; Remove(oldNode); } Node node = new Node(key, value); dic[key] = node; Add(node); if (dic.Count > capacity) { Node nodeToDelete = head.next; Remove(nodeToDelete); dic.Remove(nodeToDelete.key); } } private void Add(Node node) { Node previousEnd = tail.prev; previousEnd.next = node; node.prev = previousEnd; node.next = tail; tail.prev = node; } private void Remove(Node node) { node.prev.next = node.next; node.next.prev = node.prev; } } Ставь 👍 и забирай 📚 Базу знаний