Задача: 642. Design Search Autocomplete System
Сложность: hard

Разработайте свою реализацию круговой двусторонней очереди (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 {
    var children = [Character: TrieNode]()
    var count = [String: Int]()
}

class AutocompleteSystem {
    private var root = TrieNode()
    private var prefix = ""

    init(_ sentences: [String], _ times: [Int]) {
        for i in 0..<sentences.count {
            add(sentences[i], times[i])
        }
    }

    private func add(_ sentence: String, _ count: Int) {
        var node = root
        for char in sentence {
            if node.children[char] == nil {
                node.children[char] = TrieNode()
            }
            node = node.children[char]!
            node.count[sentence, default: 0] += count
        }
    }

    func input(_ c: Character) -> [String] {
        if c == "#" {
            add(prefix, 1)
            prefix = ""
            return []
        }

        prefix.append(c)
        var node = root
        for char in prefix {
            if node.children[char] == nil {
                return []
            }
            node = node.children[char]!
        }

        let pq = node.count.sorted { lhs, rhs in
            if lhs.value == rhs.value {
                return lhs.key < rhs.key
            }
            return lhs.value > rhs.value
        }

        return Array(pq.prefix(3)).map { $0.key }
    }
}

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