Сообщения

Проверить полноту двоичного дерева

Изображение
Дан корень бинарного дерева. Определить, являтеся ли дерево полным. В полном бинарном дереве каждый уровень, за исклением возможно последнего (с листьями), полностью заполен. Если последний уровень не заполнен, то все его элементы занимают все левые позиции. Пример 1: Дано: root = [1,2,3,4,5,6] Результат: true Пояснение: Каждый уровень дерева, за исключением нижнего, заполнен. Самый нижний уровень имеет пробелы только справа. Пример 2: Дано: root = [1,2,3,4,5,null,7] Результат: false Пояснение: Узел с числом 7 следует за "дыркой", которая находится левее его. Ограничения: Количество вершин в дереве находится в интервале [1, 100] . 1 <= Node.val <= 1000 Идея решения Будем обходить дерево по BFS, и на каждом уровне будем добавлять в очередь левое и правое поддерево рассматриваемой вершины, даже если они нулевые.  Если дерево полное, то после рассмотрения всех вершин в очереди останутся только нулевые элементы. В противном случае, дерево не полное, а с "дырками...

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

Источник: 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...

Фотокамеры в двоичном дереве

Изображение
Дано двоичное дерево, нам нужно установить в его узлах фотокамеры. Камера в каждом узле мониторит сам узел, его родителя и его непосредственных детей. Вычислить минимальное колчиество камер, которыми можно промониторить всё дерево. Пример 1: Дано: [0,0,null,0,0] Результат: 1 Пояснение: Одной камеры достаточно, чтобы промониторить все узлы дерева, если установить её так, как показано на рисунке. Пример 2: Дано: [0,0,null,0,null,0,null,null,0] Результат: 2 Пояснение: По крайней мере 2 камеры нужны, чтобы мониторить всё дерево. На рисунке показана однеа из конфигураций расположения камер. Примечания: Число узлов в дереве варбируется в интервале [1, 1000] . Все узлы дерева имеют значение 0 . Идея решения  Рассмотрим "внутренний" (не корневой и не листовой) узел в дереве. Он может мониториться камерой в родителе, в себе, в своих 2 детях. Итого: 4 узла задействованы. Рассмотрим корневой узел дерева.. Он монтирится двумя детьми и собой. Итого: 3 узла задействованы. Расммотрим...

Следующий правый указатель в каждой вершине дерева

Изображение
 Дано бинарное дерево: struct Node { int val; Node *left; Node *right; Node *next; } Заполнить поле next так, чтобы вершина дерева указывала на соседнюю вершину справа, если та существует. Если же никакой вершины справа не существует, то указательnext принимает значение NULL. Изначально все next указатели имеют значение NULL. Ограничение: можно использовать константный объём (не зависящий от размера лерева) дополнительной памяти. Пример: Дано: root = [1,2,3,4,5,null,7] Результат: [1,#,2,3,#,4,5,7,#] Объяснение: Исходное бинарное дерево на рисунке A. Результат на рисунке B: каждая вершина указывает на соседа справа, если он существует. А если не существует, то указывает на NULL. Сериализованный результат выведен в порядке уровней дерева, где уровни разделены символом #. Внутри уровня его элементы указаны слева направо. Идея решения Нам нужно обойти все "этажи" дерева и выстроить в цепочку элементы дерева, находящиеся на одном "этаже". Самый правый элемент ...

Разбить массив на m подмассивов и минимизировать максимальную сумму

Источник:  https://leetcode.com/problems/split-array-largest-sum/ Дан массив nums состоящий из целочисленных положитльных элементов, и дано целое число m . Нужно разделить этот массив на m непустых непрерывных подмассивов. При этом самая максимальная сумма элементов в этих подмассивах должна быть минимизирована. Пример 1: Дано: nums = [7,2,5,10,8], m = 2 Результат: 18 Пояснение: Можно разбить массив на 2 подмассива четырьмя способами. Но мы выберем разбиение на [7,2,5] и [10,8], потому что именно здесь максимальная сумма = 18, и она минимальна по сравнению с другими разбиениями. Пример 2: Дано : nums = [1,2,3,4,5], m = 2 Результат : 9 Пример 3: Дано : nums = [1,4,4], m = 3 Результат : 4 Ограничения: 1 <= nums.length <= 1000 0 <= nums[i] <= 10 6 1 <= m <= min(50, nums.length)   Идея решения   Переформулируем эту задачу в утилитарном виде. Есть набор коробок разного размера. Порядок коробок не должен меняться, все коробки заранее известны. Кор...

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);...

Число подмассивов, в которых сумма элементов равна k

Дан целочисленный массив и целое число k . Найти количество непрерывных подмассивов таких, что сумма их элементов равна k . Пример 1: Дано: nums = [1,1,1], k = 2 Результат: 2 Условия: Длинна массива находится в диапазоне [1, 20,000]. Элементы массива находятся в диапазоне [-1000, 1000], число k - в диапазоне [-1e7, 1e7]. Идея решения Если кумулятивная сумма (пусть s u m [ i ] - это сумма с нулевого до i^{th} i t h индекса ) одинакова для индексов i и j, значит, сумма между этими двумя индексами равна нулю. А если суммы в индексах i i и  j j таковы, что sum[i] - sum[j] = k s u m [ i ] − s u m [ j ] = k , значит, сумма элементов между индексами i i   and   j j равна k k . Создадим хэшмап map m a p , чтобы хранить кумулятивные суммы для всех индексов, вместе с количеством того, сколько раз мы посчитали эту сумму . То есть это пары (sum_i, no. of occurences of sum_i) ( s u m i ​ , n o . o f o c c u r e n c e s o f s u m i ​ ) . Каждый раз, когда мы встречаем ...