Задача: 991. Broken Calculator
Сложность: medium
Имеется неисправный калькулятор, на экране которого изначально отображается целое число startValue. За одну операцию можно:
Умножить число на экране на 2, или
Вычесть 1 из числа на экране.
Даны два целых числа startValue и target. Верните минимальное количество операций, необходимых для отображения target на калькуляторе.
Пример:
👨💻 Алгоритм:
1⃣Обратный путь:
Если target больше startValue, то попытайтесь уменьшить target, чтобы привести его к startValue.
Если target четный, разделите его на 2, иначе прибавьте 1.
2⃣Подсчет операций:
Повторяйте шаги, пока target не станет меньше или равен startValue.
После этого вычитайте из startValue оставшееся значение target.
3⃣Возврат результата:
Возвращайте суммарное количество выполненных операций.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Имеется неисправный калькулятор, на экране которого изначально отображается целое число startValue. За одну операцию можно:
Умножить число на экране на 2, или
Вычесть 1 из числа на экране.
Даны два целых числа startValue и target. Верните минимальное количество операций, необходимых для отображения target на калькуляторе.
Пример:
Input: startValue = 2, target = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.
👨💻 Алгоритм:
1⃣Обратный путь:
Если target больше startValue, то попытайтесь уменьшить target, чтобы привести его к startValue.
Если target четный, разделите его на 2, иначе прибавьте 1.
2⃣Подсчет операций:
Повторяйте шаги, пока target не станет меньше или равен startValue.
После этого вычитайте из startValue оставшееся значение target.
3⃣Возврат результата:
Возвращайте суммарное количество выполненных операций.
😎 Решение:
public class Solution {
public int brokenCalc(int startValue, int target) {
int operations = 0;
while (target > startValue) {
operations++;
if (target % 2 == 0) {
target /= 2;
} else {
target += 1;
}
}
return operations + (startValue - target);
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 973. K Closest Points to Origin
Сложность: medium
Дан массив точек, где points[i] = [xi, yi] представляет собой точку на плоскости X-Y, и целое число k. Верните k точек, ближайших к началу координат (0, 0).
Расстояние между двумя точками на плоскости X-Y является евклидовым расстоянием (то есть √((x1 - x2)² + (y1 - y2)²)).
Вы можете вернуть ответ в любом порядке. Гарантируется, что ответ будет уникальным (за исключением порядка).
Пример:
👨💻 Алгоритм:
1⃣Отсортируйте массив с помощью функции компаратора.
2⃣Функция компаратора будет использовать уравнение квадратного евклидова расстояния для сравнения двух точек.
3⃣Верните первые k элементов массива.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дан массив точек, где points[i] = [xi, yi] представляет собой точку на плоскости X-Y, и целое число k. Верните k точек, ближайших к началу координат (0, 0).
Расстояние между двумя точками на плоскости X-Y является евклидовым расстоянием (то есть √((x1 - x2)² + (y1 - y2)²)).
Вы можете вернуть ответ в любом порядке. Гарантируется, что ответ будет уникальным (за исключением порядка).
Пример:
Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].
👨💻 Алгоритм:
1⃣Отсортируйте массив с помощью функции компаратора.
2⃣Функция компаратора будет использовать уравнение квадратного евклидова расстояния для сравнения двух точек.
3⃣Верните первые k элементов массива.
😎 Решение:
import java.util.Arrays;
class Solution {
public int[][] kClosest(int[][] points, int k) {
Arrays.sort(points, (a, b) -> squaredDistance(a) - squaredDistance(b));
return Arrays.copyOfRange(points, 0, k);
}
private int squaredDistance(int[] point) {
return point[0] * point[0] + point[1] * point[1];
}
}
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1273. Delete Tree Nodes
Сложность: medium
Дерево, укорененное в узле 0, задано следующим образом: количество узлов - nodes; значение i-го узла - value[i]; родитель i-го узла - parent[i]. Удалите все поддеревья, сумма значений узлов которых равна нулю. Верните количество оставшихся узлов в дереве.
Пример:
👨💻 Алгоритм:
1⃣Постройте дерево из заданных узлов, значений и родителей.
2⃣Используйте постфиксный обход для вычисления суммы значений в каждом поддереве и помечайте узлы для удаления, если их сумма равна нулю.
3⃣Удалите отмеченные узлы и их поддеревья и верните количество оставшихся узлов.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дерево, укорененное в узле 0, задано следующим образом: количество узлов - nodes; значение i-го узла - value[i]; родитель i-го узла - parent[i]. Удалите все поддеревья, сумма значений узлов которых равна нулю. Верните количество оставшихся узлов в дереве.
Пример:
Input: nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1]
Output: 2
👨💻 Алгоритм:
1⃣Постройте дерево из заданных узлов, значений и родителей.
2⃣Используйте постфиксный обход для вычисления суммы значений в каждом поддереве и помечайте узлы для удаления, если их сумма равна нулю.
3⃣Удалите отмеченные узлы и их поддеревья и верните количество оставшихся узлов.
😎 Решение:
import java.util.*;
public class Solution {
public int deleteTreeNodes(int nodes, int[] parent, int[] value) {
Map<Integer, List<Integer>> tree = new HashMap<>();
for (int i = 0; i < nodes; i++) {
tree.computeIfAbsent(parent[i], k -> new ArrayList<>()).add(i);
}
return dfs(0, tree, value)[1];
}
private int[] dfs(int node, Map<Integer, List<Integer>> tree, int[] value) {
int totalSum = value[node];
int totalCount = 1;
if (tree.containsKey(node)) {
for (int child : tree.get(node)) {
int[] childResult = dfs(child, tree, value);
totalSum += childResult[0];
totalCount += childResult[1];
}
}
if (totalSum == 0) {
return new int[]{0, 0};
}
return new int[]{totalSum, totalCount};
}
}
Ставь 👍 и забирай 📚 Базу знаний
Задача: 919. Complete Binary Tree Inserter
Сложность: medium
Полное двоичное дерево - это двоичное дерево, в котором каждый уровень, кроме, возможно, последнего, полностью заполнен, а все узлы расположены как можно дальше влево. Разработайте алгоритм вставки нового узла в полное двоичное дерево, сохраняя его полным после вставки.
Реализуйте класс CBTInserter: CBTInserter(TreeNode root) Инициализирует структуру данных корнем полного бинарного дерева. int insert(int v) Вставляет TreeNode в дерево со значением Node.val == val так, что дерево остается полным, и возвращает значение родителя вставленного TreeNode. TreeNode get_root() Возвращает корневой узел дерева.
Пример:
👨💻 Алгоритм:
1⃣Инициализация: Проход по дереву и добавление всех узлов в очередь, чтобы отслеживать узлы, у которых есть хотя бы одно пустое место для нового дочернего узла.
2⃣Вставка: Добавление нового узла в первое доступное место слева направо.
3⃣Возвращение корня: Просто возвращает корневой узел.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Полное двоичное дерево - это двоичное дерево, в котором каждый уровень, кроме, возможно, последнего, полностью заполнен, а все узлы расположены как можно дальше влево. Разработайте алгоритм вставки нового узла в полное двоичное дерево, сохраняя его полным после вставки.
Реализуйте класс CBTInserter: CBTInserter(TreeNode root) Инициализирует структуру данных корнем полного бинарного дерева. int insert(int v) Вставляет TreeNode в дерево со значением Node.val == val так, что дерево остается полным, и возвращает значение родителя вставленного TreeNode. TreeNode get_root() Возвращает корневой узел дерева.
Пример:
Input
["CBTInserter", "insert", "insert", "get_root"]
[[[1, 2]], [3], [4], []]
Output
[null, 1, 2, [1, 2, 3, 4]]
👨💻 Алгоритм:
1⃣Инициализация: Проход по дереву и добавление всех узлов в очередь, чтобы отслеживать узлы, у которых есть хотя бы одно пустое место для нового дочернего узла.
2⃣Вставка: Добавление нового узла в первое доступное место слева направо.
3⃣Возвращение корня: Просто возвращает корневой узел.
😎 Решение:
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class CBTInserter {
private TreeNode root;
private Queue<TreeNode> deque;
public CBTInserter(TreeNode root) {
this.root = root;
this.deque = new LinkedList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node.left == null || node.right == null) {
deque.add(node);
}
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
public int insert(int v) {
TreeNode node = deque.peek();
TreeNode newNode = new TreeNode(v);
if (node.left == null) {
node.left = newNode;
} else {
node.right = newNode;
deque.poll();
}
deque.add(newNode);
return node.val;
}
public TreeNode get_root() {
return root;
}
}
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1055. Shortest Way to Form String
Сложность: medium
Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (например, "ace" является подпоследовательностью "abcde", а "aec" - нет). Если даны две строки source и target, верните минимальное количество подпоследовательностей source, чтобы их объединение равнялось target. Если задача невыполнима, верните -1.
Пример:
👨💻 Алгоритм:
1⃣Используй два указателя для отслеживания текущих позиций в строках source и target.
2⃣Перебирай символы строки source, пока не найдешь совпадающий символ в target.
Если ты прошел всю строку source и не нашел все символы target, увеличь счетчик количества подпоследовательностей и начни снова с начала source.
3⃣Повтори шаги 2 и 3 до тех пор, пока не пройдешь всю строку target.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (например, "ace" является подпоследовательностью "abcde", а "aec" - нет). Если даны две строки source и target, верните минимальное количество подпоследовательностей source, чтобы их объединение равнялось target. Если задача невыполнима, верните -1.
Пример:
Input: source = "abc", target = "abcbc"
Output: 2
👨💻 Алгоритм:
1⃣Используй два указателя для отслеживания текущих позиций в строках source и target.
2⃣Перебирай символы строки source, пока не найдешь совпадающий символ в target.
Если ты прошел всю строку source и не нашел все символы target, увеличь счетчик количества подпоследовательностей и начни снова с начала source.
3⃣Повтори шаги 2 и 3 до тех пор, пока не пройдешь всю строку target.
😎 Решение:
public class Solution {
public int minSubsequences(String source, String target) {
int subsequencesCount = 0;
int targetIndex = 0;
while (targetIndex < target.length()) {
int sourceIndex = 0;
subsequencesCount++;
int startIndex = targetIndex;
while (sourceIndex < source.length() && targetIndex < target.length()) {
if (source.charAt(sourceIndex) == target.charAt(targetIndex)) {
targetIndex++;
}
sourceIndex++;
}
if (targetIndex == startIndex) {
return -1;
}
}
return subsequencesCount;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1023. Camelcase Matching
Сложность: medium
Учитывая массив строк queries и строку pattern, верните булевский массив answer, где answer[i] - true, если queries[i] соответствует pattern, и false в противном случае. Слово запроса queries[i] соответствует pattern, если вы можете вставить строчные английские буквы pattern так, чтобы они были равны запросу. Вы можете вставить каждый символ в любую позицию и не можете вставить ни одного символа.
Пример:
👨💻 Алгоритм:
1⃣Инициализация переменных:
Создайте массив answer для хранения результатов соответствия каждого запроса шаблону.
2⃣Проверка каждого запроса:
Для каждого запроса из queries, проверьте, можно ли вставить строчные буквы в pattern, чтобы они соответствовали запросу.
Используйте два указателя, один для query и один для pattern. Перемещайте оба указателя, пока они не достигнут конца строк. Если текущие символы совпадают, переместите оба указателя. Если символы не совпадают и текущий символ в запросе является строчной буквой, переместите только указатель запроса.
3⃣Возврат результата:
Если указатель шаблона достиг конца строки, добавьте true в answer, иначе добавьте false.
Верните массив answer.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Учитывая массив строк queries и строку pattern, верните булевский массив answer, где answer[i] - true, если queries[i] соответствует pattern, и false в противном случае. Слово запроса queries[i] соответствует pattern, если вы можете вставить строчные английские буквы pattern так, чтобы они были равны запросу. Вы можете вставить каждый символ в любую позицию и не можете вставить ни одного символа.
Пример:
Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB"
Output: [true,false,true,true,false]
👨💻 Алгоритм:
1⃣Инициализация переменных:
Создайте массив answer для хранения результатов соответствия каждого запроса шаблону.
2⃣Проверка каждого запроса:
Для каждого запроса из queries, проверьте, можно ли вставить строчные буквы в pattern, чтобы они соответствовали запросу.
Используйте два указателя, один для query и один для pattern. Перемещайте оба указателя, пока они не достигнут конца строк. Если текущие символы совпадают, переместите оба указателя. Если символы не совпадают и текущий символ в запросе является строчной буквой, переместите только указатель запроса.
3⃣Возврат результата:
Если указатель шаблона достиг конца строки, добавьте true в answer, иначе добавьте false.
Верните массив answer.
😎 Решение:
public class Solution {
public boolean[] camelMatch(String[] queries, String pattern) {
boolean matches(String query, String pattern) {
int i = 0, j = 0;
while (i < query.length()) {
if (j < pattern.length() && query.charAt(i) == pattern.charAt(j)) {
j++;
} else if (Character.isUpperCase(query.charAt(i))) {
return false;
}
i++;
}
return j == pattern.length();
}
boolean[] answer = new boolean[queries.length];
for (int i = 0; i < queries.length; i++) {
answer[i] = matches(queries[i], pattern);
}
return answer;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 506. Relative Ranks
Сложность: easy
Вам дан целочисленный массив score размером n, где score[i] — это результат i-го спортсмена на соревновании. Все результаты гарантированно уникальны.
Спортсмены размещаются на основе своих результатов: спортсмен, занявший 1-е место, имеет наивысший результат, спортсмен, занявший 2-е место, имеет второй по величине результат и так далее. Размещение каждого спортсмена определяет его ранг:
Ранг спортсмена, занявшего 1-е место, — "Gold Medal".
Ранг спортсмена, занявшего 2-е место, — "Silver Medal".
Ранг спортсмена, занявшего 3-е место, — "Bronze Medal".
Для спортсменов, занявших с 4-го по n-е место, их ранг соответствует их номеру в размещении (т.е. ранг спортсмена, занявшего x-е место, — "x").
Верните массив answer размером n, где answer[i] — это ранг i-го спортсмена.
Пример:
👨💻 Алгоритм:
1⃣Инициализация и нахождение максимального значения
Инициализируйте переменную N длиной массива score. Определите функцию findMax, которая находит максимальный балл в массиве score.
2⃣Создание вспомогательных структур
Инициализируйте массив scoreToIndex размером M + 1, где M — это максимальное значение в массиве score. Заполните scoreToIndex таким образом, чтобы для каждого score[i] его индекс сохранялся в scoreToIndex[score[i]].
3⃣Присваивание рангов и формирование ответа
Создайте массив rank для хранения рангов спортсменов. Используйте цикл для присваивания медалей и рангов в зависимости от значений в scoreToIndex, начиная с наибольшего.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Вам дан целочисленный массив score размером n, где score[i] — это результат i-го спортсмена на соревновании. Все результаты гарантированно уникальны.
Спортсмены размещаются на основе своих результатов: спортсмен, занявший 1-е место, имеет наивысший результат, спортсмен, занявший 2-е место, имеет второй по величине результат и так далее. Размещение каждого спортсмена определяет его ранг:
Ранг спортсмена, занявшего 1-е место, — "Gold Medal".
Ранг спортсмена, занявшего 2-е место, — "Silver Medal".
Ранг спортсмена, занявшего 3-е место, — "Bronze Medal".
Для спортсменов, занявших с 4-го по n-е место, их ранг соответствует их номеру в размещении (т.е. ранг спортсмена, занявшего x-е место, — "x").
Верните массив answer размером n, где answer[i] — это ранг i-го спортсмена.
Пример:
Input: score = [5,4,3,2,1]
Output: ["Gold Medal","Silver Medal","Bronze Medal","4","5"]
Explanation: The placements are [1st, 2nd, 3rd, 4th, 5th].
👨💻 Алгоритм:
1⃣Инициализация и нахождение максимального значения
Инициализируйте переменную N длиной массива score. Определите функцию findMax, которая находит максимальный балл в массиве score.
2⃣Создание вспомогательных структур
Инициализируйте массив scoreToIndex размером M + 1, где M — это максимальное значение в массиве score. Заполните scoreToIndex таким образом, чтобы для каждого score[i] его индекс сохранялся в scoreToIndex[score[i]].
3⃣Присваивание рангов и формирование ответа
Создайте массив rank для хранения рангов спортсменов. Используйте цикл для присваивания медалей и рангов в зависимости от значений в scoreToIndex, начиная с наибольшего.
😎 Решение:
class Solution {
private int findMax(int[] score) {
int maxScore = 0;
for (int s : score) {
if (s > maxScore) {
maxScore = s;
}
}
return maxScore;
}
public String[] findRelativeRanks(int[] score) {
int N = score.length;
int M = findMax(score);
int[] scoreToIndex = new int[M + 1];
for (int i = 0; i < N; i++) {
scoreToIndex[score[i]] = i + 1;
}
final String[] MEDALS = {"Gold Medal", "Silver Medal", "Bronze Medal"};
String[] rank = new String[N];
int place = 1;
for (int i = M; i >= 0; i--) {
if (scoreToIndex[i] != 0) {
int originalIndex = scoreToIndex[i] - 1;
if (place < 4) {
rank[originalIndex] = MEDALS[place - 1];
} else {
rank[originalIndex] = String.valueOf(place);
}
place++;
}
}
return rank;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 621. Task Scheduler
Сложность: medium
Вам дан массив задач процессора, каждая из которых представлена буквами от A до Z, и время охлаждения, n. Каждый цикл или интервал позволяет завершить одну задачу. Задачи могут быть выполнены в любом порядке, но есть ограничение: одинаковые задачи должны быть разделены не менее чем n интервалами из-за времени охлаждения. Верните минимальное количество интервалов, необходимое для выполнения всех задач.
Пример:
👨💻 Алгоритм:
1⃣Подсчитайте количество каждой задачи и найдите максимальное количество вхождений (maxFreq).
2⃣Вычислите количество интервалов, необходимых для задач с maxFreq: (maxFreq - 1) * (n + 1) + countMaxFreq, где countMaxFreq - количество задач, имеющих maxFreq.
3⃣Верните максимум между вычисленным значением и длиной массива задач, поскольку некоторые задачи могут заполнять интервал до n.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Вам дан массив задач процессора, каждая из которых представлена буквами от A до Z, и время охлаждения, n. Каждый цикл или интервал позволяет завершить одну задачу. Задачи могут быть выполнены в любом порядке, но есть ограничение: одинаковые задачи должны быть разделены не менее чем n интервалами из-за времени охлаждения. Верните минимальное количество интервалов, необходимое для выполнения всех задач.
Пример:
Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
👨💻 Алгоритм:
1⃣Подсчитайте количество каждой задачи и найдите максимальное количество вхождений (maxFreq).
2⃣Вычислите количество интервалов, необходимых для задач с maxFreq: (maxFreq - 1) * (n + 1) + countMaxFreq, где countMaxFreq - количество задач, имеющих maxFreq.
3⃣Верните максимум между вычисленным значением и длиной массива задач, поскольку некоторые задачи могут заполнять интервал до n.
😎 Решение:
import java.util.HashMap;
import java.util.Map;
public class Solution {
public int leastInterval(char[] tasks, int n) {
Map<Character, Integer> taskCounts = new HashMap<>();
for (char task : tasks) {
taskCounts.put(task, taskCounts.getOrDefault(task, 0) + 1);
}
int maxFreq = taskCounts.values().stream().max(Integer::compare).get();
int countMaxFreq = (int) taskCounts.values().stream().filter(count -> count == maxFreq).count();
return Math.max(tasks.length, (maxFreq - 1) * (n + 1) + countMaxFreq);
}
}
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1339. Maximum Product of Splitted Binary Tree
Сложность: medium
Дано корневое дерево. Разделите бинарное дерево на два поддерева, удалив одно ребро так, чтобы произведение сумм поддеревьев было максимальным.
Верните максимальное произведение сумм двух поддеревьев. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.
Обратите внимание, что вам нужно максимально увеличить ответ до взятия модуля, а не после.
Пример:
👨💻 Алгоритм:
1⃣Рассчитать сумму значений всех узлов дерева и сохранить суммы всех поддеревьев в списке.
2⃣Перебрать все сохраненные суммы поддеревьев и для каждой вычислить произведение суммы поддерева и разности между общей суммой дерева и данной суммой поддерева.
3⃣Найти максимальное произведение среди всех вычисленных и вернуть его значение по модулю 10^9 + 7.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дано корневое дерево. Разделите бинарное дерево на два поддерева, удалив одно ребро так, чтобы произведение сумм поддеревьев было максимальным.
Верните максимальное произведение сумм двух поддеревьев. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.
Обратите внимание, что вам нужно максимально увеличить ответ до взятия модуля, а не после.
Пример:
Input: root = [1,2,3,4,5,6]
Output: 110
Explanation: Remove the red edge and get 2 binary trees with sum 11 and 10. Their product is 110 (11*10)
👨💻 Алгоритм:
1⃣Рассчитать сумму значений всех узлов дерева и сохранить суммы всех поддеревьев в списке.
2⃣Перебрать все сохраненные суммы поддеревьев и для каждой вычислить произведение суммы поддерева и разности между общей суммой дерева и данной суммой поддерева.
3⃣Найти максимальное произведение среди всех вычисленных и вернуть его значение по модулю 10^9 + 7.
😎 Решение:
class Solution {
private List<Integer> allSums = new ArrayList<>();
public int maxProduct(TreeNode root) {
long totalSum = treeSum(root);
long best = 0;
for (long sum : allSums) {
best = Math.max(best, sum * (totalSum - sum));
}
return (int)(best % 1000000007);
}
private int treeSum(TreeNode subroot) {
if (subroot == null) return 0;
int leftSum = treeSum(subroot.left);
int rightSum = treeSum(subroot.right);
int totalSum = leftSum + rightSum + subroot.val;
allSums.add(totalSum);
return totalSum;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 208. Implement Trie (Prefix Tree)
Сложность: medium
Trie (произносится как "трай") или префиксное дерево — это древовидная структура данных, используемая для эффективного хранения и поиска ключей в наборе строк. Существует множество применений этой структуры данных, таких как автозаполнение и проверка орфографии.
Реализуйте класс Trie:
Trie() инициализирует объект trie.
void insert(String word) вставляет строку word в trie.
boolean search(String word) возвращает true, если строка word есть в trie (то есть была вставлена ранее), и false в противном случае.
boolean startsWith(String prefix) возвращает true, если есть ранее вставленная строка word, которая имеет префикс prefix, и false в противном случае.
Пример:
👨💻 Алгоритм:
1⃣Инициализация и вставка в Trie:
Создайте класс Trie, который включает в себя метод insert(String word) для добавления строк в Trie.
Метод insert инициализирует текущий узел как корень и проходит по каждому символу строки. Если текущий узел не содержит символа, создайте новый узел. В конце отметьте последний узел как конец слова.
2⃣Поиск строки в Trie:
Создайте метод search(String word), который использует вспомогательный метод searchPrefix(String word) для поиска строки или префикса в Trie.
В методе searchPrefix начните с корневого узла и для каждого символа строки перемещайтесь к следующему узлу. Если на каком-то этапе узел не содержит текущего символа, верните null. В противном случае, в конце строки верните текущий узел.
3⃣Проверка наличия префикса в Trie:
Создайте метод startsWith(String prefix), который также использует метод searchPrefix(String prefix).
Метод startsWith вызывает searchPrefix и возвращает true, если возвращаемый узел не равен null, что указывает на наличие префикса в Trie.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Trie (произносится как "трай") или префиксное дерево — это древовидная структура данных, используемая для эффективного хранения и поиска ключей в наборе строк. Существует множество применений этой структуры данных, таких как автозаполнение и проверка орфографии.
Реализуйте класс Trie:
Trie() инициализирует объект trie.
void insert(String word) вставляет строку word в trie.
boolean search(String word) возвращает true, если строка word есть в trie (то есть была вставлена ранее), и false в противном случае.
boolean startsWith(String prefix) возвращает true, если есть ранее вставленная строка word, которая имеет префикс prefix, и false в противном случае.
Пример:
Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]
Explanation
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
👨💻 Алгоритм:
1⃣Инициализация и вставка в Trie:
Создайте класс Trie, который включает в себя метод insert(String word) для добавления строк в Trie.
Метод insert инициализирует текущий узел как корень и проходит по каждому символу строки. Если текущий узел не содержит символа, создайте новый узел. В конце отметьте последний узел как конец слова.
2⃣Поиск строки в Trie:
Создайте метод search(String word), который использует вспомогательный метод searchPrefix(String word) для поиска строки или префикса в Trie.
В методе searchPrefix начните с корневого узла и для каждого символа строки перемещайтесь к следующему узлу. Если на каком-то этапе узел не содержит текущего символа, верните null. В противном случае, в конце строки верните текущий узел.
3⃣Проверка наличия префикса в Trie:
Создайте метод startsWith(String prefix), который также использует метод searchPrefix(String prefix).
Метод startsWith вызывает searchPrefix и возвращает true, если возвращаемый узел не равен null, что указывает на наличие префикса в Trie.
😎 Решение:
class TrieNode {
private TrieNode[] links = new TrieNode[26];
private boolean isEnd;
public boolean containsKey(char ch) {
return links[ch - 'a'] != null;
}
public TrieNode get(char ch) {
return links[ch - 'a'];
}
public void put(char ch, TrieNode node) {
links[ch - 'a'] = node;
}
public void setEnd() {
isEnd = true;
}
public boolean isEnd() {
return isEnd;
}
}
class Trie {
private TrieNode root = new TrieNode();
public void insert(String word) {
TrieNode node = root;
for (char ch : word.toCharArray()) {
if (!node.containsKey(ch)) {
node.put(ch, new TrieNode());
}
node = node.get(ch);
}
node.setEnd();
}
private TrieNode searchPrefix(String word) {
TrieNode node = root;
for (char ch : word.toCharArray()) {
if (node.containsKey(ch)) {
node = node.get(ch);
} else {
return null;
}
}
return node;
}
public boolean search(String word) {
TrieNode node = searchPrefix(word);
return node != null && node.isEnd();
}
public boolean startsWith(String prefix) {
return searchPrefix(prefix) != null;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 743. Network Delay Time
Сложность: medium
Дана сеть из узлов, помеченных от 1 до n. Также дано times - список времен прохождения сигнала в виде направленных ребер times[i] = (ui, vi, wi), где ui - исходный узел, vi - целевой узел, а wi - время прохождения сигнала от источника до цели. Мы пошлем сигнал из заданного узла k. Верните минимальное время, которое потребуется всем узлам, чтобы получить сигнал. Если все узлы не могут получить сигнал, верните -1.
Пример:
👨💻 Алгоритм:
1⃣Представьте граф в виде списка смежности.
2⃣Используйте алгоритм Дейкстры для нахождения кратчайших путей от узла k до всех других узлов.
3⃣Найдите максимальное значение среди кратчайших путей к узлам. Если какой-либо узел недостижим, верните -1.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дана сеть из узлов, помеченных от 1 до n. Также дано times - список времен прохождения сигнала в виде направленных ребер times[i] = (ui, vi, wi), где ui - исходный узел, vi - целевой узел, а wi - время прохождения сигнала от источника до цели. Мы пошлем сигнал из заданного узла k. Верните минимальное время, которое потребуется всем узлам, чтобы получить сигнал. Если все узлы не могут получить сигнал, верните -1.
Пример:
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
👨💻 Алгоритм:
1⃣Представьте граф в виде списка смежности.
2⃣Используйте алгоритм Дейкстры для нахождения кратчайших путей от узла k до всех других узлов.
3⃣Найдите максимальное значение среди кратчайших путей к узлам. Если какой-либо узел недостижим, верните -1.
😎 Решение:
import java.util.*;
public class Solution {
public int networkDelayTime(int[][] times, int n, int k) {
Map<Integer, List<int[]>> graph = new HashMap<>();
for (int i = 1; i <= n; i++) {
graph.put(i, new ArrayList<>());
}
for (int[] time : times) {
graph.get(time[0]).add(new int[]{time[1], time[2]});
}
PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
minHeap.add(new int[]{0, k});
Map<Integer, Integer> minTime = new HashMap<>();
for (int i = 1; i <= n; i++) {
minTime.put(i, Integer.MAX_VALUE);
}
minTime.put(k, 0);
while (!minHeap.isEmpty()) {
int[] top = minHeap.poll();
int time = top[0];
int node = top[1];
for (int[] neighbor : graph.get(node)) {
int newTime = time + neighbor[1];
if (newTime < minTime.get(neighbor[0])) {
minTime.put(neighbor[0], newTime);
minHeap.add(new int[]{newTime, neighbor[0]});
}
}
}
int maxTime = Collections.max(minTime.values());
return maxTime == Integer.MAX_VALUE ? -1 : maxTime;
}
}
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1026. Maximum Difference Between Node and Ancestor
Сложность: medium
Учитывая корень бинарного дерева, найдите максимальное значение v, для которого существуют различные вершины a и b, где v = |a.val - b.val| и a является предком b. Вершина a является предком b, если: любой ребенок a равен b или любой ребенок a является предком b.
Пример:
👨💻 Алгоритм:
1⃣Рекурсивный обход дерева:
Используйте рекурсивную функцию для обхода дерева. Передавайте минимальное и максимальное значения, встреченные на пути от корня к текущему узлу.
2⃣Обновление максимальной разницы:
При посещении каждого узла обновляйте минимальное и максимальное значения. Вычисляйте разницу между текущим значением узла и минимальным и максимальным значениями на пути. Обновляйте максимальную разницу, если текущая разница больше.
3⃣Рекурсивный вызов для детей:
Рекурсивно вызывайте функцию для левого и правого поддерева, передавая обновленные минимальное и максимальное значения.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Учитывая корень бинарного дерева, найдите максимальное значение v, для которого существуют различные вершины a и b, где v = |a.val - b.val| и a является предком b. Вершина a является предком b, если: любой ребенок a равен b или любой ребенок a является предком b.
Пример:
Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7
👨💻 Алгоритм:
1⃣Рекурсивный обход дерева:
Используйте рекурсивную функцию для обхода дерева. Передавайте минимальное и максимальное значения, встреченные на пути от корня к текущему узлу.
2⃣Обновление максимальной разницы:
При посещении каждого узла обновляйте минимальное и максимальное значения. Вычисляйте разницу между текущим значением узла и минимальным и максимальным значениями на пути. Обновляйте максимальную разницу, если текущая разница больше.
3⃣Рекурсивный вызов для детей:
Рекурсивно вызывайте функцию для левого и правого поддерева, передавая обновленные минимальное и максимальное значения.
😎 Решение:
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public int maxAncestorDiff(TreeNode root) {
return dfs(root, root.val, root.val);
}
private int dfs(TreeNode node, int minVal, int maxVal) {
if (node == null) return maxVal - minVal;
minVal = Math.min(minVal, node.val);
maxVal = Math.max(maxVal, node.val);
int left = dfs(node.left, minVal, maxVal);
int right = dfs(node.right, minVal, maxVal);
return Math.max(left, right);
}
}Ставь 👍 и забирай 📚 Базу знаний