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

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

Условие задачи: дается 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
Объяснение: *во вложении

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

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

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

Условие задачи: дается две строки 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

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

Грабители 2

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

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

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

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

Пример:

Ввод: nums = [2,3,2]
Вывод: 3
Объяснение: нельзя грабить первый и третий дома, так как они соседние.

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

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

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

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

Условие задачи: дается доска с целочисленной матрицей 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

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

Нахождение индекс первого вхождения в строку

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

Условие задачи: дается две строки needle и haystack, верните индекс первого появления иглы в стоге сена или -1, если игла не является частью стога сена.

Пример:

Ввод: haystack = "sadbutsad", needle = "sad"
Вывод: 0

Ввод: haystack = "leetcode", needle = "leeto"
Вывод: -1

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

Треугольник наибольшей площади

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

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

Пример:

Ввод: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
Вывод: 2.00000
Объяснение:

Ввод: points = [[1,0],[0,0],[0,1]]
Вывод: 0.50000

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

Наиболее частое слово

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

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

Слова в абзаце не учитывают регистр, и ответ должен быть возвращен в нижнем регистре.

Пример:

Ввод: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"]
Вывод: "ball"

Ввод: paragraph = "a.", banned = []
Вывод: "a"

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

Pow(x, n)

Сложность задачи: Средняя

Условие задачи:
Реализуйте функцию pow(x, n), которая вычисляет x в степени n (т. е. x^n).

Пример:
Ввод: x = 2.00000, n = 10
Вывод: 1024.00000

Ввод: x = 2.10000, n = 3
Вывод: 9.26100

Диапазон данных:
-100.0 < x < 100.0
-231 <= n <= 231-1
-104 <= x^n <= 104

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

То же дерево

Сложность задачи:
Низкая

Условие:
Получив корни двух бинарных деревьев p и q, напишите функцию, проверяющую, совпадают ли они.

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

Примеры (картинки по порядку):
Ввод: p = [1,2,3], q = [1,2,3]
Вывод: true

Ввод: p = [1,2], q = [1,null,2]
Вывод: false

Ввод: p = [1,2,1], q = [1,1,2]
Вывод: false

Ограничения:
Количество узлов в обоих деревьях находится в диапазоне [0, 100].

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

Балансировка бинарного дерева

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

Условие задачи: дается бинарное дерево, определите является ли дерево сбалансированным.

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

Пример:

Ввод: root = [3,9,20,null,null,15,7]
Вывод: true

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

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

Инвертировать бинарное дерево

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

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

Пример:

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

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

Поиск мажоритарного элемента

Условие задачи:
Дан массив nums размера n. Требуется вернуть мажоритарный элемент.

Мажоритарный элемент - это элемент, который появляется более n / 2 раз. Вы можете быть уверены, что мажоритарный элемент всегда существует в массиве.

Примеры:
Ввод: nums = [4,2,4]
Вывод: 4

Ввод: nums = [8, 8, 6, 6, 6, 8, 8]
Вывод: 8

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

Извлечение дубликатов из отсортированного списка II

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

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

Пример:

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

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

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

Сжатие строки

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

Условие задачи: дается массив символов chars, сожмите его, используя следующий алгоритм:

Начинайте с пустой строки s. Для каждой группы последовательных повторяющихся символов в chars:

Если длина группы равна 1, добавьте символ для просмотра.
В противном случае добавьте символ, за которым следует длина группы.
Сжатые строки не должны возвращаться отдельно, а вместо этого должны храниться во входном символьном массиве chars. Обратите внимание, что длина группы, равная 10 или более, будет разделена на несколько символов в chars.

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

Вы должны написать алгоритм, который использует только постоянное дополнительное пространство.

Пример:

Ввод: chars = ["a","a","b","b","c","c","c"]
Вывод: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]

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