اکنون در دسترس! پژوهش تلگرام ۲۰۲۵ — مهمترین بینشهای سال 
Java | LeetCode
رفتن به کانال در Telegram
Cайт easyoffer.ru Реклама @easyoffer_adv ВП @easyoffer_vp Тесты t.me/+icUwivvbGOkwNWRi Вопросы собесов t.me/+7ESm0VKXC4tjYzky Вакансии t.me/+4pspF5nDjgM4MjQy
نمایش بیشتر6 665
مشترکین
-124 ساعت
-157 روز
-3930 روز
آرشیو پست ها
6 662
Задача: 1033. Moving Stones Until Consecutive
Сложность: medium
На оси X расположены три камня в разных позициях. Вам даны три целых числа a, b и c - позиции камней. За одно движение вы берете камень в конечной точке (т. е. либо в самой низкой, либо в самой высокой позиции камня) и перемещаете его в незанятую позицию между этими конечными точками. Формально, допустим, камни в данный момент находятся в позициях x, y и z, причем x < y < z. Вы берете камень в позиции x или z и перемещаете его в целочисленную позицию k, причем x < k < z и k != y. Игра заканчивается, когда вы больше не можете сделать ни одного хода (то есть камни находятся в трех последовательных позициях). Возвращается целочисленный массив answer длины 2, где: answer[0] - минимальное количество ходов, которое вы можете сыграть, а answer[1] - максимальное количество ходов, которое вы можете сыграть.
Пример:
Input: a = 3, b = 5, c = 1 Output: [1,2]👨💻 Алгоритм: 1⃣Сортировка позиций: Убедитесь, что позиции камней отсортированы в порядке возрастания. Обозначим отсортированные позиции как x, y и z. 2⃣Вычисление минимальных ходов: Если камни уже находятся в последовательных позициях (то есть y - x == 1 и z - y == 1), минимальное количество ходов равно 0. Если два камня находятся в соседних позициях, а третий камень на расстоянии более чем одна позиция, минимальное количество ходов равно 1. В остальных случаях минимальное количество ходов равно 2. 3⃣Вычисление максимальных ходов: Максимальное количество ходов равно сумме расстояний между соседними камнями минус 2, то есть (y - x - 1) + (z - y - 1). 😎 Решение:
public class Solution {
public int[] numMovesStones(int a, int b, int c) {
int[] stones = new int[] { a, b, c };
Arrays.sort(stones);
int x = stones[0], y = stones[1], z = stones[2];
int minMoves = (y - x <= 2 || z - y <= 2) ? ((y - x == 1 && z - y == 1) ? 0 : 1) : 2;
int maxMoves = (y - x - 1) + (z - y - 1);
return new int[] { minMoves, maxMoves };
}
}6 662
Java.hasChosen(you)
🥶😟
Почему Java всё ещё №1 в автотестах?
Стас Васенков, основатель школы автотестировщиков @qa_guru, расскажет про свой мэтч с Java. Чем его зацепил этот язык и куда привёл. И куда Java может привести вас.
Приходите на открытый эфир ➡ 27 января ➡ 13:00 (МСК)
Что будет:
— неочевидные карьерные сценарии
— внутрянка: какой стек ждут, когда ищут автоматизатора
— кому Java уже не поможет 🐹
Не откладываем в TODO ➡ webinar.join();6 662
Задача: 920. Number of Music Playlists
Сложность: hard
В вашем плеере есть n разных песен. Во время путешествия вы хотите прослушать goal песен (не обязательно разных). Чтобы избежать скуки, вы создадите плейлист таким образом, чтобы: каждая песня играла хотя бы один раз. Песня может быть проиграна снова только в том случае, если было проиграно k других песен. Учитывая n, цель и k, верните количество возможных плейлистов, которые вы можете создать. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.
Пример:
Input: n = 3, goal = 3, k = 1 Output: 6👨💻 Алгоритм: 1⃣Создать двумерный массив dp, где dp[i][j] представляет количество возможных плейлистов длины i, содержащих j различных песен. 2⃣Инициализировать dp[0][0] = 1, что означает, что существует один способ создать плейлист длины 0 с 0 песнями. Заполнить массив dp, используя два случая: Добавление новой песни, которая не была проиграна раньше: dp[i][j] += dp[i-1][j-1] * (n - j + 1) Повторное проигрывание песни, если было проиграно k других песен: dp[i][j] += dp[i-1][j] * max(j - k, 0) 3⃣Ответ находится в dp[goal][n]. 😎 Решение:
class Solution {
public int numMusicPlaylists(int n, int goal, int k) {
final int MOD = 1_000_000_007;
long[][] dp = new long[goal + 1][n + 1];
dp[0][0] = 1;
for (int i = 1; i <= goal; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = dp[i-1][j-1] * (n - j + 1) % MOD;
if (j > k) {
dp[i][j] = (dp[i][j] + dp[i-1][j] * (j - k) % MOD) % MOD;
}
}
}
return (int) dp[goal][n];
}
}6 662
Задача: 664. Strange Printer
Сложность: hard
Существует странный принтер с двумя особыми свойствами:
Принтер может печатать последовательность одного и того же символа за раз.
На каждом шагу принтер может печатать новые символы, начиная и заканчивая в любом месте, при этом покрывая уже существующие символы.
Дана строка s. Верните минимальное количество ходов, необходимых для её печати.
Пример:
Input: s = "aaabbb" Output: 2 Explanation: Print "aaa" first and then print "bbb".👨💻 Алгоритм: 1⃣Инициализация и подсчет: Создайте двумерный массив dp, где dp[i][j] представляет минимальное количество ходов для печати подстроки s[i:j+1]. 2⃣Динамическое программирование: Если s[i] == s[j], тогда dp[i][j] = dp[i][j-1], так как последний символ совпадает с предыдущим. В противном случае, dp[i][j] = min(dp[i][k] + dp[k+1][j]) для всех i <= k < j, чтобы найти минимальное количество ходов. 3⃣Возврат результата: Возвратите dp[0][n-1], где n - длина строки s, что представляет минимальное количество ходов для печати всей строки. 😎 Решение:
public class Solution {
public int strangePrinter(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for (int length = 1; length <= n; length++) {
for (int i = 0; i <= n - length; i++) {
int j = i + length - 1;
dp[i][j] = (i == j) ? 1 : dp[i][j - 1] + 1;
for (int k = i; k < j; k++) {
if (s.charAt(k) == s.charAt(j)) {
dp[i][j] = Math.min(dp[i][j], dp[i][k] + (k + 1 <= j - 1 ? dp[k + 1][j - 1] : 0));
}
}
}
}
return dp[0][n - 1];
}
}6 662
Задача: 189. Rotate Array
Сложность: medium
Для целочисленного массива nums, поверните массив вправо на k шагов, где k — неотрицательное число.
Пример:
Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4]👨💻 Алгоритм: 1⃣Создаем дополнительный массив, в который будем помещать каждый элемент исходного массива на его новую позицию. Элемент на позиции i в исходном массиве будет размещен на индексе (i+k) % длина массива. 2⃣Копируем элементы из нового массива в исходный массив, сохраняя новый порядок элементов. 3⃣Заменяем исходный массив полученным результатом, завершая процесс поворота массива. 😎 Решение:
class Solution {
public void rotate(int[] nums, int k) {
int[] a = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
a[(i + k) % nums.length] = nums[i];
}
for (int i = 0; i < nums.length; i++) {
nums[i] = a[i];
}
}
}6 662
Задача: №16. 3Sum Closest
Сложность: medium
Учитывая целочисленный массив
nums длины n и целочисленную target, найдите три целых числа в nums, сумма которых наиболее близка к target.
Возвращается сумма этих трех чисел.
Гарантируется, что существует ровно одно решение.
Пример:
Input: licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"] Output: "steps"👨💻 Алгоритм: 1⃣Отсортировать массив
nums.
2⃣Для каждого элемента использовать два указателя: один в начале оставшегося массива, другой — в конце.
3⃣Обновлять текущую минимальную разницу и ближайшую сумму при необходимости, сдвигая указатели в зависимости от того, насколько текущая сумма отклоняется от target.
😎 Решение:
class Solution {
public int threeSumClosest(int[] nums, int target) {
int n = nums.length;
int closest = 0;
int max = Integer.MAX_VALUE;
Arrays.sort(nums);
for(int i = 0; i < n - 2; i++) {
int j = i + 1;
int k = n - 1;
while(j < k) {
int sum = nums[i] + nums[j] + nums[k];
if(sum == target)
return sum;
else if(sum < target)
j++;
else
k--;
int diff = Math.abs(sum - target);
if(diff < max) {
max = diff;
closest = sum;
}
}
}
return closest;
}
}6 662
Задача: 1326. Minimum Number of Taps to Open to Water a Garden
Сложность: hard
Есть одномерный сад на оси x. Сад начинается в точке 0 и заканчивается в точке n. (т.е. длина сада равна n).
В саду есть n + 1 кранов, расположенных в точках [0, 1, ..., n].
Даны целое число n и целочисленный массив ranges длиной n + 1, где ranges[i] (индексация начинается с 0) означает, что i-й кран может поливать область [i - ranges[i], i + ranges[i]], если он открыт.
Верните минимальное количество кранов, которые должны быть открыты для полива всего сада. Если сад невозможно полить, верните -1.
Пример:
Input: n = 5, ranges = [3,4,1,1,0,0]
Output: 1
Explanation: The tap at point 0 can cover the interval [-3,3]
The tap at point 1 can cover the interval [-3,5]
The tap at point 2 can cover the interval [1,3]
The tap at point 3 can cover the interval [2,4]
The tap at point 4 can cover the interval [4,4]
The tap at point 5 can cover the interval [5,5]
Opening Only the second tap will water the whole garden [0,5]class Solution {
public int minTaps(int n, int[] ranges) {
int INF = (int) 1e9;
int[] dp = new int[n + 1];
Arrays.fill(dp, INF);
dp[0] = 0;
for (int i = 0; i <= n; i++) {
int tapStart = Math.max(0, i - ranges[i]);
int tapEnd = Math.min(n, i + ranges[i]);
for (int j = tapStart; j <= tapEnd; j++) {
dp[tapEnd] = Math.min(dp[tapEnd], dp[j] + 1);
}
}
return dp[n] == INF ? -1 : dp[n];
}
}6 662
Задача: 292. Nim Game
Сложность: easy
Вы играете в следующую игру Nim со своим другом:
Изначально на столе лежит куча камней.
Вы и ваш друг поочередно делаете ходы, и вы ходите первым.
Каждый ход игрок, чей ход, будет убирать от 1 до 3 камней из кучи.
Тот, кто убирает последний камень, становится победителем.
Дано n, количество камней в куче. Верните true, если вы можете выиграть игру, предполагая, что и вы, и ваш друг играете оптимально, иначе верните false.
Пример:
Input: n = 4 Output: false Explanation: These are the possible outcomes: 1. You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins. 2. You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins. 3. You remove 3 stones. Your friend removes the last stone. Your friend wins. In all outcomes, your friend wins.👨💻 Алгоритм: 1⃣Определите базовый случай: Если количество камней n меньше или равно 3, вы всегда можете выиграть, убрав все камни. В этом случае верните true. 2⃣Анализ оставшихся камней: Если количество камней n делится на 4 без остатка (n % 4 == 0), вы не можете выиграть, так как независимо от вашего хода ваш друг всегда сможет оставить вам кратное 4 количество камней. В этом случае верните false. 3⃣Выигрышная стратегия: Если количество камней n не кратно 4 (n % 4 != 0), вы можете выиграть, оставляя вашему другу кратное 4 количество камней после вашего хода. В этом случае верните true. 😎 Решение:
public class Solution {
public boolean canWinNim(int n) {
return n % 4 != 0;
}
}6 662
Задача: 81. Search in Rotated Sorted Array II
Сложность: medium
В массиве целых чисел nums, отсортированном в неубывающем порядке (не обязательно содержащем уникальные значения), произведена ротация в неизвестном индексе поворота k (0 <= k < nums.length). В результате массив принимает вид [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (нумерация с 0). Например, массив [0,1,2,4,4,4,5,6,6,7] может быть повернут в индексе 5 и превратиться в [4,5,6,6,7,0,1,2,4,4].
Для данного массива nums после ротации и целого числа target необходимо вернуть true, если target присутствует в nums, и false в противном случае.
Необходимо сократить количество операций поиска настолько, насколько это возможно.
Пример:
Input: nums = [2,5,6,0,0,1,2], target = 0 Output: true👨💻 Алгоритм: 1⃣Вспомним стандартный бинарный поиск, где мы используем два указателя (start и end), чтобы отслеживать область поиска в массиве arr. Затем мы делим пространство поиска на три части: [start, mid), [mid, mid], (mid, end]. Далее мы продолжаем искать наш целевой элемент в одной из этих зон поиска. 2⃣Определяя положение arr[mid] и target в двух частях массива F и S, мы можем сократить область поиска так же, как в стандартном бинарном поиске: Случай 1: arr[mid] находится в F, target в S: так как S начинается после окончания F, мы знаем, что элемент находится здесь: (mid, end]. Случай 2: arr[mid] находится в S, target в F: аналогично, мы знаем, что элемент находится здесь: [start, mid). Случай 3: Оба arr[mid] и target находятся в F: поскольку оба они находятся в той же отсортированной части массива, мы можем сравнить arr[mid] и target, чтобы решить, как сократить область поиска. Случай 4: Оба arr[mid] и target находятся в S: так как оба они в той же отсортированной части массива, мы также можем сравнить их для решения о сокращении области поиска. 3⃣Однако, если arr[mid] равен arr[start], то мы знаем, что arr[mid] может принадлежать и F, и S, и поэтому мы не можем определить относительное положение target относительно mid. В этом случае у нас нет другого выбора, кроме как перейти к следующей области поиска итеративно. Таким образом, существуют области поиска, которые позволяют использовать бинарный поиск, и области, где это невозможно. 😎 Решение:
class Solution {
public boolean search(int[] nums, int target) {
int n = nums.length;
if (n == 0) return false;
int end = n - 1;
int start = 0;
while (start <= end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) {
return true;
}
if (!isBinarySearchHelpful(nums, start, nums[mid])) {
start++;
continue;
}
boolean pivotArray = existsInFirst(nums, start, nums[mid]);
boolean targetArray = existsInFirst(nums, start, target);
if (pivotArray ^ targetArray) {
if (pivotArray) {
start = mid + 1;
} else {
end = mid - 1;
}
} else {
if (nums[mid] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
return false;
}
private boolean isBinarySearchHelpful(int[] arr, int start, int element) {
return arr[start] != element;
}
private boolean existsInFirst(int[] arr, int start, int element) {
return arr[start] <= element;
}
}6 662
Задача: 1669. Merge In Between Linked Lists
Сложность: medium
Вам даны два связанных списка: list1 и list2 размером n и m соответственно.
Удалите узлы list1 с ath узла по bth узел и вставьте на их место list2.
Синие ребра и узлы на рисунке в вверху поста указывают на результат:
Пример:
Input: list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
Output: [10,1,13,1000000,1000001,1000002,5]
Explanation: We remove the nodes 3 and 4 and put the entire list2 in their place. The blue edges and nodes in the above figure indicate the result.class Solution {
public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
List<Integer> mergeArray = new ArrayList<>();
int index = 0;
ListNode current1 = list1;
while (index < a) {
mergeArray.add(current1.val);
current1 = current1.next;
index++;
}
ListNode current2 = list2;
while (current2 != null) {
mergeArray.add(current2.val);
current2 = current2.next;
}
while (index < b + 1) {
current1 = current1.next;
index++;
}
while (current1 != null) {
mergeArray.add(current1.val);
current1 = current1.next;
}
ListNode resultList = null;
for (int i = mergeArray.size() - 1; i >= 0; i--) {
ListNode newNode = new ListNode(mergeArray.get(i), resultList);
resultList = newNode;
}
return resultList;
}
}6 662
Задача: 715. Range Module
Сложность: hard
Модуль Range - это модуль, который отслеживает диапазоны чисел. Создайте структуру данных для отслеживания диапазонов, представленных в виде полуоткрытых интервалов, и запросов к ним. Полуоткрытый интервал [left, right) обозначает все вещественные числа x, где left <= x < right. Реализуйте класс RangeModule: RangeModule() Инициализирует объект структуры данных. void addRange(int left, int right) Добавляет полуоткрытый интервал [left, right), отслеживая каждое вещественное число в этом интервале. Добавление интервала, который частично перекрывает отслеживаемые в данный момент числа, должно добавить все числа в интервале [left, right), которые еще не отслеживаются. boolean queryRange(int left, int right) Возвращает true, если каждое действительное число в интервале [left, right) отслеживается в данный момент, и false в противном случае. void removeRange(int left, int right) Прекращает отслеживание каждого действительного числа, отслеживаемого в данный момент в полуоткрытом интервале [left, right).
Пример:
Input
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
Output
[null, null, null, true, false, true]import java.util.ArrayList;
import java.util.List;
public class RangeModule {
private List<int[]> ranges;
public RangeModule() {
ranges = new ArrayList<>();
}
public void addRange(int left, int right) {
List<int[]> newRanges = new ArrayList<>();
int i = 0;
while (i < ranges.size() && ranges.get(i)[1] < left) {
newRanges.add(ranges.get(i));
i++;
}
while (i < ranges.size() && ranges.get(i)[0] <= right) {
left = Math.min(left, ranges.get(i)[0]);
right = Math.max(right, ranges.get(i)[1]);
i++;
}
newRanges.add(new int[] {left, right});
while (i < ranges.size()) {
newRanges.add(ranges.get(i));
i++;
}
ranges = newRanges;
}
public boolean queryRange(int left, int right) {
for (int[] range : ranges) {
if (range[0] <= left && right <= range[1]) {
return true;
}
}
return false;
}
public void removeRange(int left, int right) {
List<int[]> newRanges = new ArrayList<>();
for (int[] range : ranges) {
if (range[0] < left) {
newRanges.add(new int[] {range[0], Math.min(range[1], left)});
}
if (right < range[1]) {
newRanges.add(new int[] {Math.max(range[0], right), range[1]});
}
}
ranges = newRanges;
}
}6 662
Задача: 867. Transpose Matrix
Сложность: easy
Дан двумерный целочисленный массив matrix, верните его транспонированную матрицу.
Транспонированная матрица — это матрица, перевернутая относительно своей главной диагонали, при этом строки и столбцы меняются местами.
Пример:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[1,4,7],[2,5,8],[3,6,9]]class Solution {
public int[][] transpose(int[][] A) {
int R = A.length, C = A[0].length;
int[][] ans = new int[C][R];
for (int r = 0; r < R; ++r)
for (int c = 0; c < C; ++c)
ans[c][r] = A[r][c];
return ans;
}
}6 662
Задача: 145. Binary Tree Postorder Traversal
Сложность: easy
Дан корень бинарного дерева, верните обход значений узлов в постпорядке.
Пример:
Input: root = [1,null,2,3] Output: [3,2,1]👨💻 Алгоритм: 1⃣Заполнение стека по стратегии право->узел->лево: Инициируйте стек и добавьте в него корень дерева. Перед тем как положить узел в стек, сначала добавьте его правого потомка, затем сам узел, а после — левого потомка. Это обеспечит последовательное извлечение узлов из стека в нужном порядке для постпорядкового обхода. 2⃣Извлечение узла из стека и проверка: Извлекайте последний узел из стека, проверяя, является ли он левым листом (узел без потомков). Если это так, добавьте значение узла в выходной список (массив значений). Если узел имеет потомков, продолжайте выполнение стека с добавлением дочерних узлов по той же стратегии. 3⃣Повторение процесса до опустошения стека: Если извлеченный узел не является левым листом, необходимо обработать его потомков. Для этого, верните узел и его потомков в стек в правильном порядке, чтобы следующие итерации могли корректно обработать все узлы. Повторяйте процесс до тех пор, пока стек не опустеет, что означает завершение обхода всех узлов. 😎 Решение:
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> output = new LinkedList();
Deque<TreeNode> stack = new ArrayDeque();
if (root == null) return output;
stack.push(root);
while (!stack.isEmpty()) {
root = stack.pop();
output.addFirst(root.val);
if (root.left != null) stack.push(root.left);
if (root.right != null) stack.push(root.right);
}
return output;
}
}6 662
Задача: 663. Equal Tree Partition
Сложность: medium
Дан корень бинарного дерева. Верните true, если можно разделить дерево на два дерева с равными суммами значений после удаления ровно одного ребра из исходного дерева.
Пример:
Input: root = [5,10,10,null,null,2,3] Output: true👨💻 Алгоритм: 1⃣Вычисление общей суммы: Напишите функцию для вычисления общей суммы всех узлов дерева. 2⃣Проверка возможности разделения: Напишите функцию, чтобы рекурсивно проверить, может ли поддерево быть равно половине общей суммы. Если такое поддерево найдено, значит дерево можно разделить на две части с равными суммами. 3⃣Валидация и возврат результата: Проверьте, что общая сумма четная (так как только в этом случае возможно её разделение на две равные части), и используйте функцию проверки поддерева, чтобы определить, можно ли разделить дерево на две части с равными суммами. 😎 Решение:
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public boolean checkEqualTree(TreeNode root) {
int totalSum = sumTree(root);
if (totalSum % 2 != 0) return false;
int target = totalSum / 2;
return checkSubtreeSum(root, target, root);
}
private int sumTree(TreeNode node) {
if (node == null) return 0;
return node.val + sumTree(node.left) + sumTree(node.right);
}
private boolean checkSubtreeSum(TreeNode node, int target, TreeNode root) {
if (node == null) return false;
if (node != root && sumTree(node) == target) {
return true;
}
return checkSubtreeSum(node.left, target, root) || checkSubtreeSum(node.right, target, root);
}
}6 662
Задача: 1675. Minimize Deviation in Array
Сложность: hard
Вам дан массив nums из n положительных целых чисел.
Вы можете выполнять два типа операций над любым элементом массива любое количество раз:
Если элемент четный, разделите его на 2.
Например, если массив [1,2,3,4], то вы можете выполнить эту операцию на последнем элементе, и массив станет [1,2,3,2].
Если элемент нечетный, умножьте его на 2.
Например, если массив [1,2,3,4], то вы можете выполнить эту операцию на первом элементе, и массив станет [2,2,3,4].
Отклонение массива — это максимальная разница между любыми двумя элементами в массиве.
Верните минимальное отклонение, которое может иметь массив после выполнения некоторого числа операций.
Пример:
Input: nums = [1,2,3,4]
Output: 1
Explanation: You can transform the array to [1,2,3,2], then to [2,2,3,2], then the deviation will be 3 - 2 = 1.class Solution {
public int minimumDeviation(int[] nums) {
PriorityQueue<Integer> evens = new PriorityQueue<>(Collections.reverseOrder());
int minimum = Integer.MAX_VALUE;
for (int num : nums) {
if (num % 2 == 0) {
evens.offer(num);
minimum = Math.min(minimum, num);
} else {
evens.offer(num * 2);
minimum = Math.min(minimum, num * 2);
}
}
int minDeviation = Integer.MAX_VALUE;
while (!evens.isEmpty()) {
int currentValue = evens.poll();
minDeviation = Math.min(minDeviation, currentValue - minimum);
if (currentValue % 2 == 0) {
evens.offer(currentValue / 2);
minimum = Math.min(minimum, currentValue / 2);
} else {
break;
}
}
return minDeviation;
}
}6 662
Законный способ списать долги по кредитам и займам
⚡✅ Да, это легально. Государство разрешило списывать долги по 127-ФЗ.
Бесплатно расскажем, как это сделали уже тысячи. Хватит быть должным! Узнайте за 60 секунд. ⚡
Проверьте 📊, сможете ли вы пройти процедуру и начать всё с чистого листа.
Жмите «Подробнее» 👍
Узнать больше
Банкротство влечет негативные последствия, в том числе ограничения на получение кредита и повторное банкротство в течение пяти лет. Предварительно обратитесь к своему кредитору и в МФЦ.
#реклама
sfera.help
О рекламодателе
6 662
Задача: 383. Ransom Note
Сложность: easy
Даны две строки ransomNote и magazine, верните true, если ransomNote можно составить, используя буквы из magazine, и false в противном случае.
Каждая буква из magazine может быть использована в ransomNote только один раз.
Пример:
Input: ransomNote = "a", magazine = "b" Output: false👨💻 Алгоритм: 1⃣Поскольку строки являются неизменяемым типом, их нельзя изменять, поэтому у них нет операций "вставки" и "удаления". 2⃣По этой причине необходимо заменять строку magazine новой строкой, в которой отсутствует символ, который мы хотели удалить. 3⃣Повторяйте этот процесс, пока не будут удалены все необходимые символы. 😎 Решение:
public boolean canConstruct(String ransomNote, String magazine) {
for (char c : ransomNote.toCharArray()) {
int index = magazine.indexOf(c);
if (index == -1) {
return false;
}
magazine = magazine.substring(0, index) + magazine.substring(index + 1);
}
return true;
}6 662
Задача: 323. Number of Connected Components in an Undirected Graph
Сложность: medium
У вас есть граф из n узлов. Вам дано целое число n и массив edges, где edges[i] = [ai, bi] указывает на наличие ребра между ai и bi в графе.
Верните количество связных компонентов в графе.
Пример:
Input: n = 5, edges = [[0,1],[1,2],[3,4]] Output: 2👨💻 Алгоритм: 1⃣Создание списка смежности Создайте список смежности, такой что adj[v] содержит все смежные вершины вершины v. 2⃣Инициализация посещенных узлов Инициализируйте хэш-карту или массив visited для отслеживания посещенных вершин. 3⃣Подсчет компонентов Определите счетчик и инициализируйте его нулем. Итерируйте по каждой вершине в edges, и если вершина еще не была посещена, начните DFS с этой вершины. Добавляйте каждую вершину, посещенную во время DFS, в visited. Каждый раз, когда начинается новый DFS, увеличивайте счетчик на один. В конце, счетчик будет содержать количество связных компонентов в неориентированном графе. 😎 Решение:
public class Solution {
public int countComponents(int n, int[][] edges) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]);
adj.get(edge[1]).add(edge[0]);
}
boolean[] visited = new boolean[n];
int count = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i, adj, visited);
count++;
}
}
return count;
}
private void dfs(int node, List<List<Integer>> adj, boolean[] visited) {
Stack<Integer> stack = new Stack<>();
stack.push(node);
while (!stack.isEmpty()) {
int current = stack.pop();
if (!visited[current]) {
visited[current] = true;
for (int neighbor : adj.get(current)) {
if (!visited[neighbor]) stack.push(neighbor);
}
}
}
}
}6 662
Задача: 1242. Web Crawler Multithreaded
Сложность: medium
Учитывая URL startUrl и интерфейс HtmlParser, реализуйте многопоточный веб-краулер, который будет просматривать все ссылки, находящиеся под тем же именем хоста, что и startUrl. Верните все URL, полученные вашим веб-краулером, в любом порядке.
Ваш краулер должен: Начинать со страницы: startUrl Вызывать HtmlParser.getUrls(url), чтобы получить все URL с веб-страницы данного URL. Не просматривать одну и ту же ссылку дважды. Исследовать только те ссылки, которые находятся под тем же именем хоста, что и startUrl.
Пример:
Input: urls = [ "http://news.yahoo.com", "http://news.yahoo.com/news", "http://news.yahoo.com/news/topics/", "http://news.google.com", "http://news.yahoo.com/us" ] edges = [[2,0],[2,1],[3,2],[3,1],[0,4]] startUrl = "http://news.yahoo.com/news/topics/" Output: [ "http://news.yahoo.com", "http://news.yahoo.com/news", "http://news.yahoo.com/news/topics/", "http://news.yahoo.com/us" ]👨💻 Алгоритм: 1⃣Извлечь имя хоста из startUrl. Использовать многопоточность для обработки URL-адресов. 2⃣Хранить посещенные URL-адреса, чтобы избежать повторного посещения. 3⃣Использовать HtmlParser для получения URL-адресов с веб-страниц. 😎 Решение:
import java.net.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicBoolean;
class HtmlParser {
public List<String> getUrls(String url) {
return new ArrayList<>();
}
}
public class Solution {
public List<String> crawl(String startUrl, HtmlParser htmlParser) {
String hostname = extractHostname(startUrl);
Set<String> visited = ConcurrentHashMap.newKeySet();
ExecutorService executor = Executors.newFixedThreadPool(10);
Queue<Future<?>> futures = new ConcurrentLinkedQueue<>();
visited.add(startUrl);
futures.add(executor.submit(() -> visit(startUrl, htmlParser, hostname, visited, futures, executor)));
while (!futures.isEmpty()) {
try {
futures.poll().get();
} catch (InterruptedException | ExecutionException e) {
e.printStackTrace();
}
}
executor.shutdown();
return new ArrayList<>(visited);
}
private void visit(String url, HtmlParser htmlParser, String hostname, Set<String> visited, Queue<Future<?>> futures, ExecutorService executor) {
for (String nextUrl : htmlParser.getUrls(url)) {
if (extractHostname(nextUrl).equals(hostname) && visited.add(nextUrl)) {
futures.add(executor.submit(() -> visit(nextUrl, htmlParser, hostname, visited, futures, executor)));
}
}
}
private String extractHostname(String url) {
try {
URL u = new URL(url);
return u.getHost();
} catch (MalformedURLException e) {
e.printStackTrace();
return "";
}
}
}6 662
Задача: 1359. Count All Valid Pickup and Delivery Options
Сложность: hard
Дано n заказов, каждый из которых состоит из услуги забора и доставки.
Посчитайте все возможные допустимые последовательности забора/доставки, такие что доставка(i) всегда идет после забора(i).
Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.
Пример:
Input: n = 1 Output: 1 Explanation: Unique order (P1, D1), Delivery 1 always is after of Pickup 1.👨💻 Алгоритм: 1⃣Инициализация: Используйте динамическое программирование для хранения количества допустимых последовательностей для каждого количества заказов от 1 до n. 2⃣Рекурсивное вычисление: Для каждого количества заказов k используйте рекурсивную формулу для вычисления количества допустимых последовательностей, учитывая, что каждая новая пара (забор и доставка) может быть вставлена в любую из существующих позиций. 3⃣Возвращение результата: Верните результат для n заказов, применяя модуль 10^9 + 7 для предотвращения переполнения. 😎 Решение:
public class Solution {
public int countOrders(int n) {
int MOD = 1_000_000_007;
long[] dp = new long[n + 1];
dp[0] = 1;
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1] * (2 * i - 1) * i % MOD;
}
return (int) dp[n];
}
}