Раскладка костей

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

Условие задачи: есть два типа костей: типа domino и типа tromino.

Дается целое число n, необходимо вычислить количество комбинаций чтобы выложить поле размером 2 x n при помощи двух типов костей.

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

Пример:

Ввод: n = 3
Вывод: 5
Объяснение: *во вложении

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

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

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

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

Пример:

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

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

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

Очередь через стак

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

Условие задачи: необходимо реализовать очередь, используя лишь два стака. Созданная очередь, должна поддерживать все операции, что и обычная (push, peek, pop, empty).

- void push(int x): добавление в конец очереди.
- int pop() удаление верхнего элемента из очереди и возврат его значения.
- int peek() возврат верхнего значения.
- boolean empty() проверка на наличие элементов в очереди.

Пример:

Ввод: ["MyQueue", "push", "push", "peek", "pop", "empty"]
[[ ], [1], [2], [], [ ], [ ] ]
Вывод: [null, null, null, 1, 1, false]
Объяснение:

MyQueue myQueue = new MyQueue();
myQueue.push(1); // очередь: [1]
myQueue.push(2); // очередь: [1, 2]
myQueue.peek(); // return 1
myQueue.pop(); // return 1, очередь [2]
myQueue.empty(); // return false

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

Максимальная разница между узлом и предком

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

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

Пример:

Ввод: root = [8,3,10,1,6,null,14,null,null,4,7,13]
Вывод: 7
Объяснение: некоторые из комбинаций пар потомок-родитель:
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3

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

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

Конструирование прямоугольника

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

Условие задачи: web-разработчикам необходимо знать размеры окна создаваемого приложения. Дается специальная прямоугольная рамка, имеющая размеры L (длина) и W (ширина). На данные габариты накладываются определенные условия:

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

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

Пример:

Ввод: area = 4
Вывод: [2,2]
Объяснение:

Ввод: area = 122122
Вывод: [427,286]

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

Бинарный часы

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

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

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

Пример:

Ввод: turnedOn = 1
Вывод: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]
Объяснение:

Ввод: turnedOn = 9
Вывод: [ ]

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

Максимальное количество единиц

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

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

Пример:

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

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

Минимальная средняя разница

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

Условие задачи: дается массив из целых чисел.

Средняя разница в индексе i - это абсолютная разница между средним первых i + 1 элементов и последних n - i - 1. Оба средних долдны быть округлены до ближайшего целого в меньшую сторону.

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

Пример:

Ввод: nums = [2,5,3,9,5,3]
Вывод: 3
Объяснение: *click


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

Окружение регионов

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

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

Пример:

Ввод: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Вывод: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]

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

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

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

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

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

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

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

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

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

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

Пример:

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

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

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

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

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

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

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

Пример:

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

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

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

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

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

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

Пример:

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


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

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

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

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

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

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

Пример:

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

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

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

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

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

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

Пример:

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

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

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

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

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

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

- 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

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

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

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

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

Пример:

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

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

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

Пересечение интервала

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

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

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

Пример:

Ввод: intervals = [[1,3],[6,9]], newInterval = [2,5]
Вывод: [[1,5],[6,9]]

Ввод: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Вывод: [[1,2],[3,10],[12,16]]

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

Нахождение первой и последние позиций в отсортированном массиве

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

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

Если целевого элемента нет в массиве, то надо вывести [-1; 1].

Алгоритм должен быть не медленнее, чем O(log n) по времени.

Пример:

Ввод: nums = [5,7,7,8,8,10], target = 8
Вывод: [3,4]
Объяснение:

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

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

Где приземлится мяч

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

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

Каждая ячейка данной коробки имеет диагональную перегородку, которая может перенаправлять движение мяча.

- Перегородка ячейки типа "левый верхний угол —> правый нижний угол" имеет представление 1.
- Перегородка ячейки типа "правый верхний угол —> левый нижний угол" имеет представление -1.

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

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

Пример:

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

Ввод: grid = [[-1]]
Вывод: [-1]
Объяснение: мяч уткнется в левую стенку коробки

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

Проверка соответствия строк в двух списках

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

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

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

Пример:

Ввод: word1 = ["ab", "c"], word2 = ["a", "bc"]
Вывод: true

Объяснение:
word1: "ab" + "c" -> "abc"
word2: "a" + "bc" -> "abc"

Ввод: word1 = ["a", "cb"], word2 = ["ab", "c"]
Вывод: false

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