Задача: 1266. Minimum Time Visiting All Points
Сложность: easy
На двумерной плоскости имеется n точек с целочисленными координатами points[i] = [xi, yi]. Верните минимальное время в секундах для посещения всех точек в порядке, заданном точками. Вы можете перемещаться по следующим правилам: за 1 секунду вы можете либо: переместиться по вертикали на одну единицу, по горизонтали на одну единицу, либо по диагонали sqrt(2) единиц (другими словами, переместиться на одну единицу по вертикали и на одну единицу по горизонтали за 1 секунду). Вы должны посетить точки в том же порядке, в котором они появляются в массиве. Вы можете проходить через точки, которые появляются позже в порядке, но они не считаются за посещение.
Пример:
👨💻 Алгоритм:
1⃣Инициализируйте переменную для хранения минимального времени.
2⃣Последовательно проходите по всем точкам и вычисляйте минимальное время для перехода от текущей точки к следующей.
3⃣Суммируйте время переходов для получения общего минимального времени.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
На двумерной плоскости имеется n точек с целочисленными координатами points[i] = [xi, yi]. Верните минимальное время в секундах для посещения всех точек в порядке, заданном точками. Вы можете перемещаться по следующим правилам: за 1 секунду вы можете либо: переместиться по вертикали на одну единицу, по горизонтали на одну единицу, либо по диагонали sqrt(2) единиц (другими словами, переместиться на одну единицу по вертикали и на одну единицу по горизонтали за 1 секунду). Вы должны посетить точки в том же порядке, в котором они появляются в массиве. Вы можете проходить через точки, которые появляются позже в порядке, но они не считаются за посещение.
Пример:
Input: points = [[1,1],[3,4],[-1,0]]
Output: 7
👨💻 Алгоритм:
1⃣Инициализируйте переменную для хранения минимального времени.
2⃣Последовательно проходите по всем точкам и вычисляйте минимальное время для перехода от текущей точки к следующей.
3⃣Суммируйте время переходов для получения общего минимального времени.
😎 Решение:
public class Solution {
public int minTimeToVisitAllPoints(int[][] points) {
int time = 0;
for (int i = 0; i < points.length - 1; i++) {
time += distance(points[i], points[i + 1]);
}
return time;
}
private int distance(int[] p1, int[] p2) {
return Math.max(Math.abs(p1[0] - p2[0]), Math.abs(p1[1] - p2[1]));
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 723. Candy Crush
Сложность: medium
Этот вопрос касается реализации базового алгоритма исключения для Candy Crush. Дан целочисленный массив board размером m x n, представляющий сетку конфет, где board[i][j] представляет тип конфеты. Значение board[i][j] == 0 означает, что ячейка пуста. Данная доска представляет собой состояние игры после хода игрока. Теперь необходимо вернуть доску в стабильное состояние, раздавив конфеты по следующим правилам: если три или более конфет одного типа находятся рядом по вертикали или горизонтали, раздавите их все одновременно - эти позиции станут пустыми. После одновременного раздавливания всех конфет, если на пустом месте доски есть конфеты, расположенные сверху, то эти конфеты будут падать, пока не ударятся о конфету или дно одновременно. Новые конфеты не будут падать за верхнюю границу. После выполнения описанных выше действий может остаться больше конфет, которые можно раздавить. Если конфет, которые можно раздавить, больше не существует (т. е. доска стабильна), верните текущую доску. Выполняйте описанные выше правила, пока доска не станет стабильной, затем верните стабильную доску.
Пример:
👨💻 Алгоритм:
1⃣Найдите все группы из трех или более одинаковых конфет, как в горизонтальном, так и в вертикальном направлениях, и отметьте их для удаления.
2⃣Удалите отмеченные конфеты, установив их значение в 0.
3⃣Переместите конфеты вниз, чтобы заполнить пустые ячейки, и повторите процесс, пока не останется групп конфет для удаления.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Этот вопрос касается реализации базового алгоритма исключения для Candy Crush. Дан целочисленный массив board размером m x n, представляющий сетку конфет, где board[i][j] представляет тип конфеты. Значение board[i][j] == 0 означает, что ячейка пуста. Данная доска представляет собой состояние игры после хода игрока. Теперь необходимо вернуть доску в стабильное состояние, раздавив конфеты по следующим правилам: если три или более конфет одного типа находятся рядом по вертикали или горизонтали, раздавите их все одновременно - эти позиции станут пустыми. После одновременного раздавливания всех конфет, если на пустом месте доски есть конфеты, расположенные сверху, то эти конфеты будут падать, пока не ударятся о конфету или дно одновременно. Новые конфеты не будут падать за верхнюю границу. После выполнения описанных выше действий может остаться больше конфет, которые можно раздавить. Если конфет, которые можно раздавить, больше не существует (т. е. доска стабильна), верните текущую доску. Выполняйте описанные выше правила, пока доска не станет стабильной, затем верните стабильную доску.
Пример:
Input: board = [[110,5,112,113,114],[210,211,5,213,214],[310,311,3,313,314],[410,411,412,5,414],[5,1,512,3,3],[610,4,1,613,614],[710,1,2,713,714],[810,1,2,1,1],[1,1,2,2,2],[4,1,4,4,1014]]
Output: [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[110,0,0,0,114],[210,0,0,0,214],[310,0,0,113,314],[410,0,0,213,414],[610,211,112,313,614],[710,311,412,613,714],[810,411,512,713,1014]]
👨💻 Алгоритм:
1⃣Найдите все группы из трех или более одинаковых конфет, как в горизонтальном, так и в вертикальном направлениях, и отметьте их для удаления.
2⃣Удалите отмеченные конфеты, установив их значение в 0.
3⃣Переместите конфеты вниз, чтобы заполнить пустые ячейки, и повторите процесс, пока не останется групп конфет для удаления.
😎 Решение:
public class Solution {
public int[][] candyCrush(int[][] board) {
int m = board.length;
int n = board[0].length;
boolean stable = false;
while (!stable) {
stable = true;
boolean[][] crush = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n - 2; j++) {
int v = Math.abs(board[i][j]);
if (v != 0 && v == Math.abs(board[i][j + 1]) && v == Math.abs(board[i][j + 2])) {
stable = false;
crush[i][j] = crush[i][j + 1] = crush[i][j + 2] = true;
}
}
}
for (int i = 0; i < m - 2; i++) {
for (int j = 0; j < n; j++) {
int v = Math.abs(board[i][j]);
if (v != 0 && v == Math.abs(board[i + 1][j]) && v == Math.abs(board[i + 2][j])) {
stable = false;
crush[i][j] = crush[i + 1][j] = crush[i + 2][j] = true;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (crush[i][j]) {
board[i][j] = 0;
}
}
}
for (int j = 0; j < n; j++) {
int idx = m - 1;
for (int i = m - 1; i >= 0; i--) {
if (board[i][j] != 0) {
board[idx][j] = board[i][j];
idx--;
}
}
for (int i = idx; i >= 0; i--) {
board[i][j] = 0;
}
}
}
return board;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 672. Bulb Switcher II
Сложность: medium
Есть комната с n лампочками, пронумерованными от 1 до n, которые изначально все включены, и четыре кнопки на стене. Каждая из четырех кнопок имеет разную функциональность:
Кнопка 1: Переключает состояние всех лампочек.
Кнопка 2: Переключает состояние всех лампочек с четными номерами (т.е. 2, 4, ...).
Кнопка 3: Переключает состояние всех лампочек с нечетными номерами (т.е. 1, 3, ...).
Кнопка 4: Переключает состояние всех лампочек с номером j = 3k + 1, где k = 0, 1, 2, ... (т.е. 1, 4, 7, 10, ...).
Необходимо сделать ровно presses нажатий кнопок. Для каждого нажатия можно выбрать любую из четырех кнопок для нажатия.
Даны два целых числа n и presses, вернуть количество различных возможных состояний после выполнения всех presses нажатий кнопок.
Пример:
👨💻 Алгоритм:
1⃣Рассчитаем возможные множества остатков: то есть какие множества c_i = f_i (mod 2) возможны.
2⃣Так как c_i ≡ f_i и c_i ≤ f_i, если ∑f_i ≠ ∑c_i, или если ∑f_i < ∑c_i, это невозможно. В противном случае это возможно простым построением: выполните операции, указанные c_i, затем выполните операцию номер 1 с четным числом оставшихся операций.
3⃣Для каждого возможного множества остатков симулируем и запоминаем, как будут выглядеть первые 6 лампочек, сохраняя это в структуре Set. В конце возвращаем размер этого множества.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Есть комната с n лампочками, пронумерованными от 1 до n, которые изначально все включены, и четыре кнопки на стене. Каждая из четырех кнопок имеет разную функциональность:
Кнопка 1: Переключает состояние всех лампочек.
Кнопка 2: Переключает состояние всех лампочек с четными номерами (т.е. 2, 4, ...).
Кнопка 3: Переключает состояние всех лампочек с нечетными номерами (т.е. 1, 3, ...).
Кнопка 4: Переключает состояние всех лампочек с номером j = 3k + 1, где k = 0, 1, 2, ... (т.е. 1, 4, 7, 10, ...).
Необходимо сделать ровно presses нажатий кнопок. Для каждого нажатия можно выбрать любую из четырех кнопок для нажатия.
Даны два целых числа n и presses, вернуть количество различных возможных состояний после выполнения всех presses нажатий кнопок.
Пример:
Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2
👨💻 Алгоритм:
1⃣Рассчитаем возможные множества остатков: то есть какие множества c_i = f_i (mod 2) возможны.
2⃣Так как c_i ≡ f_i и c_i ≤ f_i, если ∑f_i ≠ ∑c_i, или если ∑f_i < ∑c_i, это невозможно. В противном случае это возможно простым построением: выполните операции, указанные c_i, затем выполните операцию номер 1 с четным числом оставшихся операций.
3⃣Для каждого возможного множества остатков симулируем и запоминаем, как будут выглядеть первые 6 лампочек, сохраняя это в структуре Set. В конце возвращаем размер этого множества.
😎 Решение:
class Solution {
public int flipLights(int n, int m) {
Set<Integer> seen = new HashSet<>();
n = Math.min(n, 6);
int shift = Math.max(0, 6 - n);
for (int cand = 0; cand < 16; ++cand) {
int bcount = Integer.bitCount(cand);
if (bcount % 2 == m % 2 && bcount <= m) {
int lights = 0;
if (((cand >> 0) & 1) > 0) lights ^= 0b111111 >> shift;
if (((cand >> 1) & 1) > 0) lights ^= 0b010101 >> shift;
if (((cand >> 2) & 1) > 0) lights ^= 0b101010 >> shift;
if (((cand >> 3) & 1) > 0) lights ^= 0b100100 >> shift;
seen.add(lights);
}
}
return seen.size();
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1413. Minimum Value to Get Positive Step by Step Sum
Сложность: easy
Дан массив целых чисел nums, вы начинаете с начального положительного значения startValue.
На каждой итерации вы вычисляете поэтапную сумму startValue плюс элементы из nums (слева направо).
Верните минимальное положительное значение startValue, такое что поэтапная сумма никогда не будет меньше 1.
Пример:
👨💻 Алгоритм:
1⃣Инициализируйте переменные startValue со значением 1 и total со значением startValue.
2⃣Итеративно добавляйте каждый элемент массива nums к total и проверяйте, не опускается ли total ниже 1.
3⃣Если total падает ниже 1, увеличьте startValue на 1 и повторите шаги 2-3. Если total остается не менее 1, верните текущее значение startValue.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Дан массив целых чисел nums, вы начинаете с начального положительного значения startValue.
На каждой итерации вы вычисляете поэтапную сумму startValue плюс элементы из nums (слева направо).
Верните минимальное положительное значение startValue, такое что поэтапная сумма никогда не будет меньше 1.
Пример:
Input: nums = [-3,2,-3,4,2]
Output: 5
Explanation: If you choose startValue = 4, in the third iteration your step by step sum is less than 1.
step by step sum
startValue = 4 | startValue = 5 | nums
(4 -3 ) = 1 | (5 -3 ) = 2 | -3
(1 +2 ) = 3 | (2 +2 ) = 4 | 2
(3 -3 ) = 0 | (4 -3 ) = 1 | -3
(0 +4 ) = 4 | (1 +4 ) = 5 | 4
(4 +2 ) = 6 | (5 +2 ) = 7 | 2
👨💻 Алгоритм:
1⃣Инициализируйте переменные startValue со значением 1 и total со значением startValue.
2⃣Итеративно добавляйте каждый элемент массива nums к total и проверяйте, не опускается ли total ниже 1.
3⃣Если total падает ниже 1, увеличьте startValue на 1 и повторите шаги 2-3. Если total остается не менее 1, верните текущее значение startValue.
😎 Решение:
class Solution {
public int minStartValue(int[] nums) {
int startValue = 1;
while (true) {
int total = startValue;
boolean isValid = true;
for (int num : nums) {
total += num;
if (total < 1) {
isValid = false;
break;
}
}
if (isValid) {
return startValue;
} else {
startValue += 1;
}
}
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1120. Maximum Average Subtree
Сложность: medium
Дан корень бинарного дерева. Верните максимальное среднее значение поддерева этого дерева. Ответы, отличающиеся от фактического ответа не более чем на 10^-5, будут приняты.
Поддерево дерева — это любой узел этого дерева плюс все его потомки.
Среднее значение дерева — это сумма его значений, деленная на количество узлов.
Пример:
👨💻 Алгоритм:
1⃣Инициализация и определение State:
Определите класс State для хранения количества узлов в поддереве, суммы значений узлов в поддереве и максимального среднего значения поддерева.
2⃣Постобход (postorder traversal):
Реализуйте функцию maxAverage, которая выполняет постобход дерева, вычисляя nodeCount, valueSum и maxAverage для каждого узла, начиная с дочерних узлов и продвигаясь к родительским узлам.
3⃣Вычисление максимального среднего значения:
Используйте значения, полученные от дочерних узлов, для вычисления среднего значения для текущего узла и обновите maxAverage, если новое среднее значение больше текущего максимума.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дан корень бинарного дерева. Верните максимальное среднее значение поддерева этого дерева. Ответы, отличающиеся от фактического ответа не более чем на 10^-5, будут приняты.
Поддерево дерева — это любой узел этого дерева плюс все его потомки.
Среднее значение дерева — это сумма его значений, деленная на количество узлов.
Пример:
Input: root = [5,6,1]
Output: 6.00000
Explanation:
For the node with value = 5 we have an average of (5 + 6 + 1) / 3 = 4.
For the node with value = 6 we have an average of 6 / 1 = 6.
For the node with value = 1 we have an average of 1 / 1 = 1.
So the answer is 6 which is the maximum.
👨💻 Алгоритм:
1⃣Инициализация и определение State:
Определите класс State для хранения количества узлов в поддереве, суммы значений узлов в поддереве и максимального среднего значения поддерева.
2⃣Постобход (postorder traversal):
Реализуйте функцию maxAverage, которая выполняет постобход дерева, вычисляя nodeCount, valueSum и maxAverage для каждого узла, начиная с дочерних узлов и продвигаясь к родительским узлам.
3⃣Вычисление максимального среднего значения:
Используйте значения, полученные от дочерних узлов, для вычисления среднего значения для текущего узла и обновите maxAverage, если новое среднее значение больше текущего максимума.
😎 Решение:
class Solution {
class State {
int nodeCount;
int valueSum;
double maxAverage;
State(int nodes, int sum, double maxAverage) {
this.nodeCount = nodes;
this.valueSum = sum;
this.maxAverage = maxAverage;
}
}
public double maximumAverageSubtree(TreeNode root) {
return maxAverage(root).maxAverage;
}
State maxAverage(TreeNode root) {
if (root == null) {
return new State(0, 0, 0);
}
State left = maxAverage(root.left);
State right = maxAverage(root.right);
int nodeCount = left.nodeCount + right.nodeCount + 1;
int sum = left.valueSum + right.valueSum + root.val;
double maxAverage = Math.max(
(1.0 * (sum)) / nodeCount,
Math.max(right.maxAverage, left.maxAverage)
);
return new State(nodeCount, sum, maxAverage);
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1332. Remove Palindromic Subsequences
Сложность: easy
Вам дана строка s, состоящая только из букв 'a' и 'b'. За один шаг вы можете удалить одну палиндромную подпоследовательность из s.
Верните минимальное количество шагов, чтобы сделать данную строку пустой.
Строка является подпоследовательностью данной строки, если она создается путем удаления некоторых символов из данной строки без изменения их порядка. Обратите внимание, что подпоследовательность не обязательно должна быть непрерывной.
Строка называется палиндромом, если она читается одинаково как вперед, так и назад.
Пример:
👨💻 Алгоритм:
1⃣Если строка s уже является палиндромом, верните 1, так как можно удалить всю строку за один шаг.
2⃣Если строка s не является палиндромом, верните 2. В этом случае можно удалить все символы 'a' за один шаг, а затем все символы 'b' за второй шаг (или наоборот).
3⃣Таким образом, минимум шагов для опустошения строки всегда будет либо 1, либо 2, в зависимости от того, является ли строка палиндромом.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Вам дана строка s, состоящая только из букв 'a' и 'b'. За один шаг вы можете удалить одну палиндромную подпоследовательность из s.
Верните минимальное количество шагов, чтобы сделать данную строку пустой.
Строка является подпоследовательностью данной строки, если она создается путем удаления некоторых символов из данной строки без изменения их порядка. Обратите внимание, что подпоследовательность не обязательно должна быть непрерывной.
Строка называется палиндромом, если она читается одинаково как вперед, так и назад.
Пример:
Input: s = "ababa"
Output: 1
Explanation: s is already a palindrome, so its entirety can be removed in a single step.
👨💻 Алгоритм:
1⃣Если строка s уже является палиндромом, верните 1, так как можно удалить всю строку за один шаг.
2⃣Если строка s не является палиндромом, верните 2. В этом случае можно удалить все символы 'a' за один шаг, а затем все символы 'b' за второй шаг (или наоборот).
3⃣Таким образом, минимум шагов для опустошения строки всегда будет либо 1, либо 2, в зависимости от того, является ли строка палиндромом.
😎 Решение:
class Solution {
public int removePalindromeSub(String s) {
if (s.isEmpty()) {
return 0;
}
if (new StringBuilder(s).reverse().toString().equals(s)) {
return 1;
}
return 2;
}
}Ставь 👍 и забирай 📚 Базу знаний
🤔1
Задача: 229. Majority Element II
Сложность: medium
Дан массив целых чисел размера n, найдите все элементы, которые встречаются более ⌊ n/3 ⌋ раз.
Пример:
👨💻 Алгоритм:
1⃣Поиск кандидатов: Пройдите через массив, используя алгоритм Бойера-Мура для поиска двух потенциальных кандидатов, которые могут встречаться более ⌊ n/3 ⌋ раз. Поддерживайте два счётчика и двух кандидатов. Если текущий элемент равен одному из кандидатов, увеличьте соответствующий счётчик. Если счётчик равен нулю, установите текущий элемент как кандидата и установите счётчик в 1. Если текущий элемент не совпадает ни с одним из кандидатов, уменьшите оба счётчика.
2⃣Подсчёт голосов: После определения двух кандидатов, пройдите через массив снова, чтобы посчитать фактическое количество появлений каждого кандидата.
3⃣Проверка порога: Проверьте, превышает ли количество появлений каждого кандидата порог ⌊ n/3 ⌋. Если да, добавьте кандидата в результат.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дан массив целых чисел размера n, найдите все элементы, которые встречаются более ⌊ n/3 ⌋ раз.
Пример:
Input: nums = [3,2,3]
Output: [3]
👨💻 Алгоритм:
1⃣Поиск кандидатов: Пройдите через массив, используя алгоритм Бойера-Мура для поиска двух потенциальных кандидатов, которые могут встречаться более ⌊ n/3 ⌋ раз. Поддерживайте два счётчика и двух кандидатов. Если текущий элемент равен одному из кандидатов, увеличьте соответствующий счётчик. Если счётчик равен нулю, установите текущий элемент как кандидата и установите счётчик в 1. Если текущий элемент не совпадает ни с одним из кандидатов, уменьшите оба счётчика.
2⃣Подсчёт голосов: После определения двух кандидатов, пройдите через массив снова, чтобы посчитать фактическое количество появлений каждого кандидата.
3⃣Проверка порога: Проверьте, превышает ли количество появлений каждого кандидата порог ⌊ n/3 ⌋. Если да, добавьте кандидата в результат.
😎 Решение:
class Solution {
public List<Integer> majorityElement(int[] nums) {
int count1 = 0, count2 = 0;
Integer candidate1 = null, candidate2 = null;
for (int n : nums) {
if (candidate1 != null && candidate1 == n) {
count1++;
} else if (candidate2 != null && candidate2 == n) {
count2++;
} else if (count1 == 0) {
candidate1 = n;
count1 = 1;
} else if (count2 == 0) {
candidate2 = n;
count2 = 1;
} else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
for (int n : nums) {
if (candidate1 != null && candidate1 == n) count1++;
if (candidate2 != null && candidate2 == n) count2++;
}
List<Integer> result = new ArrayList<>();
int n = nums.length;
if (count1 > n / 3) result.add(candidate1);
if (count2 > n / 3) result.add(candidate2);
return result;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 735. Asteroid Collision
Сложность: medium
Нам дан массив asteroids, состоящий из целых чисел, представляющих астероиды в ряд. Для каждого астероида абсолютное значение обозначает его размер, а знак - направление движения (положительное - вправо, отрицательное - влево). Каждый астероид движется с одинаковой скоростью. Определите состояние астероидов после всех столкновений. Если два астероида столкнутся, меньший из них взорвется. Если оба одинакового размера, то взорвутся оба. Два астероида, движущиеся в одном направлении, никогда не встретятся.
Пример:
👨💻 Алгоритм:
1⃣Используйте стек для отслеживания движущихся вправо астероидов.
2⃣Пройдите по массиву астероидов: Если астероид движется вправо, добавьте его в стек. Если астероид движется влево, сравните его с последним астероидом в стеке (если он есть и движется вправо): Если движущийся вправо астероид больше, текущий взорвется. Если движущийся влево астероид больше, последний астероид в стеке взорвется, и продолжите сравнение. Если они одинакового размера, оба взорвутся.
3⃣Добавьте оставшиеся астероиды из стека и текущий астероид в результат.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Нам дан массив asteroids, состоящий из целых чисел, представляющих астероиды в ряд. Для каждого астероида абсолютное значение обозначает его размер, а знак - направление движения (положительное - вправо, отрицательное - влево). Каждый астероид движется с одинаковой скоростью. Определите состояние астероидов после всех столкновений. Если два астероида столкнутся, меньший из них взорвется. Если оба одинакового размера, то взорвутся оба. Два астероида, движущиеся в одном направлении, никогда не встретятся.
Пример:
Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","fine"],["drama","acting"],["skills","talent"]]
Output: true
👨💻 Алгоритм:
1⃣Используйте стек для отслеживания движущихся вправо астероидов.
2⃣Пройдите по массиву астероидов: Если астероид движется вправо, добавьте его в стек. Если астероид движется влево, сравните его с последним астероидом в стеке (если он есть и движется вправо): Если движущийся вправо астероид больше, текущий взорвется. Если движущийся влево астероид больше, последний астероид в стеке взорвется, и продолжите сравнение. Если они одинакового размера, оба взорвутся.
3⃣Добавьте оставшиеся астероиды из стека и текущий астероид в результат.
😎 Решение:
import java.util.*;
public class Solution {
public int[] asteroidCollision(int[] asteroids) {
Stack<Integer> stack = new Stack<>();
for (int asteroid : asteroids) {
boolean alive = true;
while (alive && asteroid < 0 && !stack.isEmpty() && stack.peek() > 0) {
int last = stack.pop();
if (last == -asteroid) {
alive = false;
} else if (last > -asteroid) {
stack.push(last);
alive = false;
}
}
if (alive) {
stack.push(asteroid);
}
}
int[] result = new int[stack.size()];
for (int i = result.length - 1; i >= 0; i--) {
result[i] = stack.pop();
}
return result;
}
}
Ставь 👍 и забирай 📚 Базу знаний
👍1
Задача: 1431. Kids With the Greatest Number of Candies
Сложность: easy
Дано n детей с конфетами. Вам дан целочисленный массив candies, где каждый candies[i] представляет количество конфет у i-го ребенка, и целое число extraCandies, обозначающее количество дополнительных конфет, которые у вас есть.
Вернуть булев массив result длиной n, где result[i] равно true, если, дав i-му ребенку все дополнительные конфеты, он будет иметь наибольшее количество конфет среди всех детей, или false в противном случае.
Обратите внимание, что несколько детей могут иметь наибольшее количество конфет.
Пример:
👨💻 Алгоритм:
1⃣Найдите максимальное количество конфет в массиве candies, сохраняя его в переменной maxCandies.
2⃣Создайте булев список answer и пройдитесь по массиву candies, добавляя в answer значение true, если текущий ребенок с добавленными extraCandies имеет количество конфет больше или равное maxCandies, иначе добавляйте false.
3⃣Верните список answer.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Дано n детей с конфетами. Вам дан целочисленный массив candies, где каждый candies[i] представляет количество конфет у i-го ребенка, и целое число extraCandies, обозначающее количество дополнительных конфет, которые у вас есть.
Вернуть булев массив result длиной n, где result[i] равно true, если, дав i-му ребенку все дополнительные конфеты, он будет иметь наибольшее количество конфет среди всех детей, или false в противном случае.
Обратите внимание, что несколько детей могут иметь наибольшее количество конфет.
Пример:
Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [true,true,true,false,true]
Explanation: If you give all extraCandies to:
- Kid 1, they will have 2 + 3 = 5 candies, which is the greatest among the kids.
- Kid 2, they will have 3 + 3 = 6 candies, which is the greatest among the kids.
- Kid 3, they will have 5 + 3 = 8 candies, which is the greatest among the kids.
- Kid 4, they will have 1 + 3 = 4 candies, which is not the greatest among the kids.
- Kid 5, they will have 3 + 3 = 6 candies, which is the greatest among the kids.
👨💻 Алгоритм:
1⃣Найдите максимальное количество конфет в массиве candies, сохраняя его в переменной maxCandies.
2⃣Создайте булев список answer и пройдитесь по массиву candies, добавляя в answer значение true, если текущий ребенок с добавленными extraCandies имеет количество конфет больше или равное maxCandies, иначе добавляйте false.
3⃣Верните список answer.
😎 Решение:
class Solution {
public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
int maxCandies = 0;
for (int candy : candies) {
maxCandies = Math.max(candy, maxCandies);
}
List<Boolean> result = new ArrayList<>();
for (int candy : candies) {
result.add(candy + extraCandies >= maxCandies);
}
return result;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 745. Prefix and Suffix Search
Сложность: hard
Создайте специальный словарь, в котором поиск слов осуществляется по префиксу и суффиксу. Реализуйте класс WordFilter: WordFilter(string[] words) Инициализирует объект со словами в словаре. f(string pref, string suff) Возвращает индекс слова в словаре, которое имеет префикс pref и суффикс suff. Если существует более одного допустимого индекса, возвращается наибольший из них. Если в словаре нет такого слова, возвращается -1.
Пример:
👨💻 Алгоритм:
1⃣Сохраните слова и их индексы в словаре.
2⃣Создайте объединенные ключи, состоящие из префиксов и суффиксов для всех возможных комбинаций.
3⃣Реализуйте функцию поиска, которая ищет наибольший индекс слова по префиксу и суффиксу.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
Создайте специальный словарь, в котором поиск слов осуществляется по префиксу и суффиксу. Реализуйте класс WordFilter: WordFilter(string[] words) Инициализирует объект со словами в словаре. f(string pref, string suff) Возвращает индекс слова в словаре, которое имеет префикс pref и суффикс suff. Если существует более одного допустимого индекса, возвращается наибольший из них. Если в словаре нет такого слова, возвращается -1.
Пример:
Input: letters = ["c","f","j"], target = "a"
Output: "c"
👨💻 Алгоритм:
1⃣Сохраните слова и их индексы в словаре.
2⃣Создайте объединенные ключи, состоящие из префиксов и суффиксов для всех возможных комбинаций.
3⃣Реализуйте функцию поиска, которая ищет наибольший индекс слова по префиксу и суффиксу.
😎 Решение:
public class WordFilter {
private Map<String, Integer> prefixSuffixMap = new HashMap<>();
public WordFilter(String[] words) {
for (int index = 0; index < words.length; index++) {
String word = words[index];
int length = word.length();
for (int prefixLength = 1; prefixLength <= length; prefixLength++) {
for (int suffixLength = 1; suffixLength <= length; suffixLength++) {
String prefix = word.substring(0, prefixLength);
String suffix = word.substring(length - suffixLength);
String key = prefix + "#" + suffix;
prefixSuffixMap.put(key, index);
}
}
}
}
public int f(String pref, String suff) {
String key = pref + "#" + suff;
return prefixSuffixMap.getOrDefault(key, -1);
}
}Ставь 👍 и забирай 📚 Базу знаний