Создание скобок

Для заданных n пар скобок напишите функцию, генерирующую все комбинации правильных пар скобок.

Ввод: n = 3
Вывод: ["((()))","(()())","(())()","()(())","()()()"]

Ввод: n = 1
Вывод: ["()"]

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

Мокрые бандиты

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

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

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

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

Пример:

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

Объяснение: Грабим 1-ый дом (money = 1), а после навещаем 3-ий дом (money = 3).
Суммарный куш: 1 + 3 = 4.

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

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

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

Условие задачи:
Дан список строк dict, где все строки имеют одинаковую длину.

Верните true, если в одном и том же индексе есть 2 строки, которые отличаются только на 1 символ, в противном случае возвращает false.

Пример:
Ввод: dict = ["abcd","acbd", "aacd"]
Вывод: true
Объяснение: Строки "abcd" и "aacd" отличаются только одним символом в индексе 1.

Ввод: dict = ["ab","cd","yz"]
Вывод: false

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

Проверка бинарного дерева

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

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

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

Пример:

Ввод: root = [5,1,4,null,null,3,6]
Вывод: False
Объяснение: 4 < 5, но при этом находится в правом поддереве.

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

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

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

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

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

Пример:

Ввод: s = "abcabcbb"
Вывод: 3
Объяснение: ответом является подстрока "abc", длина которой равна 3.

Ввод: s = "bbbbb"
Вывод: 1

Ввод: s = "pwwkew"
Вывод: 3
Объяснение: ответ - "wke" (длина = 3).

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

Объединить два отсортированных списка

Вам даны head’ы двух отсортированных связанных списков list1 и list2. Объедините два списка в один отсортированный список. Список должен быть составлен путем соединения узлов первых двух списков. Верните head объединенного связанного списка.

Пример 1 (на картинке):
Ввод: list1 = [1,2,4], list2 = [1,3,4]
Вывод: [1,1,2,3,4,4]

Пример 2:
Ввод: list1 = [], list2 = []
Вывод: []

Пример 3:
Ввод: list1 = [], list2 = [0]
Вывод: [0]

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

То же дерево

Сложность задачи:
Низкая

Условие:
Получив корни двух бинарных деревьев p и q, напишите функцию, проверяющую, совпадают ли они.

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

Примеры (картинки по порядку):
Ввод: p = [1,2,3], q = [1,2,3]
Вывод: true

Ввод: p = [1,2], q = [1,null,2]
Вывод: false

Ввод: p = [1,2,1], q = [1,1,2]
Вывод: false

Ограничения:
Количество узлов в обоих деревьях находится в диапазоне [0, 100].

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

Конференц-залы II

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

Условие задачи:
Дан массив интервалов времени проведения совещаний, intervals, где intervals[i] = [start(i), end(i)]. Найдите минимальное требуемое количество конференц-залов.

Пример:
Ввод: intervals = [[0,30],[5,10],[15,20]]
Вывод: 2

Ввод: intervals = [[7,10],[2,4]]
Вывод: 1

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

Комбинации

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

Условие задачи: даны два целых положительных числа n и k. Надо вывести все комибинации, состоящие из k-чисел в диапазоне [1, n].

Пример:

Ввод: n = 4, k = 2
Вывод:[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Объяснение: число перестановок равно 6. Важным моментом является неупорядоченность чисел внутри самих комбинаций, то есть пары [1,2] и [2,1] являются одинаковыми.

Ввод: n = 1, k = 1
Вывод: [[1]]

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

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

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

Условие задачи: дан двумерный массив, где 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

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

Изъятие дубликатов из односвязного списка

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

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

Пример:

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

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

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

Сцепка бинарного дерева

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

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

Пример:

Ввод: root = [3,9,20,null,null,15,7]
Вывод: [[3],[9,20],[15,7]]
Объяснение:

Ввод: root = [1]
Вывод: [[1]]

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

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

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

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

Пример:

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

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

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

Реализация класса MinStack

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

Условиеи задачи: разработай пользовательский класс MinStack(), который будет иметь следующие методы:

- void push(int val), который добавляет элемент в стак;
- void pop(), удаляющий верхний элемент стака;
- int top(), возвращающий верхний элемент на стаке;
- int getMin(), возвращающий минимальный элемент в стаке на момент вызова метода.

Требуется реализовать все методы таким образом чтобы каждый из них имел временную сложность O(1).

Пример:

Ввод:
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Вывод:
[null,null,null,null,-3,null,0,-2]

Объяснение:

MinStack minStack = новый объект класса MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2

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

Матрица Топлица

Сложность: Лёгкая Средняя Тяжёлая

Условие задачи: дается матрица mxn, верните значение true, если матрица является Теплициевой. В противном случае верните значение false.

Матрица является Теплициевой, если каждая диагональ от верхнего левого края до нижнего правого имеет одинаковые элементы.

Пример:

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

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

Перелет с наименьшей ценой

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

Условие задачи: есть n городов, соединенных некоторым количеством рейсов. Вам предоставляется массив рейсов, где рейсы[i] = [fromi, toi, pricei] указывают, что есть рейс из города из i в город toi со стоимостью pricei.

Вам также даны три целых числа src, dst и k, возвращающие самую дешевую цену из src в dst не более чем с k остановками. Если такого маршрута нет, верните значение -1.

Пример:

Ввод: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Вывод: 700

Ввод: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Вывод: 200

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

Треугольник

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

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

Пример:
Ввод: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Вывод: 11

Объяснение: треуголльник выглядит следующим образом:

2
3 4
6 5 7
4 1 8 3

Минимальный путь выглядит следующим образом: 2 + 3 + 5 + 1 = 11.

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

Комбинация сумм 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» также будет правильным ответом.

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

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

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

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

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