Связный список-палидром

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

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

Пример:

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

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

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

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

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

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

Класс должен содержать в себе следующие методы:

- BSTIterator(TreeNode root). Данный метод инициализирует объект класса. root передаются в конструктор в качестве входного аргумента. Указатель должен быть инициализирован несуществующим числом, которое меньше любого из элементов бинарного дерева;

- boolean hasNext(). Возвращает true в случае если существует потомок у правого поддерева. В ином случае возвращает false;

- int next(). Перемещает указатель в правую ветвь, возвращая число в указателе.

При инициализации указатель на несуществующий наименьший элемент, вызывая метод next(), будет возвращать наименьший элемент бинарного дерева.

Пример:

Ввод:
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Вывод: [null, 3, 7, true, 9, true, 15, true, 20, false]

Объяснение:
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next(); // return 3
bSTIterator.next(); // return 7
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 9
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 15
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 20
bSTIterator.hasNext(); // return False

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

Удаление элементов из связного списка

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

Условие задачи: дан указетель на связный список и целое число (val). Надо извлечь из сипска все узлыва, значение в которых равняется val.

Итогом должен быть возврат на начало изменненного списка (все опреции будут производиться непосредственно с самим списком).

Пример:

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

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

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

Расписание курсов

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

Условие задачи: дается количество курсов, сами курсы пронумерованны с нуля. Помимо этого дан массив, в котором хранятся зависимости. Зависимость
prerequisites[i] = [ai, bi] предполагает, что курс ai может быть пройден только в случае, если пройден курс bi.

Ответ на задачу должен содержать в себе такую последовательность курсов, при которой все курсы будут пройдены.

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

Пример:

Ввод: numCourses = 2, prerequisites = [[1,0]]
Вывод: [0,1]
Объяснение: чтобы пройти все курсы, изначально надо пройти курс под номером "0", а после имеется возможность пройти курс под номером "1".

Ввод: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Вывод: [0,2,1,3]

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

Наиближайший общий предок

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

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

Наиближайший общий родитель определяется между двумя узлами p и q как наименьший узел в дереве, который имеет как p, так и q в качестве потомков (где мы разрешаем узлу быть потомком самого себя).

Пример:

Ввод: [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Вывод: 6
Объяснение: *на картинке

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

Суммы чисел

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

Примеры:
Ввод: nums = [2,7,11,15], target = 9
Вывод: [0,1]
Поскольку nums [0] + nums [1] == 9, мы возвращаем [0, 1].

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

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

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

Подмножества II

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

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

Множество-решение не должно содержать повторяющихся подмножеств.

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

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

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

Преобразование параметров матрицы

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

Условие задачи: дана матрица (m x n), необходимо выполнить преобразования чтобы матрица имела параметры количества строк и столбцов (r x c).

Значения в новой матрицы должны быть взяты из исходной.

Пример:

Ввод: mat = [[1,2],[3,4]], r = 1, c = 4
Вывод: [[1,2,3,4]]

Ввод: mat = [[1,2],[3,4]], r = 2, c = 4
Вывод: [[1,2],[3,4]]

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

Удаление дубликатов из отсортированного связного списка

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

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

Пример:

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

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

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

Прямой обход дерева

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

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

Пример:

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

Ввод: 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]
Вывод: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]

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

К-ый наименьший элемент в бинарном дереве поиска

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

Условие задачи: на вход подается бинарное дерево поиска, необходимо осуществить в нем поиск К-наименьшего элемента (при условии индексирования с 1).

Пример:

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

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

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

Первая плохая версия

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

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

Предоставляется n - версий, нумерованных с единицы, необходимо найти первую неисправную версию ПО.

Также дается интерфейс bool isBadVersion(version), который производит проверку на то, является ли проверяемая версия неисправной. Решить задачу необходимо за минимальное количество вызовов чекера.

Пример:

Ввод: n = 5, bad = 4
Вывод: 4
Объяснение:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
4 - первая испорченная версия.

Ввод:
Вывод:

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

Мутация генов

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

Условие задачи: подается 8-символьная строка, состоящая из символов: 'A', 'C', 'G', и 'T'.

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

Пример одной мутации: "AACCGGTT" --> "AACCGGTA".

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

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

Пример:

Ввод:
start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
Вывод: 1

Ввод:start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
Вывод: 2

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

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

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

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

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

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

Пример:

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

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

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


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

Записка о выкупе

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

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

Одна буква из magazine может быть исопльзована единажды в ransomNote.

Пример:

Ввод: ransomNote = "a", magazine = "b"
Вывод: false

Ввод: ransomNote = "aa", magazine = "ab"
Вывод: false

Ввод: ransomNote = "aa", magazine = "aab"
Вывод: true

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

Поддерево дерева

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

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

Пример:

Ввод: root = [3,4,5,1,2], subRoot = [4,1,2]
Вывод: true
Объяснение: *на картинке к задаче

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

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

Грабители 2

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

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

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

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

Пример:

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

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

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

Палиндром наибольшей длины в подстроке

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

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

Палиндром - строка, которая одинаково читается как справа-налево, так и слева-направо.

Пример:

Ввод: s = "babad"
Вывод: "bab"
Объяснение: "aba" также является ответом

Ввод: s = "cbbd"
Вывод: "bb"

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

Арифметическая прогрессия в массиве

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

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

Массивы [1,3,5,7,9], [7,7,7,7], [3,-1,-5,-9] являются таковыми.

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

Подмассив - непрерывная последовательность исходного массива.

Пример:

Ввод: nums = [1,2,3,4]
Вывод: 3
Объяснение: [1, 2, 3], [2, 3, 4] и [1,2,3,4] являются арифметическими подмассивами.

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

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

Расшифровка строки

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

Условие задачи: сообщение содержит символы из множества A-Z и может быть расшифровано следующим образом:

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

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

Пример:

Ввод: s = "12"
Вывод: 2
Объяснение: "12" можно расшифровать двумя путями: как (1 2) = "AB", а также как и (12) = "L".

Ввод: s = "226"
Вывод: 3

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