Змейка из машин

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

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

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

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

Змейка из машин - группа нескольких или одной машины, достигающих одновременно целевого пункта (расстояние между машинами в одной змейке не учитывается).

Необходимо вычислить количество таких змеек.

Пример:

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

Ввод: target = 10, position = [3], speed = [3]
Вывод: 1

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

Уродливое число

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

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

Надо проверить, является ли подаваемое число уродливым.

Пример:

Ввод: n = 6
Вывод: true
Объяснение: 6 = 2 × 3

Ввод: n = 14
Вывод: false

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

Содержание дубликатов II

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

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

- nums[i] == nums[j];
- abs(i - j) <= k.

Пример:

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

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

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

Стак через очередь

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

Условие задачи: необходимо реализовать стркутуру "последний зашел - первый вышел" используя только две очереди. Реализованная струкутура должна поддерживать функции обычного стака (добавления в стак, удаление верхнего элемента стака, возврат верхнего элемента стака, проверка на наличие элемнтов в стаке).

Пример:

Ввод: ["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Вывод: [null, null, null, 2, 2, false]

Объяснение:
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

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

Степень двойки

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

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

Пример:

Ввод: n = 1
Вывод: true

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

Путь минимальной суммы

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

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

Двигаться можно лишь вправо и вниз.

Пример:

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

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

Сводные диапазоны

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

Условие задачи: дается массив из уникальных целых чисел цисел. Срез [a,b] - включает в себя множество значений из данного отрезка включительно.

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

• "a->b" if a != b
• "a" if a == b

Пример:

Ввод: nums = [0,1,2,4,5,7]
Вывод: ["0->2","4->5","7"]

Объяснение:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

Ввод: nums = [0,2,3,4,6,8,9]
Вывод: ["0","2->4","6","8->9"]

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

Идеальные квадраты

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

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

Пример:

Ввод: n = 12
Вывод: 3
Объяснение: 12 = 4 + 4 + 4.

Ввод: n = 13
Вывод: 2

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

Перестановки II

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

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

Пример:

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

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

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

Поиск слова

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

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

Слово можно составлять из соседей справа, слева, сверху или снизу.

Пример:

Ввод: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Вывод: true
Объяснение: *во вложении

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

Заливка

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

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

Также даются три числа sr, sc, color. Надо осуществить заливку, начиная с image[sr][sc].

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

Пример:

Ввод: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Вывод: [[2,2,2],[2,2,0],[2,0,1]]

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

Сумма минимумов подмассивов

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

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

Пример:

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

Объяснение:
Подмассивы: [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4], минимумы этих подмассивов: 3, 1, 2, 4, 1, 1, 2, 1, 1, 1, которые в сумме дают 17.

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

Swap Adjacent in LR String

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

Условие задачи:
В строке, состоящей из символов «L», «R» и «X», например «RXXLRXRXL», перемещение состоит либо в замене одного вхождения «XL» на «LX», либо в замене одного вхождения «RX» на "ХР". Учитывая начальную строку и конец конечной строки, вернуть True тогда и только тогда, когда существует последовательность ходов для преобразования одной строки в другую.

Пример:
Ввод: start = "RXXLRXRXL", end = "XRLXXRRLX"
Вывод: true
Объяснение: Мы можем преобразовать начало в конец, выполнив следующие шаги:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX

Ввод: start = "X", end = "L"
Вывод: false

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

Пути в бинарном дереве

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

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

Пример:

Ввод: root = [1,2,3,null,5]
Вывод: ["1->2->5","1->3"]

Ввод: root = [1]
Вывод: ["1"]

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

Подсчет подостровов

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

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

Острова на второй решетке рассматриваются как подострова только в случае полного соответствия отображения с первой решетки.

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

Пример:

Ввод: grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
Вывод: 3
Объяснение:

Ввод: grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1,1,1,1,1],[1,0,1,0,1]], grid2 = [[0,0,0,0,0],[1,1,1,1,1],[0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]
Вывод: 2

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

Сдвиг нулей

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

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

Решение должно изменять исходный массив, не используя дополнительной памяти.

Пример:

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

Ввод: nums = [0]
Вывод: [0]

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

Шаблон слова

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

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

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

Пример:

Ввод: pattern = "abba", s = "dog cat cat dog"
Вывод: true

Ввод: pattern = "abba", s = "dog cat cat fish"
Вывод: false

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

Количество провинций

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

Условие задачи: даётся n провинций, какие-то из них соединены между собой, какие-то нет, также соблюдается правило транзитивности: если провинция «1» соединена с провинцией «2», а «2» соединена с «3» провинцией, то и «1» соединена с «3».

Провинцией является совокупность городов, объединённых между собой, но при этом отделенные от других, принадлежащих другим провинциям.

На вход даётся квадратичная матрица, в которой isConnected[i][j] = 1 - соединение между i - ым и j - - ым населенными пунктами (1 - имеется соединение, 0 - отсутствует).

Необходимо вычислить количество провинций.

Пример:

Ввод: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Вывод: 2
Объяснение: *во вложении

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

Взлом замка

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

Условие задачи: даётся замок, состоящий из четырёх вращающихся дисков, на каждом из которых имеется 10 цифр: от 0 до 9. При этом за раз можно перемещать только одно колесо и на одно значение.

Изначально замок находится на значении «0000».

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

Помимо этого даётся шифр открывающий замок, необходимо вычислить наименьшее число перемещений дисков механизма для открытия замка.

Пример:

Ввод: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Вывод: 6
Объяснение: последовательность, открывающая замок: "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".

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

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

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

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

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

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

Пример:

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

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