Быки и коровы

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

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

Быки - правильные цифры, находящиеся на нужных позициях.

Коровы - правильные числа, но находящиеся на соответствующих позициях.

Задача - выдать подсказку в формате "xAyB", где x - количество быков, y - количество коров.

Пример:

Ввод: secret = "1807", guess = "7810"
Вывод: "1A3B"
Объяснение:

Ввод: secret = "1123", guess = "0111"
Вывод: "1A1B"

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

Петля в связном списке II

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

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

Пример:

Ввод: head = [3,2,0,-4], pos = 1
Вывод: последний элемент зацикливается на элементе с индексом
1*.

* соответствующий список проиллюстрирован на картинке.

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

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

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

Условие задачи: дана строка в формате: k[encoded_string], где k - число повторений зашифрованной строки. Необходимо вывести результирующую строку, которая соответствует расшифровке исходной строки.

Пример:

Ввод: s = "3[a]2[bc]"
Вывод: "aaabcbc"

Ввод: s = "3[a2[c]]"
Вывод: "accaccacc"

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

Перебор регистра букв

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

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

Пример:

Ввод: s = "a1b2"
Вывод: ["a1b2","a1B2","A1b2","A1B2"]
Объяснение:

Ввод: s = "3z4"
Вывод: ["3z4","3Z4"]

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

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

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

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

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