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

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

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

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

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

Пример:

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

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

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

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

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

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

Массивы [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

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

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

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

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

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

Пример:

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

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

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

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

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

Условие задачи: даны корни бинарных деревьев 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

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

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

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

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

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

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

Пример:

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

Ввод:
Вывод:

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

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

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

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

Пример:

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

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

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

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

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

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

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

Счастливое число

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

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

Счастливым называется число, соответствующее следующим требованиям:
- создается число, являющееся суммой квадратов цифр числа на предыдущей итерации;
- процесс прододжается до тех пор, пока данная сумма не будет равна 1 или не зациклится;
- числа, которые сходяится по данному алгаритму к единице и являются счастливыми.

Пример:

Ввод: n = 19
Вывод: true
Объяснение:
1 + 81 = 82
64 + 4 = 68
36 + 64 = 100
1 + 0 + 0 = 1

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

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

Сортировка связного списка

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

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

Пример:

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

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

Можете ли вы отсортировать связанный список за O (n logn) времени и O(1) памяти (т.е. постоянного пространства)?

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

Слияние двух отсортированных массивов

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

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

Надо свзать оба массива в один в порядке неубывания.

Результирующий массив должен содержаться в массиве nums1.

Пример:

Ввод: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Вывод: [1,2,2,3,5,6]

Ввод: nums1 = [1], m = 1, nums2 = [], n = 0
Вывод: [1]

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

Переспелые апельсины

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

Условие задачи: дана двумерная решетка размера m x n, в каждой из ячеек может находится одно из следующих значений:
0 - пустая ячейка,
1 - созревший апельсин,
2 - переспевший апельсин.

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

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

Пример:

Ввод: [[2,1,1],[1,1,0],[0,1,1]]
Вывод: 4

Ввод: grid = [[2,1,1],[0,1,1],[1,0,1]]
Вывод: -1
Объяснение: переспевший фрукт не контактирует со спелыми плодами.

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

Двумерный бинарный поиск

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

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

Пример:

Ввод: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Вывод: True

Ввод: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Вывод: Fasle

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

Середина связного списка

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

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

Пример:

Ввод: head = [1,2,3,4,5]
Вывод: [3,4,5]
Объяснение: серединный узел - узел 3.

Ввод: head = [1,2,3,4,5,6]
Вывод: [4,5,6]
Объяснение: лист имеет два серединных значения: 3 и 4, мы возвращаем второй.

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

Топ k-наиболее часто встречающихся слов

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

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

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

Пример:

Ввод:
words = ["i","love","leetcode","i","love","coding"],
k = 2
Вывод: ["i","love"]

Объяснение: "i" и "love" два наиболее частых слова.
Но заметим, что "i" идет первее, чем "love" как раз-таки из-за алфавитного порядка.

Ввод: words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4
Вывод: ["the","is","sunny","day"]

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

Нахождение всех анаграмм в строке

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

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

Анаграмма - строка, составленная путём перестановок букв из какого либо базового набора.

Пример:

Ввод: s = "cbaebabacd", p = "abc"
Вывод: [0,6]

Объяснение:
Подстрока "cba" начинается с индекса 0, она является анаграммой строки "abc".
Подстрока "bac" начинается с индекса 6, она является анаграммой строки "abc".

Ввод: s = "abab", p = "ab"
Вывод: [0,1,2]

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

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

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

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

Пример:

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

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

Содержание дубликатов 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

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

Смена операции

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

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

В результате необходимо получить это самое произведение.

Пример:

Ввод: n = 2
Вывод: 1
Объяснение: 2 = 1 + 1, 1 × 1 = 1.

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

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

Последний из камней

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

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

Осуществляется игра в камни: берутся два камня с наибольшим весом и сталкиваются. Результат их столкновения может быть следующим:

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

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

Пример:

Ввод: stones = [2,7,4,1,8,1]
Вывод: 1

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

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

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

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

Пример:

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

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

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

Make the string great AGAIN

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

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

Строка считается качественной, если две соседние буквы не представлены одной и той же буквой, но в разных регистрах. Такие буквы удаляются до тех пор, пока строка не станет качественной.

Вернуть надо строку, над которой были совершены все преобразования. Гарантируется уникальность ответа.

Пустая строка по умолчанию является качественной.

Пример:

Ввод: s = "leEeetcode"
Вывод: "leetcode"

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