#ЛитКод
Задача: 642. Design Search Autocomplete System

Разработайте свою реализацию круговой двусторонней очереди (deque). Реализуйте класс MyCircularDeque: MyCircularDeque(int k) Инициализирует deque с максимальным размером k. boolean insertFront() Добавляет элемент в переднюю часть Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean insertLast() Добавляет элемент в заднюю часть Deque. Возвращает true, если операция выполнена успешно, или false в противном случае. boolean deleteFront() Удаляет элемент из передней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean deleteLast() Удаляет элемент из задней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. int getFront() Возвращает передний элемент из Deque. Возвращает -1, если Deque пуст. int getRear() Возвращает последний элемент из Deque. Возвращает -1, если Deque пуст. boolean isEmpty() Возвращает true, если Deque пуст, или false в противном случае. boolean isFull() Возвращает true, если Deque полон, или false в противном случае.

Пример:

Input
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 2, true, true, true, 4]

👨‍💻 Алгоритм:

1⃣Инициализация и проверка состояний
Реализуйте конструктор для инициализации кольцевой двусторонней очереди заданного размера и методы для проверки пустоты и полноты очереди.

2⃣Операции вставки
Реализуйте методы вставки элементов в переднюю и заднюю части очереди с учетом кольцевой структуры.

3⃣Операции удаления
Реализуйте методы удаления элементов из передней и задней частей очереди с учетом кольцевой структуры и методы для получения переднего и заднего элементов очереди.

😎 Решение:

class TrieNode {
    public $children;
    public $count;

    public function __construct() {
        $this->children = [];
        $this->count = [];
    }
}

class AutocompleteSystem {
    private $root;
    private $prefix;

    function __construct($sentences, $times) {
        $this->root = new TrieNode();
        $this->prefix = "";
        for ($i = 0; $i < count($sentences); $i++) {
            $this->add($sentences[$i], $times[$i]);
        }
    }

    private function add($sentence, $count) {
        $node = $this->root;
        for ($i = 0; $i < strlen($sentence); $i++) {
            $char = $sentence[$i];
            if (!isset($node->children[$char])) {
                $node->children[$char] = new TrieNode();
            }
            $node = $node->children[$char];
            if (!isset($node->count[$sentence])) {
                $node->count[$sentence] = 0;
            }
            $node->count[$sentence] += $count;
        }
    }

    function input($c) {
        if ($c == '#') {
            $this->add($this->prefix, 1);
            $this->prefix = "";
            return [];
        }

        $this->prefix .= $c;
        $node = $this->root;
        for ($i = 0; $i < strlen($this->prefix); $i++) {
            $char = $this->prefix[$i];
            if (!isset($node->children[$char])) {
                return [];
            }
            $node = $node->children[$char];
        }

        $pq = [];
        foreach ($node->count as $sentence => $count) {
            $pq[] = [$sentence, $count];
        }

        usort($pq, function($a, $b) {
            if ($a[1] == $b[1]) {
                return strcmp($a[0], $b[0]);
            }
            return $b[1] - $a[1];
        });

        $result = [];
        for ($i = 0; $i < min(3, count($pq)); $i++) {
            $result[] = $pq[$i][0];
        }

        return $result;
    }
}

👉Новости 👉Платформа