Сумма расстояний в дереве

Сложность: Тяжёлая

Условие задачи: имеется ненаправленное дерево, соединяющее n узлов пронумерованных от 0 до n-1.

Дается также целое число n, а также массив ребер, соединяющих узлы.

Необходимо вычислить массив, состоящий из длин между узлами, находящимися в исходном массиве edges.

Пример:

Ввод: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Вывод: [8,12,6,10,10,10]
Объяснение:

Дистанция между узлом состоит из следующих длин:
dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5) = 1 + 1 + 2 + 2 + 2 = 8.

Решение задачи

Партиционированние массива

Сложность: Лёгкая

Условие задачи: дается целочисленный массив, содержащий 2n-чисел, надо сгруппировать эти числа в n-пар (a1, b1), (a2, b2), ..., (an, bn), таких что сумма min(ai, bi) для всех i - максимальна. Необходимо вычислить максимальную сумму.

Пример:

Ввод: nums = [1,4,3,2]
Вывод: 4
Объяснение:

Комбинации пар :
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4 (максимум).

Решение задачи

Длиннейшая подпоследовательность с ограниченной суммой

Сложность: Лёгкая

Условие задачи: дается целочисленный массив nums длины n и целочисленный массив queries длины m.

Необходимо вернуть ответ в массиве, где i-ый элемент массива - максимальная длина подпоследовательности, которую можно вычислить в массиве nums, так что сумма этих элементов будет не больше, чем queries[i].

Пример:

Ввод: nums = [4,5,2,1], queries = [3,10,21]
Вывод: [2,3,4]

Решение задачи

Извлечение камней для минимизации общего количества

Сложность: Средняя

Условие задачи: дается проиндексированный с нуля целочисленный массив piles, где каждое число отображает количество камней в соответствующей куче. Помимо этого дается также целое число k - количество раз, которое надо применить операцию: выбрать кучу камней и извлечь из нее floor(piles[i] / 2) камней.

Данную операцию можно производить над одной и той же кучей несколько раз подряд.

Необходимо вычислить минимальное количество итогового оставшегося количества камней после применения данной операции k-раз.

Пример:

Ввод: piles = [5,4,9], k = 2
Вывод: 12

Ввод: piles = [4,3,6,7], k = 3
Вывод: 12

Решение задачи

Максимальное количество сумок, полностью заполненных камнями

Сложность: Средняя

Условие задачи: дается n-сумок, пронумерованных с нуля. Дается также два массива, проиндексированных аналогичным образом: capacity и rocks. i-а сумка может вмещать capacity[i] камней и в текущий момент содержит уже rocks[i] каменей. Помимо этого дается еще additionalRocks, число камней, которые можно добавить в произвольную сумку.

Необходимо вычислить максимальное количество сумок, которое получится при ситуации, когда все дополнительные камни размещены.

Пример:

Ввод: capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2
Вывод: 3

Ввод: capacity = [10,2,2], rocks = [2,2,0], additionalRocks = 100
Вывод: 3

Решение задачи

Разность по потомкам

Сложность: Лёгкая

Условие задачи: дается корень двоичного дерева, верните сумму наклона каждого узла дерева.

Наклон узла дерева - это абсолютная разница между суммой всех значений узла левого поддерева и всех значений узла правого поддерева. Если узел не имеет левого дочернего элемента, то сумма значений узла левого поддерева обрабатывается как 0. Правило аналогично, если у узла нет правого дочернего элемента.

Пример:

Ввод: root = [1,2,3]
Вывод: 1

Ввод: root = [4,2,9,3,5,null,7]
Вывод: 15
Объяснение: *во вложении

Решение задачи

Самый длинный путь с разными соседними символами

Сложность: Тяжёлая

Условие задачи: дано дерево (т.е. связанный неориентированный граф, не имеющий циклов) с корнем в узле 0, состоящее из n узлов, пронумерованных от 0 до n - 1. Дерево представлено родительским массивом с индексом 0 размера n, где родительский элемент[i] является родительским элементом узла i. Поскольку узел 0 является корневым, родительский элемент[0] == -1.

