Задача: 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;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 247. Strobogrammatic Number II
Сложность: medium
Дано целое число n, верните все стробограмматические числа длины n. Ответ можно возвращать в любом порядке.
Стробограмматическое число — это число, которое выглядит одинаково при повороте на 180 градусов (если посмотреть вверх ногами).
Пример:
👨💻 Алгоритм:
1⃣Инициализируйте структуру данных reversiblePairs, которая содержит все пары обратимых цифр. Вызовите и верните результат рекурсивной функции generateStroboNumbers(n, finalLength), где первый аргумент указывает, что текущий вызов создаст все стробограмматические числа длиной n, а второй аргумент указывает длину конечных стробограмматических чисел, которые мы будем генерировать, и будет использоваться для проверки возможности добавления '0' в начало и конец числа.
2⃣Создайте функцию generateStroboNumbers(n, finalLength), которая вернет все стробограмматические числа длиной n:
Проверьте базовые случаи: если n == 0, верните массив с пустой строкой [""]; если n == 1, верните ["0", "1", "8"].
Вызовите generateStroboNumbers(n - 2, finalLength), чтобы получить все стробограмматические числа длиной (n-2), и сохраните их в subAns.
Инициализируйте пустой массив currStroboNums для хранения стробограмматических чисел длиной n.
3⃣Для каждого числа в subAns добавьте все reversiblePairs в начало и конец, за исключением случая, когда текущая пара '00' и n == finalLength (потому что нельзя добавить '0' в начало числа), и добавьте это новое число в currStroboNums. В конце функции верните все стробограмматические числа, т.е. currStroboNums.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дано целое число n, верните все стробограмматические числа длины n. Ответ можно возвращать в любом порядке.
Стробограмматическое число — это число, которое выглядит одинаково при повороте на 180 градусов (если посмотреть вверх ногами).
Пример:
Input: n = 2
Output: ["11","69","88","96"]
👨💻 Алгоритм:
1⃣Инициализируйте структуру данных reversiblePairs, которая содержит все пары обратимых цифр. Вызовите и верните результат рекурсивной функции generateStroboNumbers(n, finalLength), где первый аргумент указывает, что текущий вызов создаст все стробограмматические числа длиной n, а второй аргумент указывает длину конечных стробограмматических чисел, которые мы будем генерировать, и будет использоваться для проверки возможности добавления '0' в начало и конец числа.
2⃣Создайте функцию generateStroboNumbers(n, finalLength), которая вернет все стробограмматические числа длиной n:
Проверьте базовые случаи: если n == 0, верните массив с пустой строкой [""]; если n == 1, верните ["0", "1", "8"].
Вызовите generateStroboNumbers(n - 2, finalLength), чтобы получить все стробограмматические числа длиной (n-2), и сохраните их в subAns.
Инициализируйте пустой массив currStroboNums для хранения стробограмматических чисел длиной n.
3⃣Для каждого числа в subAns добавьте все reversiblePairs в начало и конец, за исключением случая, когда текущая пара '00' и n == finalLength (потому что нельзя добавить '0' в начало числа), и добавьте это новое число в currStroboNums. В конце функции верните все стробограмматические числа, т.е. currStroboNums.
😎 Решение:
import java.util.*;
class Solution {
List<List<Character>> reversiblePairs = Arrays.asList(
Arrays.asList('0', '0'), Arrays.asList('1', '1'),
Arrays.asList('6', '9'), Arrays.asList('8', '8'), Arrays.asList('9', '6')
);
public List<String> generateStroboNumbers(int n, int finalLength) {
if (n == 0) {
return Arrays.asList("");
}
if (n == 1) {
return Arrays.asList("0", "1", "8");
}
List<String> prevStroboNums = generateStroboNumbers(n - 2, finalLength);
List<String> currStroboNums = new ArrayList<>();
for (String prevStroboNum : prevStroboNums) {
for (List<Character> pair : reversiblePairs) {
if (pair.get(0) != '0' || n != finalLength) {
currStroboNums.add(pair.get(0) + prevStroboNum + pair.get(1));
}
}
}
return currStroboNums;
}
public List<String> findStrobogrammatic(int n) {
return generateStroboNumbers(n, n);
}
}
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1345. Jump Game IV
Сложность: hard
Дан массив целых чисел arr, изначально вы находитесь на первом индексе массива.
За один шаг вы можете прыгнуть с индекса i на индекс:
- i + 1, где: i + 1 < arr.length.
- i - 1, где: i - 1 >= 0.
- j, где: arr[i] == arr[j] и i != j.
Вернуть минимальное количество шагов, чтобы достичь последнего индекса массива.
Обратите внимание, что нельзя прыгать за пределы массива в любой момент времени.
Пример:
👨💻 Алгоритм:
1⃣Построить граф, где ключи - значения из массива, а значения - списки индексов этих значений. Начать с первого индекса, добавив его в очередь текущего слоя и инициализировать набор посещенных индексов.
2⃣Выполнять BFS: для каждого индекса текущего слоя проверять соседние индексы (i + 1, i - 1 и все j, где arr[i] == arr[j]), добавляя непосещенные индексы в очередь следующего слоя.
3⃣Повторять шаг 2, увеличивая счетчик шагов до достижения последнего индекса или пока не закончится очередь.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
Дан массив целых чисел arr, изначально вы находитесь на первом индексе массива.
За один шаг вы можете прыгнуть с индекса i на индекс:
- i + 1, где: i + 1 < arr.length.
- i - 1, где: i - 1 >= 0.
- j, где: arr[i] == arr[j] и i != j.
Вернуть минимальное количество шагов, чтобы достичь последнего индекса массива.
Обратите внимание, что нельзя прыгать за пределы массива в любой момент времени.
Пример:
Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.
👨💻 Алгоритм:
1⃣Построить граф, где ключи - значения из массива, а значения - списки индексов этих значений. Начать с первого индекса, добавив его в очередь текущего слоя и инициализировать набор посещенных индексов.
2⃣Выполнять BFS: для каждого индекса текущего слоя проверять соседние индексы (i + 1, i - 1 и все j, где arr[i] == arr[j]), добавляя непосещенные индексы в очередь следующего слоя.
3⃣Повторять шаг 2, увеличивая счетчик шагов до достижения последнего индекса или пока не закончится очередь.
😎 Решение:
class Solution {
public int minJumps(int[] arr) {
int n = arr.length;
if (n <= 1) {
return 0;
}
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int i = 0; i < n; i++) {
graph.computeIfAbsent(arr[i], v -> new LinkedList<>()).add(i);
}
List<Integer> curs = new LinkedList<>();
curs.add(0);
Set<Integer> visited = new HashSet<>();
int step = 0;
while (!curs.isEmpty()) {
List<Integer> nex = new LinkedList<>();
for (int node : curs) {
if (node == n - 1) {
return step;
}
for (int child : graph.get(arr[node])) {
if (!visited.contains(child)) {
visited.add(child);
nex.add(child);
}
}
graph.get(arr[node]).clear();
if (node + 1 < n && !visited.contains(node + 1)) {
visited.add(node + 1);
nex.add(node + 1);
}
if (node - 1 >= 0 && !visited.contains(node - 1)) {
visited.add(node - 1);
nex.add(node - 1);
}
}
curs = nex;
step++;
}
return -1;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 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);
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1380. Lucky Numbers in a Matrix
Сложность: easy
Дана матрица m x n из различных чисел, верните все счастливые числа в матрице в любом порядке.
Счастливое число — это элемент матрицы, который является минимальным элементом в своей строке и максимальным в своем столбце.
Пример:
👨💻 Алгоритм:
1⃣Сохраните минимум каждой строки в список rowMin и максимум каждого столбца в список colMax.
2⃣Итерируйте по каждому числу в матрице и проверяйте, равно ли оно rowMin[i] и colMax[j].
3⃣Если число удовлетворяет условию, добавьте его в список luckyNumbers и верните luckyNumbers.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Дана матрица m x n из различных чисел, верните все счастливые числа в матрице в любом порядке.
Счастливое число — это элемент матрицы, который является минимальным элементом в своей строке и максимальным в своем столбце.
Пример:
Input: matrix = [[3,7,8],[9,11,13],[15,16,17]]
Output: [15]
Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column.
👨💻 Алгоритм:
1⃣Сохраните минимум каждой строки в список rowMin и максимум каждого столбца в список colMax.
2⃣Итерируйте по каждому числу в матрице и проверяйте, равно ли оно rowMin[i] и colMax[j].
3⃣Если число удовлетворяет условию, добавьте его в список luckyNumbers и верните luckyNumbers.
😎 Решение:
class Solution {
public List<Integer> luckyNumbers (int[][] matrix) {
int N = matrix.length;
int M = matrix[0].length;
List<Integer> rowMin = new ArrayList<>();
for (int i = 0; i < N; i++) {
int rMin = Integer.MAX_VALUE;
for (int j = 0; j < M; j++) {
rMin = Math.min(rMin, matrix[i][j]);
}
rowMin.add(rMin);
}
List<Integer> colMax = new ArrayList<>();
for (int i = 0; i < M; i++) {
int cMax = Integer.MIN_VALUE;
for (int j = 0; j < N; j++) {
cMax = Math.max(cMax, matrix[j][i]);
}
colMax.add(cMax);
}
List<Integer> luckyNumbers = new ArrayList<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (matrix[i][j] == rowMin.get(i) && matrix[i][j] == colMax.get(j)) {
luckyNumbers.add(matrix[i][j]);
}
}
}
return luckyNumbers;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 55. Jump Game
Сложность: medium
Вам дан массив целых чисел nums. Изначально вы находитесь на первом индексе массива, и каждый элемент массива представляет вашу максимальную длину прыжка в этой позиции.
Верните true, если вы можете достичь последнего индекса, или false в противном случае.
Пример:
👨💻Алгоритм:
1⃣Инициализация таблицы памяти:
Изначально все элементы таблицы памяти имеют статус UNKNOWN, за исключением последнего, который является (тривиально) GOOD (может достичь сам себя).
2⃣Модификация алгоритма обратного трассирования:
Измените алгоритм обратного трассирования таким образом, чтобы на рекурсивном шаге сначала проверялось, известен ли индекс (GOOD/BAD).
Если индекс известен, тогда возвращается True/False.
3⃣Выполнение и сохранение результатов:
Если индекс не известен, выполняйте шаги обратного трассирования, как ранее.
После определения значения текущего индекса, сохраните его в таблице памяти.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Вам дан массив целых чисел nums. Изначально вы находитесь на первом индексе массива, и каждый элемент массива представляет вашу максимальную длину прыжка в этой позиции.
Верните true, если вы можете достичь последнего индекса, или false в противном случае.
Пример:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
👨💻Алгоритм:
1⃣Инициализация таблицы памяти:
Изначально все элементы таблицы памяти имеют статус UNKNOWN, за исключением последнего, который является (тривиально) GOOD (может достичь сам себя).
2⃣Модификация алгоритма обратного трассирования:
Измените алгоритм обратного трассирования таким образом, чтобы на рекурсивном шаге сначала проверялось, известен ли индекс (GOOD/BAD).
Если индекс известен, тогда возвращается True/False.
3⃣Выполнение и сохранение результатов:
Если индекс не известен, выполняйте шаги обратного трассирования, как ранее.
После определения значения текущего индекса, сохраните его в таблице памяти.
😎 Решение:
enum Index {
GOOD,
BAD,
UNKNOWN,
}
public class Solution {
Index[] memo;
public boolean canJumpFromPosition(int position, int[] nums) {
if (memo[position] != Index.UNKNOWN) {
return memo[position] == Index.GOOD;
}
int furthestJump = Math.min(position + nums[position], nums.length - 1);
for (int nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) {
if (canJumpFromPosition(nextPosition, nums)) {
memo[position] = Index.GOOD;
return true;
}
}
memo[position] = Index.BAD;
return false;
}
public boolean canJump(int[] nums) {
memo = new Index[nums.length];
for (int i = 0; i < memo.length; i++) {
memo[i] = Index.UNKNOWN;
}
memo[memo.length - 1] = Index.GOOD;
return canJumpFromPosition(0, nums);
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 634. Find the Derangement of An Array
Сложность: medium
В комбинаторной математике отклонение - это перестановка элементов множества таким образом, что ни один элемент не оказывается на прежнем месте. Вам дано целое число n. Изначально имеется массив, состоящий из n целых чисел от 1 до n в порядке возрастания, верните количество отклонений, которые он может породить. Поскольку ответ может быть огромным, верните его по модулю 109 + 7.
Пример:
👨💻 Алгоритм:
1⃣Инициализация массива для хранения результатов: Создайте массив dp для хранения количества отклонений для каждого значения от 0 до n. Установите начальные значения: dp[0] = 1 и dp[1] = 0.
2⃣Вычисление количества отклонений: Используйте динамическое программирование для вычисления количества отклонений для каждого значения от 2 до n. Формула для вычисления: dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD.
3⃣Возвращение результата: Верните значение dp[n], которое будет количеством отклонений для n элементов, по модулю 10^9 + 7.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
В комбинаторной математике отклонение - это перестановка элементов множества таким образом, что ни один элемент не оказывается на прежнем месте. Вам дано целое число n. Изначально имеется массив, состоящий из n целых чисел от 1 до n в порядке возрастания, верните количество отклонений, которые он может породить. Поскольку ответ может быть огромным, верните его по модулю 109 + 7.
Пример:
Input: n = 3
Output: 2
👨💻 Алгоритм:
1⃣Инициализация массива для хранения результатов: Создайте массив dp для хранения количества отклонений для каждого значения от 0 до n. Установите начальные значения: dp[0] = 1 и dp[1] = 0.
2⃣Вычисление количества отклонений: Используйте динамическое программирование для вычисления количества отклонений для каждого значения от 2 до n. Формула для вычисления: dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD.
3⃣Возвращение результата: Верните значение dp[n], которое будет количеством отклонений для n элементов, по модулю 10^9 + 7.
😎 Решение:
public class Solution {
public int countDerangements(int n) {
final int MOD = 1000000007;
if (n == 0) return 1;
if (n == 1) return 0;
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 0;
for (int i = 2; i <= n; i++) {
dp[i] = (int)((long)(i - 1) * (dp[i - 1] + dp[i - 2]) % MOD);
}
return dp[n];
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 759. Employee Free Time
Сложность: hard
Нам дан список schedule of employees, который представляет собой рабочее время каждого сотрудника. У каждого сотрудника есть список непересекающихся интервалов, и эти интервалы расположены в отсортированном порядке. Верните список конечных интервалов, представляющих общее свободное время положительной длины для всех сотрудников, также в отсортированном порядке. (Хотя мы представляем интервалы в форме [x, y], объекты внутри них являются интервалами, а не списками или массивами. Например, schedule[0][0].start = 1, schedule[0][0].end = 2, а schedule[0][0][0] не определено).Также мы не будем включать в наш ответ интервалы типа [5, 5], так как они имеют нулевую длину.
Пример:
👨💻 Алгоритм:
1⃣Объедините все интервалы всех сотрудников в один список и отсортируйте его по начальным временам.
2⃣Объедините пересекающиеся интервалы в один.
3⃣Найдите промежутки между объединенными интервалами, представляющие свободное время.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
Нам дан список schedule of employees, который представляет собой рабочее время каждого сотрудника. У каждого сотрудника есть список непересекающихся интервалов, и эти интервалы расположены в отсортированном порядке. Верните список конечных интервалов, представляющих общее свободное время положительной длины для всех сотрудников, также в отсортированном порядке. (Хотя мы представляем интервалы в форме [x, y], объекты внутри них являются интервалами, а не списками или массивами. Например, schedule[0][0].start = 1, schedule[0][0].end = 2, а schedule[0][0][0] не определено).Также мы не будем включать в наш ответ интервалы типа [5, 5], так как они имеют нулевую длину.
Пример:
Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]
👨💻 Алгоритм:
1⃣Объедините все интервалы всех сотрудников в один список и отсортируйте его по начальным временам.
2⃣Объедините пересекающиеся интервалы в один.
3⃣Найдите промежутки между объединенными интервалами, представляющие свободное время.
😎 Решение:
import java.util.*;
class Interval {
public int start;
public int end;
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
}
public class Solution {
public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
List<Interval> intervals = new ArrayList<>();
for (List<Interval> employee : schedule) {
intervals.addAll(employee);
}
intervals.sort((a, b) -> Integer.compare(a.start, b.start));
List<Interval> merged = new ArrayList<>();
for (Interval interval : intervals) {
if (merged.isEmpty() || merged.get(merged.size() - 1).end < interval.start) {
merged.add(interval);
} else {
merged.get(merged.size() - 1).end = Math.max(merged.get(merged.size() - 1).end, interval.end);
}
}
List<Interval> freeTime = new ArrayList<>();
for (int i = 1; i < merged.size(); i++) {
if (merged.get(i).start > merged.get(i - 1).end) {
freeTime.add(new Interval(merged.get(i - 1).end, merged.get(i).start));
}
}
return freeTime;
}
Ставь 👍 и забирай 📚 Базу знаний
🔥 Скрытые вакансии с удаленной работой для Java разработчика, которые нигде больше не публикуются. Напрямую от компаний, с контактами рекрутеров.
🔹 Java Jobs | Вакансии
🔸 Все каналы с вакансиями
🔹 Java Jobs | Вакансии
🔸 Все каналы с вакансиями
Задача: 1199. Minimum Time to Build Blocks
Сложность: hard
Вам дан список блоков, где blocks[i] = t означает, что на строительство i-го блока требуется t единиц времени. Блок может быть построен только одним рабочим.
Рабочий может либо разделиться на двух рабочих (количество рабочих увеличивается на одного), либо построить блок и уйти домой. Оба решения требуют некоторого времени.
Время, затраченное на разделение одного рабочего на двух, задано целым числом split. Обратите внимание, что если два рабочих разделяются одновременно, они разделяются параллельно, поэтому затраты времени будут равны split.
Выведите минимальное время, необходимое для строительства всех блоков.
Изначально есть только один рабочий.
Пример:
👨💻 Алгоритм:
1⃣Подготовка кучи строительного времени:
Инициализируйте кучу строительного времени, изначально содержащую все значения времени из массива blocks.
2⃣Обработка кучи:
Пока в куче больше одного элемента:
- извлеките минимальное значение из кучи, обозначим его как x.
- извлеките следующее минимальное значение из кучи, обозначим его как y.
- создайте новое время строительства, которое равно split + y, и вставьте его обратно в кучу.
3⃣Возврат результата:
Когда в куче останется только одно значение, оно и будет минимальным временем, необходимым для строительства всех блоков.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
Вам дан список блоков, где blocks[i] = t означает, что на строительство i-го блока требуется t единиц времени. Блок может быть построен только одним рабочим.
Рабочий может либо разделиться на двух рабочих (количество рабочих увеличивается на одного), либо построить блок и уйти домой. Оба решения требуют некоторого времени.
Время, затраченное на разделение одного рабочего на двух, задано целым числом split. Обратите внимание, что если два рабочих разделяются одновременно, они разделяются параллельно, поэтому затраты времени будут равны split.
Выведите минимальное время, необходимое для строительства всех блоков.
Изначально есть только один рабочий.
Пример:
Input: blocks = [1,2,3], split = 1
Output: 4
Explanation: Split 1 worker into 2, then assign the first worker to the last block and split the second worker into 2.
Then, use the two unassigned workers to build the first two blocks.
The cost is 1 + max(3, 1 + max(1, 2)) = 4.
👨💻 Алгоритм:
1⃣Подготовка кучи строительного времени:
Инициализируйте кучу строительного времени, изначально содержащую все значения времени из массива blocks.
2⃣Обработка кучи:
Пока в куче больше одного элемента:
- извлеките минимальное значение из кучи, обозначим его как x.
- извлеките следующее минимальное значение из кучи, обозначим его как y.
- создайте новое время строительства, которое равно split + y, и вставьте его обратно в кучу.
3⃣Возврат результата:
Когда в куче останется только одно значение, оно и будет минимальным временем, необходимым для строительства всех блоков.
😎 Решение:
class Solution {
public int minBuildTime(int[] blocks, int split) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int block : blocks) {
pq.offer(block);
}
while (pq.size() > 1) {
int x = pq.poll();
int y = pq.poll();
pq.offer(split + y);
}
return pq.poll();
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 350. Intersection of Two Arrays II
Сложность: easy
Даны два целочисленных массива nums1 и nums2. Верните массив их пересечения. Каждый элемент в результате должен появляться столько раз, сколько он встречается в обоих массивах. Вы можете вернуть результат в любом порядке.
Пример:
👨💻 Алгоритм:
1⃣Подсчет частоты элементов:
Используйте хеш-таблицу или словарь для подсчета количества вхождений каждого элемента в nums1.
2⃣Нахождение пересечения:
Пройдите по элементам nums2, и если элемент присутствует в хеш-таблице из шага 1 и его счетчик больше нуля, добавьте этот элемент в результат и уменьшите счетчик.
3⃣Возврат результата:
Верните массив пересечения.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Даны два целочисленных массива nums1 и nums2. Верните массив их пересечения. Каждый элемент в результате должен появляться столько раз, сколько он встречается в обоих массивах. Вы можете вернуть результат в любом порядке.
Пример:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]
👨💻 Алгоритм:
1⃣Подсчет частоты элементов:
Используйте хеш-таблицу или словарь для подсчета количества вхождений каждого элемента в nums1.
2⃣Нахождение пересечения:
Пройдите по элементам nums2, и если элемент присутствует в хеш-таблице из шага 1 и его счетчик больше нуля, добавьте этот элемент в результат и уменьшите счетчик.
3⃣Возврат результата:
Верните массив пересечения.
😎 Решение:
import java.util.*;
public class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Map<Integer, Integer> counts = new HashMap<>();
List<Integer> result = new ArrayList<>();
for (int num : nums1) {
counts.put(num, counts.getOrDefault(num, 0) + 1);
}
for (int num : nums2) {
if (counts.getOrDefault(num, 0) > 0) {
result.add(num);
counts.put(num, counts.get(num) - 1);
}
}
int[] resArray = new int[result.size()];
for (int i = 0; i < result.size(); i++) {
resArray[i] = result.get(i);
}
return resArray;
}
}
Ставь 👍 и забирай 📚 Базу знаний
Задача: 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;
}
}Ставь 👍 и забирай 📚 Базу знаний