Сообщения

Игра в камни 3

Источник: https://leetcode.com/problems/stone-game-iii/ Alice и Bob играют с камнями. Несколько камней выложены в рядок. У каждого камня есть своя стоимость stoneValue положительная или отрицательная. Alice и Bob играют по очереди, при этом Alice начинает первая . каждый ход позволяет взять игроку 1, 2 или 3 подряд лежащих камня , с первого доступного в ряду. Счёт каждого игрока - это сумма камней, которые он взял. Начальный счёт = 0. Цель игры: завершить игру (когда не осталось доступных камней) со счётом, превосходящим счёт противника. Если у обоих игроков равный счёт, то получается ничья (tie). Игра продолжается, пока камней не останется. Можно считать, что Alice и Bob играют оптимально . Вернуть "Alice" , если победит Alice; "Bob" , если победит Bob; или "Tie", если ничья . Пример 1: Дано: values = [1,2,3,7] Результат: "Bob" Пояснение : Alice проиграет в любом случае. Её лучший ход, дающий максимальный счёт - это первые три камня: 1...

Флот машин

 Источник: https://leetcode.com/problems/car-fleet/ N машин собираются достичб одной и той же точки назначения на одном и том же маршруте. Точка назначения находится на отметке target миль. Каждая машина i имеет константную скорость speed[i]  (миль/час), и начальную позицию position[i] миль относительно некоторой нулевой точки маршрута к пункту назначения. Машина не может обойти другую машину, но может присоединиться к ней, продолжая движение бампер за бампером с той же скоростью. В этом случае мы считаем расстояние между машинами равно нулю, и эти машины находятся в одной точке. Флот машин - это не пустое множество машин, которые движутся вместе (в одних и тех же точках) с одной и той же скоростью. Одна машина - это тоже флот. Если машина достигает точку назначения одновременно с каким-то флотом, то мы считаем, что она тоже принадлежит этому флоту. Нужно посчитать, сколько отдельных машинных флотов прибудут в точку назначения. Пример: Дано: target = 12 , position = [...

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

Изображение
Дан корень бинарного дерева. Определить, являтеся ли дерево полным. В полном бинарном дереве каждый уровень, за исклением возможно последнего (с листьями), полностью заполен. Если последний уровень не заполнен, то все его элементы занимают все левые позиции. Пример 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)   Идея решения   Переформулируем эту задачу в утилитарном виде. Есть набор коробок разного размера. Порядок коробок не должен меняться, все коробки заранее известны. Кор...