Вам также выдаются строки длиной n, где s[i] - символ, присвоенный узлу i.

Возвращает длину самого длинного пути в дереве таким образом, чтобы ни одной паре соседних узлов пути не был присвоен один и тот же символ.

Пример:

Ввод: parent = [-1,0,0,1,1,2], s = "abacbe"
Вывод: 3

Ввод: parent = [-1,0,0,0], s = "aabc"
Вывод: 3

Решение задачи

Петля в связном списке II

Сложность: Средняя

Условие задачи: дан связный список, необходимо вернуть позицию элемента, с которого начинается цикл, если же цикл отсутствует, то надо вернуть null.

Пример:

Ввод: head = [3,2,0,-4], pos = 1
Вывод: последний элемент зацикливается на элементе с индексом
1*.

* соответствующий список проиллюстрирован на картинке.

Решение задачи

Дорогие подписчики, поздравляю вас с наступающим, а кого-то уже и с наступившим Новом Годом! Пусть 2024 станет для вас чем-то особенным и незабываемым.

Быки и коровы

Сложность: Средняя

Условие задачи: разыгрывается партия, в которой мы просим оппонента угадать число. После первой попытки мы мы говорим другу количество отданных цифр и неотгаданных.

Быки - правильные цифры, находящиеся на нужных позициях.

Коровы - правильные числа, но находящиеся на соответствующих позициях.

Задача - выдать подсказку в формате "xAyB", где x - количество быков, y - количество коров.

Пример:

Ввод: secret = "1807", guess = "7810"
Вывод: "1A3B"
Объяснение:

Ввод: secret = "1123", guess = "0111"
Вывод: "1A1B"

Решение задачи

Максимальное среднее подмассива

Сложность: Лёгкая

Условие задачи: дается целочисленный массив nums, состоящий из n элементов и целого числа k.

Найдите непрерывный подмассив, длина которого равна k, который имеет максимальное среднее значение, и верните это значение. Будет принят любой ответ с ошибкой вычисления менее 10-5.

Пример:

Ввод: nums = [1,12,-5,-6,50,3], k = 4
Вывод: 12.75000
Объяснение:

Ввод: nums = [5], k = 1
Вывод: 5.00000

Решение задачи

Строка-перевертыш

Сложность: Лёгкая

Условие задачи: дается две строки s и goal, верните true тогда и только тогда, когда s может стать goal после некоторого количества смен в субботу.

Сдвиг на s состоит в перемещении крайнего левого символа s в крайнюю правую позицию.

Например, если s = "abcde", то после одной смены это будет "bcdea".

Пример:

Ввод: s = "abcde", goal = "cdeab"
Вывод: true

Ввод: s = "abcde", goal = "abced"
Вывод: false

Решение задачи

Суммы подмассивов, кратные K

Сложность: Средняя

Условие задачи: дается целочисленный массив nums и целое число k, верните количество непустых подмассивов, сумма которых делится на k.

Подмассив - это непрерывная часть массива.

Пример:

