#ЛитКод
Задача:
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;
}
}👉
Новости 👉
Платформа
