Ключи и комнаты

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

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

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

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

Пример:

Ввод: rooms = [[1],[2],[3],[]]
Вывод: true
Объяснение: из 0 комнаты можно попасть в 1, из 1 во 2, из 2 в 3.

Ввод: rooms = [[1,3],[3,0,1],[2],[0]]
Вывод: false

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

Форматирование

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

Условие задачи: дается номер водительского удостоверения, представленный строкой. Символы в номере могут быть разбиты на n+1 групп. Также дается число k.

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

Пример:

Ввод: s = "5F3Z-2e-9-w", k = 4
Вывод: "5F3Z-2E9W"
Объяснение:

Ввод: s = "2-5g-3-J", k = 2
Вывод: s = "2-5g-3-J", k = 2

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

Сумма на отрезке

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

Условие задачи: дается бинарное дерево поиска, дается два числа low и high, необходимо посчитать сумму узлов дерева, находящихся в пределах данного отрезка [low, high].

Пример:

Ввод: root = [10,5,15,3,7,null,18], low = 7, high = 15
Вывод: 32
Объяснение: в данный отрезок входят числа 7, 10, 15.

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

Общая подпоследовательность наибольшей длины

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

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

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

Пример:

Ввод: text1 = "abcde", text2 = "ace"
Вывод: 3
Объяснение: "ace"

Ввод: text1 = "abc", text2 = "def"
Вывод: 0

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

Выход из лабиринта

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

Условие задачи: на вход подается двумерный массив, отражающий карту лабиринта ('.' - пустая ячейка, ' + ' - стена). Также на вход подается массив со входом, обозначающий изначальное положение, откуда будет искаться выход.

Двигаться можно лишь в четырёх направлениях: лево, право, верх, низ.

Необходимо вычислить количество шагов до ближайшего выхода или же вернуть -1 в случае отсутствия такового.

Пример:

Ввод: maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
Вывод: 1
Объяснение: *во вложении

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

Максимальное число из 6 и 9

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

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

Пример:

Ввод: num = 9669
Вывод: 9969

Ввод: num = 9996
Вывод: 9999

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

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

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

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

Необходимо определить существует ли корректная дорога между узлом 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

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

Наиближайшая сумма трёх

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

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

Каждый массив имеет единственное решение.

Пример:

Ввод: nums = [-1,2,1,-4], target = 1
Вывод: 2
Объяснение: (-1 + 2 + 1 = 2)

Ввод: nums = [0,0,0], target = 1
Вывод: 0

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

Проверка схожести половин строки

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

Условие задачи: на вход подается строка четной длины. Далее проводится разделение на две равные части.

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

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

Пример:

Ввод: s = "book"
Вывод: true

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

Максимальное скользящее

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

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

Пример:

Ввод: nums = [1,3,-1,-3,5,3,6,7], k = 3
Вывод: [3,3,5,5,6,7]

Объяснение:
Скользящее на каждой итерации Max
-------------------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

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

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

Столбцы таблицы Excel

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

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

Пример:

Ввод:columnNumber = 1
Вывод: "A"

Ввод: columnNumber = 28
Вывод: "AB"

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

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

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

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

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

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

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

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

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

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

Пример:

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

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

Идеальное число

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

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

Необходимо проверить входное число на идеальность.

Пример:

Ввод: num = 28
Вывод: true
Объяснение: 28 = 1 + 2 + 4 + 7 + 14

Ввод: num = 7
Вывод: false

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

Минимальное количество ребер

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

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

Необходимо найти наименьшее количество ребер в графе такое что, можно было бы обойти все узлы.

Пример:

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

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

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

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

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

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

Пример:

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

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

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

Количество возрастающих подпоследовательностей наибольшей длины

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

Условие задачи: дан массив целых чисел, надо посчитать количество возрастающих подпоследовательностей наибольшей длины. Подпоследовательность (ее элементы) должна строго возрастать.

Пример:

Ввод: nums = [1,3,5,4,7]
Вывод: 2
Объяснение: есть две возрастающие подпоследовательности одинаковой длины: [1, 3, 4, 7] и [1, 3, 5, 7]

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

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

Наидлиннейший общий префикс

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

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

Пример:

Ввод: strs = ["flower","flow","flight"]
Вывод: "fl"

Ввод: strs = ["dog","racecar","car"]
Вывод: ""
Объяснение: в данных строках нет общего префикса

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

Является ли строка подпоследовательностью

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

Условие задачи: даны две строки s и t, верните true, если s - подпоследовательность строки t, false - в ином случае.

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

Пример:

Ввод: s = "abc", t = "ahbgdc"
Вывод: true

Ввод: s = "axc", t = "ahbgdc"
Вывод: false

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

Мокрые бандиты

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

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

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

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

Пример:

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

Объяснение: Грабим 1-ый дом (money = 1), а после навещаем 3-ий дом (money = 3).
Суммарный куш: 1 + 3 = 4.

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

Монетообменик

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

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

Необходимо высчитать наименьшее количество монет, которыми можно получить необходимую сумму или вернуть -1 в случае невозможности.

Количество монет не ограничено.

Пример:

Ввод: coins = [1,2,5], amount = 11
Вывод: 3
Объяснение: 11 = 5 + 5 + 1

Ввод: coins = [2], amount = 3
Вывод: -1

Ввод: coins = [1], amount = 0
Вывод: 0


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