Сообщения

Показаны сообщения с ярлыком "Дизайн структуры данных"

Взвешенная сумма вложенного списка

Источник: https://leetcode.com/problems/nested-list-weight-sum-ii/ Дан вложенный список целых чисел. Подсчитать сумму всех его элементов, взвешенных их глубиной. Каждый элемент вложенного списка может быть целым числом или вложенным списком - тоже состоящий из целых чисел и вложенных списков. Вес увеличивается снизу вверх, то есть "листьевые" целые элементы имеют вес 1. А корень имеет наибольший вес. Как изменится алгоритм, если вес увеличивается от корня к листьям? Пример 1: Дано: [[1,1],2,[1,1]] Результат: 8 Пояснение: Четыре единицы находятся на глубине 1, а 2 - на глубине 2 . Поэтому сумма считается: 1*1 + 1*1 + 2*2 + 1*1 + 1*1 = 8. Пример 2: Дано: [1,[4,[6]]] Результат: 17 Поясненеи: Число 1 находится на глубине 3, 4 - на глубине 2, 6 - на глубине 1. Поэтому сумма считается: 1*3 + 4*2 + 6*1 = 17. Есть некоторый класс NestedInteger, со следующим интерфейсом: /**  * // Интерфейс для вложенного списка, не нужно его имплементировать  *  * public interface NestedIn...

LRU-кэш

Источник: https://leetcode.com/problems/lru-cache/ Создайте структуру данных для  Least Recently Used (LRU) cache . Эта структура поддерживает две операции: get и put . get(key)   - извлекает значение (всегда положительное) по ключу key, если ключ присутствует в кэше, а в противном случае возвращает -1. put(key, value)   - помещает или изменяет значение по ключу.  Когда кэш достигает своей вместимости, наименее используемые элемент можно удалить и поместить новый элемент. Кэш инициализируется положительной вместимостью. Сделайте так, чтобы обе операции выполнялись за время со сложностью O(1) , то есть за константу. Пример 1: Входные данные ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] Результат [null, null, null, 1, null, -1, null, -1, 3, 4] Пояснение LRUCache lRUCache = new LRUCache(2);...

Волшебный словарь

Нужно создать структуру "волшебный" словарь с методами buildDict и search . Для метода buildDict будет дан список неповторящихся слов, которые будут использованы для создания словаря. Для метода search будет дано одно слово, оно может совпадать с каким-то словом из словаря или отличаться от слова в словаре на одну букву . Пример: Input: buildDict(["hello", "leetcode"]), Output: Null Input: search("hello"), Output: False Input: search("hhllo"), Output: True Input: search("hell"), Output: False Input: search("leetcoded"), Output: False Примечания: Мы предполагаем, что все слова в словаре написаны маленькими буквами английского алфавита a-z . Словарь может быть очень большим. Идея решения В процессе инициализации словаря мы можем рассортировать слова по "ведрам" (buckets), где каждое ведро содержит слова определенной длины. Когда поступает слово на поиск, мы берем список слов той же...