Комбинации

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

Условие задачи: даны два целых положительных числа 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

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

Расписание курсов

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

Условие задачи: дается количество курсов, сами курсы пронумерованны с нуля. Помимо этого дан массив, в котором хранятся зависимости. Зависимость
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]

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

Записка о выкупе

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

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

Одна буква из magazine может быть исопльзована единажды в ransomNote.

Пример:

Ввод: ransomNote = "a", magazine = "b"
Вывод: false

Ввод: ransomNote = "aa", magazine = "ab"
Вывод: false

Ввод: ransomNote = "aa", magazine = "aab"
Вывод: true

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

Удаление элементов из связного списка

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

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

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

Пример:

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

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

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

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

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

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

Пример:

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

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

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

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

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

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

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

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

Пример:

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

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

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

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

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

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

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

Пример:

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

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

Схожие деревья

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

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

Два дерева считаются схожими по последним потомкам в случае если последовательность последних потомков и в первом и во втором деревьях идентична.

Пример:

Ввод: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
Вывод: true
Объяснение: *во вложении

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