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

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

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

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

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

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

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

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

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

Пример:

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

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

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

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

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

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

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

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

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

Пример:

Ввод: 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]
]

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

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

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

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

Пример:

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

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

Матрица 01

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

Условие задачи: дается бинарная матрица (состоит только из 0 и 1). Необходимо вернуть матрицу, в которой будет отображаться расстояние от каждой единичной клетки до ближайшей нулевой.

Пример:

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

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

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

Максимальное произведение разделенного бинарного дерева

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

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

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

Пример:

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

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

Максимальная сумма по ребрам бинарного дерева

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

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

Сумма по ребрам в дереве представляет из себя сумму значений из узлов.

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

Пример:

Ввод: root = [-10,9,20,null,null,15,7]
Вывод: 42
Объяснение: путь 15 -> 20 -> 7 имеет наибольшую сумму в дереве.

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

Подъем по ступеням

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

Условие задачи: человек поднимается по ступенькам. Для подъема на вершину лестницы необходимо сделать n шагов.

При каждом шаге можно делать выбор: подниматься на 1 или же на 2 шага. Нужно посчитать сколькими способами можно подняться на вершину.

Пример:

Ввод: n = 2
Вывод: 2
Объяснение: существует лишь два варианта:
1. 1 шаг + 1 шаг;
2. 2 шага.

Ввод: n = 3
Вывод: 3
Объяснение:
1. 1 шаг + 1 шаг + 1 шаг
2. 1 шаг + 2 шага
3. 2 шага + 1 шаг

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

Атака Тимо

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

Условие задачи: происходит абстрактная ситуация наш персонаж Тимо атакует своего соперника Эша. Результатом атаки является отравление оппонента на duration секунд. То есть начав атаку в момент времени t отравление будет длиться в промежуток времени [t, t + duration - 1].

Если Тимо решит нанести ещё один удар до окончания действия отравления от предыдущего, то итоговое отравление закончится через duration секунд.

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

Пример:

Ввод: timeSeries = [1,4], duration = 2
Вывод: 4

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

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

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

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

Пример:

Ввод: nums = [10,9,2,5,3,7,101,18]
Вывод: 4
Объяснение: подпоследовательность [2,3,7,101] имеет наибольшую длину.

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