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

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

Условие задачи: дана двумерная решетка размера 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
Объяснение: переспевший фрукт не контактирует со спелыми плодами.

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

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

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

Условие задачи: даны два массива, отсортированные в порядке неубывания, а также две переменные 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]

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

Вращение изображения

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

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

Решение должно фактически изменять исходный массив, не создавая новой матрицы.

Пример:

Ввод: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Вывод: [[7,4,1],[8,5,2],[9,6,3]]


Ввод: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Вывод: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

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

Наидлиннейший общий префикс

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

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

Пример:

Ввод: strs = ["flower","flow","flight"]
Вывод: "fl"

Ввод: strs = ["dog","racecar","car"]
Вывод: ""
Объяснение: в данных строках нет общего префикса

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

Спиральная матрица

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

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

Пример:

Ввод: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Вывод: [1,2,3,6,9,8,7,4,5]

Ввод: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Вывод: [1,2,3,4,8,12,11,10,9,5,6,7]

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

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

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

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

Пример:

Ввод: 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) памяти (т.е. постоянного пространства)?

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

Проверка симметричности дерева

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

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

Пример:

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

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

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

Четно-нечетный связный список

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

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

Первый узел - нечетный, второй - четный. И так далее.

Проблема должна ьыть решена за O(1) по памяти и за O(n) по времени.

Пример:

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

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

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

Расписание дел

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

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

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

Пример:

Ввод: tasks = ["A","A","A","B","B","B"], n = 2
Вывод: 8
Объяснение: A -> B -> idle -> A -> B -> idle -> A -> B

Ввод: tasks = ["A","A","A","B","B","B"], n = 0
Вывод: 6

Ввод: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"],
n = 2
Вывод: 16
Объяснение: A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A


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

Количество анклавов

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

Условие задачи: дана двумерная решетка, где 0 - море, 1 - суша.

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

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

Пример:

Ввод: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Вывод: 3
Объяснение: на данном поле есть три участка суши, отделенных от границ водой, и один элемент, прилегающий к границе.

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

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

Наикратчайший путь в бинарной матрице

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

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

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

В случае отсутствии подобного пути, вернуть -1.

Пример:

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

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

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

Далеко на сколько это возможно

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

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

Измерение расстояния происходит через вычисление Манхэттенского пути (дистания между двумя клетками (x0, y0) и (x1, y1): |x0 - x1| + |y0 - y1|

Пример:

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

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

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

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

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

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

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

Пример:

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

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

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

Количество изолированных островов

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

Условие задачи: дан двумерный массив, содержащий 0 (острова) и 1(воду).

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

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

Пример:

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

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

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

Столкновение астероидов

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

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

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

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

Пример:

Ввод: asteroids = [5,10,-5]
Вывод: [5,10]
Объяснение: 3-ий астероид сталкивается со 2-ым и уничтожается.

Ввод: asteroids = [8,-8]
Вывод: [ ]

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

Квадраты отсортированного массива

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

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

Пример:

Ввод: nums = [-4,-1,0,3,10]
Вывод: [0,1,9,16,100]
Объяснение: после возведения в квадрат получаем следующий массив - [16,1,0,9,100], а результирующий будет выглядеть следующим образом - 0,1,9,16,100].

Ввод: nums = [-7,-3,2,3,11]
Вывод: [4,9,9,49,121]

Решить задачу надо за линейное время.

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

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

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

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

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

В ответе надо вернуть длину такого палидрома.

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

Пример:

Ввод: words = ["lc","cl","gg"]
Вывод: 6
Объяснение: lc" + "gg" + "cl" = "lcggcl" или же "clgglc", но оба имеют максимальную длину 6.

Ввод: words = ["ab","ty","yt","lc","cl","ab"]
Вывод: 8
Объяснение: "ty" + "lc" + "cl" + "yt" = "tylcclyt" или "lcyttycl"

Ввод: words = ["cc","ll","xx"]
Вывод: 2

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

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

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

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

Пример:

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

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