Итератор бинарного дерева
Сложность: Средняя
Условие задачи: надо реализовать класс 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(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
Решение задачи❤2👍1
Счастливое число
Сложность: Лёгкая
Условие задачи: требуется написать алгоритм, определяющий является ли число счастливым.
Счастливым называется число, соответствующее следующим требованиям:
- создается число, являющееся суммой квадратов цифр числа на предыдущей итерации;
- процесс прододжается до тех пор, пока данная сумма не будет равна 1 или не зациклится;
- числа, которые сходяится по данному алгаритму к единице и являются счастливыми.
Пример:
Ввод:
Сложность: Лёгкая
Условие задачи: требуется написать алгоритм, определяющий является ли число счастливым.
Счастливым называется число, соответствующее следующим требованиям:
- создается число, являющееся суммой квадратов цифр числа на предыдущей итерации;
- процесс прододжается до тех пор, пока данная сумма не будет равна 1 или не зациклится;
- числа, которые сходяится по данному алгаритму к единице и являются счастливыми.
Пример:
Ввод:
n = 19
Вывод: true
Объяснение: 1 + 81 = 82
64 + 4 = 68
36 + 64 = 100
1 + 0 + 0 = 1
Ввод: n = 2
Вывод: false
Решение задачи👍2❤1
Сортировка связного списка
Сложность: Средняя
Условие задачи: дан односвязный список, необходимо отсортировать узлы списка по значению в порядке возрастания
Пример:
Ввод:
Решение задачи
Сложность: Средняя
Условие задачи: дан односвязный список, необходимо отсортировать узлы списка по значению в порядке возрастания
Пример:
Ввод:
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) памяти (т.е. постоянного пространства)?Решение задачи
👍2🔥1
Нахождение всех анаграмм в строке
Сложность: Средняя
Условие задачи: даны две строки s и p, надо вернуть все индексы стартовых позиций, с которых начинаются анаграммы внутри строки s.
Анаграмма - строка, составленная путём перестановок букв из какого либо базового набора.
Пример:
Ввод:
Подстрока
Сложность: Средняя
Условие задачи: даны две строки s и p, надо вернуть все индексы стартовых позиций, с которых начинаются анаграммы внутри строки s.
Анаграмма - строка, составленная путём перестановок букв из какого либо базового набора.
Пример:
Ввод:
s = "cbaebabacd", p = "abc"
Вывод: [0,6]
Объяснение:Подстрока
"cba" начинается с индекса 0, она является анаграммой строки "abc".
Подстрока "bac" начинается с индекса 6, она является анаграммой строки "abc".
Ввод: s = "abab", p = "ab"
Вывод: [0,1,2]
Решение задачи👍2
Комбинация сумм 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]
]
Решение задачи
Сложность: Средняя
Условие задачи: на вход дается список возможных кандидатов и целевое значение суммы, необходимо вывести все комбинации, которыми можно получить целевое значение.
Каждое число из списка кандидатов должно содержаться в конечном подсписке из ответов ровно один раз.
Результирующий ответ не должен содержать в себе дубликатов.
Пример:
Ввод: 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]
]
Решение задачи
👍1
Сумма на отрезке
Сложность: Лёгкая
Условие задачи: дается бинарное дерево поиска, дается два числа low и high, необходимо посчитать сумму узлов дерева, находящихся в пределах данного отрезка [low, high].
Пример:
Ввод: root = [10,5,15,3,7,null,18], low = 7, high = 15
Вывод: 32
Объяснение: в данный отрезок входят числа 7, 10, 15.
Решение задачи
Сложность: Лёгкая
Условие задачи: дается бинарное дерево поиска, дается два числа low и high, необходимо посчитать сумму узлов дерева, находящихся в пределах данного отрезка [low, high].
Пример:
Ввод: root = [10,5,15,3,7,null,18], low = 7, high = 15
Вывод: 32
Объяснение: в данный отрезок входят числа 7, 10, 15.
Решение задачи
👍1👎1
Матрица 01
Сложность: Средняя
Условие задачи: дается бинарная матрица (состоит только из 0 и 1). Необходимо вернуть матрицу, в которой будет отображаться расстояние от каждой единичной клетки до ближайшей нулевой.
Пример:
Ввод: mat = [[0,0,0],[0,1,0],[0,0,0]]
Вывод: [[0,0,0],[0,1,0],[0,0,0]]
Объяснение: *во вложении
Ввод: mat = [[0,0,0],[0,1,0],[1,1,1]]
Вывод: [[0,0,0],[0,1,0],[1,2,1]]
Решение задачи
Сложность: Средняя
Условие задачи: дается бинарная матрица (состоит только из 0 и 1). Необходимо вернуть матрицу, в которой будет отображаться расстояние от каждой единичной клетки до ближайшей нулевой.
Пример:
Ввод: mat = [[0,0,0],[0,1,0],[0,0,0]]
Вывод: [[0,0,0],[0,1,0],[0,0,0]]
Объяснение: *во вложении
Ввод: mat = [[0,0,0],[0,1,0],[1,1,1]]
Вывод: [[0,0,0],[0,1,0],[1,2,1]]
Решение задачи
👍1
Максимальное произведение разделенного бинарного дерева
Сложность: Средняя
Условие задачи: дается корень бинарного дерева, необходимо ражзделить его на две части таким образом, чтобы при извлечении одного ребра произведение сумм двух поддеревьев было максимальным.
Необходимо вычислить это произведение. Так как произведение может быть слишком большим, то необходимо посчитать результат по модулю 1е9 + 7.
Пример:
Ввод:
Вывод:
Объяснение: *во вложении
Решение задачи
Сложность: Средняя
Условие задачи: дается корень бинарного дерева, необходимо ражзделить его на две части таким образом, чтобы при извлечении одного ребра произведение сумм двух поддеревьев было максимальным.
Необходимо вычислить это произведение. Так как произведение может быть слишком большим, то необходимо посчитать результат по модулю 1е9 + 7.
Пример:
Ввод:
root = [1,2,3,4,5,6]Вывод:
110Объяснение: *во вложении
Решение задачи
👍1
Максимальная сумма по ребрам бинарного дерева
Сложность: Тяжёлая
Условие задачи: путем в бинарном дереве является последовательность узлов, где каждая пара соседних узлов в последовательности соединена ребром. Узел может появляться в последовательности лишь единожды. Путь не обязательно должен проходить через корень дерева.
Сумма по ребрам в дереве представляет из себя сумму значений из узлов.
На вход подается корень, необходимо вычислить максимальную сумму по ребрам.
Пример:
Ввод:
Вывод:
Объяснение: путь
Решение задачи
Сложность: Тяжёлая
Условие задачи: путем в бинарном дереве является последовательность узлов, где каждая пара соседних узлов в последовательности соединена ребром. Узел может появляться в последовательности лишь единожды. Путь не обязательно должен проходить через корень дерева.
Сумма по ребрам в дереве представляет из себя сумму значений из узлов.
На вход подается корень, необходимо вычислить максимальную сумму по ребрам.
Пример:
Ввод:
root = [-10,9,20,null,null,15,7]Вывод:
42Объяснение: путь
15 -> 20 -> 7 имеет наибольшую сумму в дереве. Решение задачи
👍1👎1
Подъем по ступеням
Сложность: Лёгкая
Условие задачи: человек поднимается по ступенькам. Для подъема на вершину лестницы необходимо сделать n шагов.
При каждом шаге можно делать выбор: подниматься на 1 или же на 2 шага. Нужно посчитать сколькими способами можно подняться на вершину.
Пример:
Ввод: n = 2
Вывод: 2
Объяснение: существует лишь два варианта:
1. 1 шаг + 1 шаг;
2. 2 шага.
Ввод: n = 3
Вывод: 3
Объяснение:
1. 1 шаг + 1 шаг + 1 шаг
2. 1 шаг + 2 шага
3. 2 шага + 1 шаг
Решение задачи
Сложность: Лёгкая
Условие задачи: человек поднимается по ступенькам. Для подъема на вершину лестницы необходимо сделать n шагов.
При каждом шаге можно делать выбор: подниматься на 1 или же на 2 шага. Нужно посчитать сколькими способами можно подняться на вершину.
Пример:
Ввод: n = 2
Вывод: 2
Объяснение: существует лишь два варианта:
1. 1 шаг + 1 шаг;
2. 2 шага.
Ввод: n = 3
Вывод: 3
Объяснение:
1. 1 шаг + 1 шаг + 1 шаг
2. 1 шаг + 2 шага
3. 2 шага + 1 шаг
Решение задачи
👍3
Атака Тимо
Сложность: Лёгкая
Условие задачи: происходит абстрактная ситуация наш персонаж Тимо атакует своего соперника Эша. Результатом атаки является отравление оппонента на
Если Тимо решит нанести ещё один удар до окончания действия отравления от предыдущего, то итоговое отравление закончится через
На вход подаётся массив из моментов времени нападений, а также длительность действия яда. Необходимо вычислить суммарную длительность действия отравы.
Пример:
Ввод:
Сложность: Лёгкая
Условие задачи: происходит абстрактная ситуация наш персонаж Тимо атакует своего соперника Эша. Результатом атаки является отравление оппонента на
duration секунд. То есть начав атаку в момент времени t отравление будет длиться в промежуток времени [t, t + duration - 1]. Если Тимо решит нанести ещё один удар до окончания действия отравления от предыдущего, то итоговое отравление закончится через
duration секунд. На вход подаётся массив из моментов времени нападений, а также длительность действия яда. Необходимо вычислить суммарную длительность действия отравы.
Пример:
Ввод:
timeSeries = [1,4], duration = 2
Вывод: 4
Решение задачи👍1
Возрастающая подпоследовательность наибольшей длины
Сложность: Средняя
Условие задачи: даётся массив, необходимо вычислить наибольшую длину строго возрастающей подпоследовательности.
Пример:
Ввод: nums = [10,9,2,5,3,7,101,18]
Вывод: 4
Объяснение: подпоследовательность [2,3,7,101] имеет наибольшую длину.
Решение задачи
Сложность: Средняя
Условие задачи: даётся массив, необходимо вычислить наибольшую длину строго возрастающей подпоследовательности.
Пример:
Ввод: nums = [10,9,2,5,3,7,101,18]
Вывод: 4
Объяснение: подпоследовательность [2,3,7,101] имеет наибольшую длину.
Решение задачи
👍3❤1
Ряд клавиатуры
Сложность: Лёгкая
Условие задачи: дается массив из строк, необходимо вернуть те строки из массива, которые могут быть набраны лишь при использовании знаков из одного ряда.
Пример:
Ввод:
Вывод:
Объяснение:
Ввод:
Вывод: [ ]
Решение задачи
Сложность: Лёгкая
Условие задачи: дается массив из строк, необходимо вернуть те строки из массива, которые могут быть набраны лишь при использовании знаков из одного ряда.
Пример:
Ввод:
words = ["Hello","Alaska","Dad","Peace"]Вывод:
["Alaska","Dad"]Объяснение:
Ввод:
words = ["omk"]Вывод: [ ]
Решение задачи
👍1
Сумма вдоль столбцов
Сложность: Средняя
Условие задачи: дается квадратная матрица, необходимо вычислить минимальную сумму вдоль столбца.
Есть условие на движение вдоль столбца есть ограничение: можно перемещаться на ячейку вниз лишь по диагонали или строго вниз.
Пример:
Ввод: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Вывод: 13
Объяснение: *во вложении
Решение задачи
Сложность: Средняя
Условие задачи: дается квадратная матрица, необходимо вычислить минимальную сумму вдоль столбца.
Есть условие на движение вдоль столбца есть ограничение: можно перемещаться на ячейку вниз лишь по диагонали или строго вниз.
Пример:
Ввод: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Вывод: 13
Объяснение: *во вложении
Решение задачи
👍1
Перенос указателя вправо
Сложность: Средняя
Условие задачи: дается бинарное дерево, необходимо перенести каждый указатель на следующий узел на соответствующий правый правый элемент на текущем уровне либо же передать указатель на NULL в случае отсутствия узла.
Пример:
Ввод:
Вывод:
Сложность: Средняя
Условие задачи: дается бинарное дерево, необходимо перенести каждый указатель на следующий узел на соответствующий правый правый элемент на текущем уровне либо же передать указатель на NULL в случае отсутствия узла.
Пример:
Ввод:
root = [1,2,3,4,5,null,7]Вывод:
[1,#,2,3,#,4,5,7,#]
Решение задачи👍1
Подмассив с наибольшим произведением
Сложность: Средняя
Условие задачи: на вход подается массив из чисел, необходимо вычислить максимальное произведение, которое встречается в подмассиве исходного массива.
Подмассив - последовательный кусок исходного массива.
Пример:
Ввод: nums = [2,3,-2,4]
Вывод: 6
Объяснение: [2, 3] имеют наибольшее произведение.
Ввод: nums = [-2,0,-1]
Вывод: 0
Решение задачи
Сложность: Средняя
Условие задачи: на вход подается массив из чисел, необходимо вычислить максимальное произведение, которое встречается в подмассиве исходного массива.
Подмассив - последовательный кусок исходного массива.
Пример:
Ввод: nums = [2,3,-2,4]
Вывод: 6
Объяснение: [2, 3] имеют наибольшее произведение.
Ввод: nums = [-2,0,-1]
Вывод: 0
Решение задачи
👍1
Текущая длительность котировок
Сложность: Средняя
Условие задачи: разработайте алгоритм, который сохраняет котировки некоторой акции текущего дня и осуществляет подсчёт, сколько дней до этого стоимость бумаг была меньше или равна цена на текущий день (включая текущий день).
Пример:
Ввод:
Сложность: Средняя
Условие задачи: разработайте алгоритм, который сохраняет котировки некоторой акции текущего дня и осуществляет подсчёт, сколько дней до этого стоимость бумаг была меньше или равна цена на текущий день (включая текущий день).
Пример:
Ввод:
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
Вывод: [null, 1, 1, 1, 2, 1, 4, 6]
Объяснение:StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // return 1
stockSpanner.next(80); // return 1
stockSpanner.next(60); // return 1
stockSpanner.next(70); // return 2
stockSpanner.next(60); // return 1
stockSpanner.next(75); // return 4, так как цены за четыре предыдущих дня (включая сегодняшний) были меньше или равны;
stockSpanner.next(85); // return 6
Решение задачи👍1🔥1
Подсчет узлов бинарного дерева
Сложность: Средняя
Условие задачи: дается корень дерева, удовлетворяющего термину "полнота", надо посчитать количество узлов в дереве.
Полным дерево считается в случае, если на каждом уровне (возможно за исключением последнего) у каждого родителя имеется пара потомков.
Необходимо разработать алгоритм с временной сложностью менее O(n).
Пример:
Ввод: root = [1,2,3,4,5,6]
Вывод: 6
Объяснение: *во вложении
Решение задачи
Сложность: Средняя
Условие задачи: дается корень дерева, удовлетворяющего термину "полнота", надо посчитать количество узлов в дереве.
Полным дерево считается в случае, если на каждом уровне (возможно за исключением последнего) у каждого родителя имеется пара потомков.
Необходимо разработать алгоритм с временной сложностью менее O(n).
Пример:
Ввод: root = [1,2,3,4,5,6]
Вывод: 6
Объяснение: *во вложении
Решение задачи
👍1
Зигзагообразная обработка текста
Сложность: Средняя
Условие задачи: строка "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
Решение задачи
Сложность: Средняя
Условие задачи: строка "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
Решение задачи
👍1
Нахождение вершины списка
Сложность: Средняя
Условие задачи: вершина списка - элемент, который больше как соседа слева, так и соседа справа.
Дается целочисленный массив (проиндексированный с 0), необходимо вычислить элемент, который является вершиной списка, а после вернуть его индекс. В случае нескольких таких элементов можно вернуть любой из вариантов.
Алгоритм должен иметь временную сложность O (log n).
Пример:
Ввод: nums = [1,2,3,1]
Вывод: 2
Ввод: nums = [1,2,1,3,5,6,4]
Вывод: 5
Решение задачи
Сложность: Средняя
Условие задачи: вершина списка - элемент, который больше как соседа слева, так и соседа справа.
Дается целочисленный массив (проиндексированный с 0), необходимо вычислить элемент, который является вершиной списка, а после вернуть его индекс. В случае нескольких таких элементов можно вернуть любой из вариантов.
Алгоритм должен иметь временную сложность O (log n).
Пример:
Ввод: nums = [1,2,3,1]
Вывод: 2
Ввод: nums = [1,2,1,3,5,6,4]
Вывод: 5
Решение задачи
👎1