Минимальная разница по модулю

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

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

Пример:

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

Ввод: root = [1,0,48,null,null,12,49]
Вывод: 1

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

Ежедневная температура

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

Условие задачи: дается массив, в котором содержатся на температуры за определенный день. Необходимо вернуть массив, такой что будет содержать на i-ой позиции количество дней, которое необходимо выждать, чтобы наступил день теплее. Если такой ситуации не случается, то на i-ой позиции установить 0.

Пример:

Ввод: temperatures = [73,74,75,71,69,72,76,73]
Вывод: [1,1,4,2,1,1,0,0]

Ввод: temperatures = [30,40,50,60]
Вывод: [1,1,1,0]

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

Нахождение существующего пути

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

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

Необходимо определить существует ли корректная дорога между узлом source и destination.

Пример:

Ввод: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Вывод: true
Объяснение: *во вложении

Ввод: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Вывод: false

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

Отрезки пересечения отрезков

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

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

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

Пример:

Ввод: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
Вывод: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Ввод: firstList = [[1,3],[5,9]], secondList = []
Вывод: [ ]

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

Разворот строки II

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

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

Если есть несколько символов больших k, необходимо развернуть все из них. Если есть меньше, чем 2k символов, но при этом больше или равно k символов, то необходимо оставить все как есть.

Пример:

Ввод: s = "abcdefg", k = 2
Вывод: "bacdfeg"

Ввод: s = "abcd", k = 2
Вывод: "bacd"

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

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

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

Условие задачи: имеется ненаправленное дерево, соединяющее 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]

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

Раскладка костей

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

Условие задачи: есть два типа костей: типа domino и типа tromino.

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

При укладке плитки каждый квадрат должен быть покрыт плиткой. Две плитки различны тогда и только тогда, когда на доске есть две смежные в 4 направлениях ячейки, такие, что ровно в одной из плиток оба квадрата заняты плиткой.

Пример:

Ввод: n = 3
Вывод: 5
Объяснение: *во вложении

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

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

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

Условие задачи: дается проиндексированный с нуля целочисленный массив 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
Объяснение: *во вложении

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

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

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

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

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

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

Пример:

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

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

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

Гармоничная подпоследовательность наибольшей длины

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

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

Дается целочисленный массив nums, верните длину его самой длинной гармоничной подпоследовательности среди всех его возможных подпоследовательностей.

Подпоследовательность массива - это последовательность, которая может быть получена из массива путем удаления некоторых элементов или вообще без них без изменения порядка остальных элементов.

Пример:

Ввод: nums = [1,3,2,2,5,2,3,7]
Вывод: 5
Объяснение: [3,2,2,2,3] - гармоничная подпоследовательность наибольшей длины.

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

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

Минимальная сумма индексов двух списков

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

Условие задачи: дается два массива строк list1 и list2, найдите общие строки с наименьшей суммой индексов.

Общая строка - это строка, которая появилась как в list1, так и в list2.

Общая строка с наименьшей суммой индексов - это общая строка, такая, что если она появилась в list1[i] и list2[j], то i + j должно быть минимальным значением среди всех других общих строк.

Возвращает все общие строки с наименьшей суммой индексов. Верните ответ в любом порядке.

Пример:

Ввод: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]
Вывод: ["Shogun"]

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

Распределение конфет

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

Условие задачи: у Алисы есть конфеты, где i-я конфета относится к типу Candytype[i]. Алиса заметила, что начала набирать вес, поэтому обратилась к врачу.

Доктор посоветовал Алисе съесть только n / 2 конфет, которые у нее есть (n всегда четное). Алисе очень нравятся ее конфеты, и она хочет съесть максимальное количество различных видов конфет, все еще следуя советам врача.

Учитывая целочисленный массив candyType длины n, верните максимальное количество различных типов конфет, которые она может съесть, если она съест только n / 2 из них.

Пример:

Ввод: candyType = [1,1,2,2,3,3]
Вывод: 3
Объяснение: Алиса может съесть только 6/2 = 3 конфеты. Поскольку существует только 3 вида, она может съесть по одному из каждого вида.

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

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

Заправочная станция

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

Условие задачи: вдоль кольцевого маршрута расположено n заправочных станций, где количество газа на i-й станции равно gas[i].

У вас есть автомобиль с неограниченным запасом бензина, и проезд от i-й станции до следующей (i + 1)-й станции обходится в стоимость [i] бензина. Вы начинаете путешествие с пустым баком на одной из заправочных станций.

Учитывая два целочисленных массива gas и cost, верните индекс начальной заправочной станции, если вы можете объехать круг один раз по часовой стрелке, в противном случае верните -1. Если существует решение, оно гарантированно будет уникальным

Пример:

Ввод: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Вывод: 3

Ввод: gas = [2,3,4], cost = [3,4,3]
Вывод: -1

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

Количество точек на прямой

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

Условие задачи: дается массив точек, где точки [i] = [xi, yi] представляют точку на плоскости X-Y, верните максимальное количество точек, которые лежат на одной прямой.

Пример:

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

Ввод: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Вывод: 4

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

Минимальная разница между узлами бинарного дерева

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

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

Пример:

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

Ввод: root = [1,0,48,null,null,12,49]
Вывод: 1

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