Задача: 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 Node {
    public $key;
    public $value;
    public $next;
    public $prev;

    public function __construct($key, $value) {
        $this->key = $key;
        $this->value = $value;
        $this->next = null;
        $this->prev = null;
    }
}

class LRUCache {
    private $capacity;
    private $dic = [];
    private $head;
    private $tail;
    
    public function __construct($capacity) {
        $this->capacity = $capacity;
        $this->head = new Node(-1, -1);
        $this->tail = new Node(-1, -1);
        $this->head->next = $this->tail;
        $this->tail->prev = $this->head;
    }

    public function get($key) {
        if (!array_key_exists($key, $this->dic)) {
            return -1;
        }
        $node = $this->dic[$key];
        $this->remove($node);
        $this->add($node);
        return $node->value;
    }

    public function put($key, $value) {
        if (array_key_exists($key, $this->dic)) {
            $this->remove($this->dic[$key]);
        }
        $node = new Node($key, $value);
        $this->add($node);
        $this->dic[$key] = $node;
        if (count($this->dic) > $this->capacity) {
            $nodeToDelete = $this->head->next;
            $this->remove($nodeToDelete);
            unset($this->dic[$nodeToDelete->key]);
        }
    }

    private function add($node) {
        $pre = $this->tail->prev;
        $pre->next = $node;
        $node->prev = $pre;
        $node->next = $this->tail;
        $this->tail->prev = $node;
    }

    private function remove($node) {
        $pre = $node->prev;
        $nxt = $node->next;
        $pre->next = $nxt;
        $nxt->prev = $pre;
    }
}

Ставь 👍 и забирай 📚 Базу знаний