Два огромных океана

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

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

После того, как прошел бурный дождь по острову начала стекать вода. Жидкость может течь лишь в том направлении, где рельеф в текущей точке не меньше (по значению на решетке), чем рельеф в соседней.

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

Пример:

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

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

Бинарное дерево с правой стороны

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

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

Пример:

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

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

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

Префиксное дерево

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

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

Необходимо реализовать класс со следующими методами:

- Trie() - инициализатор;
- void insert(String word) - осуществляет вставку в экземпляр класса;
- boolean search(String word) - возвращает флаг о наличии слова word в дереве;
- boolean startsWith(String prefix) - возвращает флаг о том, начинается ли слово, вставленное на предыдущем шаге с prefix.

Пример:

Ввод: ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

Вывод: [null, null, true, false, true, null, true]

Объяснение:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // return True
trie.search("app"); // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app"); // return True

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

Длина последнего слова

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

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

Пример:

Ввод: s = "Hello World"
Вывод: 5
Объяснение: слово "World" имеет длину 5.

Ввод: s = " fly me to the moon "
Вывод: 4

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

Площадь прямоугольников

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

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

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

Пример:

Ввод: ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
Вывод: 45

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

Подсчет узлов бинарного дерева

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

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

Полным дерево считается в случае, если на каждом уровне (возможно за исключением последнего) у каждого родителя имеется пара потомков.

Необходимо разработать алгоритм с временной сложностью менее O(n).

Пример:

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

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

Комбинация сумм II

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

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

Каждое число из списка кандидатов должно содержаться в конечном подсписке из ответов ровно один раз.

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

Пример:

Ввод: candidates = [10,1,2,7,6,1,5], target = 8
Вывод: [
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Ввод: candidates = [2,5,2,1,2], target = 5
Вывод: [
[1,2,2],
[5]
]

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

Самая длинная счастливая строка

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

Условие задачи:
Строка s называется счастливой, если она удовлетворяет следующим условиям:

• s содержит только буквы «a», «b» и «c».
• s не содержит подстроки «aaa», «bbb» или «ccc».
• s содержит не более a вхождений буквы «a».
• s содержит не более b вхождений буквы «b».
• s содержит не более c вхождений буквы 'c'.

Даны три целых числа a, b и c, вернуть максимально длинную счастливую строку. Если есть несколько самых длинных счастливых строк, верните любую из них. Если такой строки нет, вернуть пустую строку "".

Пример:
Ввод: a = 1, b = 1, c = 7
Вывод: "ccaccbcc"
Пояснение: «ccbccacc» также будет правильным ответом.

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

Поиск в двумерной матрице II

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

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

- в строке элементы отсортированы по возрастанию (слева - направо);
- в столбце элементы отсортированы по возрастанию (снизу - вверх).

Пример:

Ввод: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Вывод: true

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

Число-палиндром

Условие задачи:
Получив целое число x, вернуть true, если x является палиндромом. Целое число является палиндромом, если оно читается одинаково как в прямом, так и в обратном порядке.

Примеры:
Ввод: х = 121
Вывод: true
Объяснение: 121 читается как 121 слева направо и справа налево.

Ввод: х = -121
Вывод: false
Объяснение: Слева направо это -121. Справа налево получается 121-. Следовательно, это не палиндром.

Ввод: х = 10
Вывод: false

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

Прибавка единицы

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

Условие задачи: на вход подаётся массив из цифр, где на i-ой позиции в массиве находится i-ая цифра в числе.

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

Пример:

Ввод: digits = [‘1’, ‘2’, ‘3’]
Вывод: [‘1’, ‘2’, ‘4’]

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

Перенос указателя вправо

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

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

Пример:

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


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

Подмассив с наибольшим произведением

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

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

Подмассив - последовательный кусок исходного массива.

Пример:

Ввод: nums = [2,3,-2,4]
Вывод: 6
Объяснение: [2, 3] имеют наибольшее произведение.

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

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

Нахождение вершины списка

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

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

Дается целочисленный массив (проиндексированный с 0), необходимо вычислить элемент, который является вершиной списка, а после вернуть его индекс. В случае нескольких таких элементов можно вернуть любой из вариантов.

Алгоритм должен иметь временную сложность O (log n).

Пример:

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

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

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

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

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

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

Пример:

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

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

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

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

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

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

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

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

Пример:

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

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

Зигзагообразная обработка текста

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

Условие задачи: строка "PAYPALISHIRING" при разбиении на чтение зигзагом имеет следующий вид.
P A H N
A P L S I I G
Y I R

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

Пример:

Ввод: s = "PAYPALISHIRING", numRows = 3
Вывод: "PAHNAPLSIIGYIR"

Ввод: s = "PAYPALISHIRING", numRows = 4
Вывод:
Объяснение:
P I N
A L S I G
Y A H R
P I

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

Make the string great AGAIN

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

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

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

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

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

Пример:

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

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

Текущая длительность котировок

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

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

Пример:

Ввод: ["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
Вывод: [null, 1, 1, 1, 2, 1, 4, 6]

Объяснение:
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // return 1
stockSpanner.next(80); // return 1
stockSpanner.next(60); // return 1
stockSpanner.next(70); // return 2
stockSpanner.next(60); // return 1
stockSpanner.next(75); // return 4, так как цены за четыре предыдущих дня (включая сегодняшний) были меньше или равны;
stockSpanner.next(85); // return 6

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

Замена элемента на правый максимум

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

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

Пример:

Ввод: arr = [17,18,5,4,6,1]
Вывод: [18,6,6,6,1,-1]

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

Минимальный размер подмассива с суммой

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

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

Пример:

Ввод: target = 7, nums = [2,3,1,2,4,3]
Вывод: 2
Объяснение: сумма в подмассиве [4,3] равна цели - 7


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