Ввод: nums = [4,5,0,-2,-3,1], k = 5
Вывод: 7
Объяснение: [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Ввод: nums = [5], k = 9
Вывод: 0

Решение задачи

Восстановить IP

Сложность: Средняя

Условие задачи: действительный IP-адрес состоит ровно из четырех целых чисел, разделенных одиночными точками. Каждое целое число находится в диапазоне от 0 до 255 (включительно) и не может содержать начальных нулей.

Например, "0.1.2.201" и "192.168.1.1" являются допустимыми IP-адресами, но "0.011.255.245", "192.168.1.312" и "192.168@1.1 " являются недопустимыми IP-адресами.
Учитывая строку s, содержащую только цифры, верните все возможные действительные IP-адреса, которые могут быть сформированы путем вставки точек в s. Вам не разрешается изменять порядок или удалять какие-либо цифры в s. Вы можете вернуть действительные IP-адреса в любом порядке.

Пример:

Ввод: s = "25525511135"
Вывод: ["255.255.11.135","255.255.111.35"]

Ввод: s = "0000"
Вывод: ["0.0.0.0"]

Решение задачи

Разделение на палиндромы

Сложность: Средняя

Условие задачи: дается строка, необходимо разделить исходную строку таким образом, чтобы всевозможные подстроки были палиндромами.

Пример:

Ввод: s = "aab"
Вывод: [["a","a","b"],["aa","b"]]
Объяснение:

Ввод: s = "a"
Вывод: s = "a"

Решение задачи

Обход по времени

Сложность: Средняя

Условие задачи: предоставляется сеть из n узлов, помеченных от 1 до n. Вам также дается время, список времени прохождения в соответствии с указаниями ребер times[i] = (ui, vi, wi), где ui - исходный узел, vi - целевой узел, а wi - время, необходимое сигналу для прохождения от источника до цели.

Мы отправим сигнал с заданного узла k. Необходимо вернуть минимальное время, необходимое для приема сигнала всеми n узлами. Если все n узлов не могут принять сигнал, верните значение -1.

Пример:

Ввод: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Вывод: 2

Ввод: times = [[1,2,1]], n = 2, k = 1
Вывод: 1

Решение задачи

Глубина N-арного дерева

Сложность: Лёгкая

Условие задачи: дается n-арное дерево, найдите его максимальную глубинуину.

Максимальная глубина - это количество узлов вдоль самого длинного пути от корневого узла до самого дальнего конечного узла.

Сериализация входных данных Nary-Tree представлена в порядке обхода их уровней, каждая группа дочерних элементов разделена нулевым значением (см. примеры).

Пример:

Ввод: root = [1,null,3,2,4,null,5,6]
Вывод: 3

Ввод: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Вывод: 5

Решение задачи

Змеи и лестницы

Сложность: Средняя

Условие задачи: дается доска с целочисленной матрицей n x n, где ячейки помечены от 1 до n2 в стиле бустрофедона, начиная с нижнего левого края доски (т.е. доска [n - 1] [0]) и чередуя направление каждой строки.

Вы начинаете с квадрата 1 на доске. В каждом ходе, начиная с квадратного поворота, выполняйте следующее:

Выберите целевой квадрат рядом с меткой в диапазоне [curr + 1, min(curr + 6, n2)].

Если рядом есть змея или лестница, вы должны перейти к месту назначения этой змеи или лестницы. В противном случае вы переходите к следующему.
Игра заканчивается, когда вы достигаете квадрата n2.

Верните наименьшее количество ходов, необходимых для достижения квадрата n2. Если добраться до квадрата невозможно, верните значение -1.

Пример:

Ввод: board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]
Вывод: 4

Ввод: board = [[-1,-1],[-1,3]]
Вывод: 1

Решение задачи

Найти ближайший узел к заданным двум узлам

Сложность: Средняя

Условие задачи: дается ориентированный граф из n узлов, пронумерованных от 0 до n - 1, где каждый узел имеет не более одного исходящего ребра.

Граф представлен заданными 0-индексированными ребрами массива размера n, указывающими на то, что существует направленное ребро от узла i к ребрам узла[i]. Если нет исходящего ребра из i, то ребра[i] == -1.

Вам также даны два целых числа node1 и node2.

Возвращает индекс узла, до которого можно добраться как из узла 1, так и из узла 2, таким образом, чтобы максимальное расстояние от узла 1 до этого узла и от узла 2 до этого узла было сведено к минимуму. Если ответов несколько, верните узел с наименьшим индексом, а если возможного ответа не существует, верните -1.

Обратите внимание, что ребра могут содержать циклы.

Пример:

Ввод: edges = [2,2,3,-1], node1 = 0, node2 = 1
Вывод: 2

Ввод: edges = [1,2,-1], node1 = 0, node2 = 2
Вывод: 2

Решение задачи