Java | LeetCode
Open in Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Show more6 515
Subscribers
-424 hours
-207 days
-5330 days
Posts Archive
6 514
Задача: 225. Implement Stack using Queues
Сложность: easy
Реализуйте стек (последним пришел - первым вышел, LIFO) с использованием только двух очередей. Реализованный стек должен поддерживать все функции обычного стека (push, top, pop и empty).
Реализуйте класс MyStack:
void push(int x): Добавляет элемент x на вершину стека.
int pop(): Удаляет элемент с вершины стека и возвращает его.
int top(): Возвращает элемент на вершине стека.
boolean empty(): Возвращает true, если стек пуст, иначе false.
Примечания:
Вы должны использовать только стандартные операции очереди, что означает, что допустимы только операции добавления в конец, просмотр/удаление из начала, определение размера и проверка на пустоту.
Пример:
Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]
Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False
👨💻 Алгоритм:
1⃣Реализация методов push и pop:
Метод push добавляет элемент x в очередь q2, затем перемещает все элементы из q1 в q2 и меняет местами q1 и q2.
Метод pop удаляет элемент из q1 и обновляет значение top.
2⃣Реализация методов top и empty:
Метод top возвращает верхний элемент стека.
Метод empty проверяет, пуста ли очередь q1, и возвращает соответствующее значение.
3⃣Поддержка стандартных операций очереди:
Используйте только стандартные операции очереди: добавление в конец, удаление из начала, определение размера и проверка на пустоту.
😎 Решение:
import java.util.LinkedList;
import java.util.Queue;
class MyStack {
private Queue<Integer> q1 = new LinkedList<>();
private Queue<Integer> q2 = new LinkedList<>();
private int top;
public void push(int x) {
q2.add(x);
top = x;
while (!q1.isEmpty()) {
q2.add(q1.remove());
}
Queue<Integer> temp = q1;
q1 = q2;
q2 = temp;
}
public void pop() {
q1.remove();
if (!q1.isEmpty()) {
top = q1.peek();
}
}
public boolean empty() {
return q1.isEmpty();
}
public int top() {
return top;
}
}
Ставь 👍 и забирай 📚 Базу знаний6 514
Бесплатный курс по 3D-моделированию с нуля
Начни карьеру в дизайне и получи первую зарплату!
Вас ждет реальный рабочий процесс:
✅ разные задачи по 3D Blander
✅ опыт общения с клиентами
✅ оплата за проект
Освойте Blender и создайте работу для портфолио
Обучение полностью бесплатное для первых 70 участников.
Осталось 28 мест.
В конце курса мы откроем для вас доступ к звездной распродаже
Там вы сможете обменять звездочки на ценные бонусы:
1. Гайд по выходу на биржу UpWork
2. Курс «Заработок на дизайне»
3. Анимированный концепт Samsung True для портфолио
4. Бессрочный грант на обучение: 15 000 ₽
5. Гайд «Горячие клавиши в Blender»
Записывайтесь сейчас!
Узнать больше
#реклама 16+
yudaevschool24.online
О рекламодателе
6 514
Задача: 200. Number of Islands
Сложность: medium
Дана двумерная бинарная сетка размером m x n, представляющая карту из '1' (земля) и '0' (вода). Верните количество островов.
Остров окружён водой и образуется путём соединения соседних земель горизонтально или вертикально. Можно предположить, что все четыре края сетки окружены водой.
Пример:
Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1👨💻 Алгоритм: 1⃣Линейно просканируйте двумерную карту, если узел содержит '1', то это корневой узел, который запускает поиск в глубину (DFS). 2⃣Во время выполнения DFS каждый посещённый узел следует установить в '0', чтобы пометить его как посещённый. 3⃣Подсчитайте количество корневых узлов, запускающих DFS. Это количество будет равно количеству островов, так как каждый DFS, начинающийся с какого-либо корня, идентифицирует остров. 😎 Решение:
class Solution {
void dfs(char[][] grid, int r, int c) {
int nr = grid.length;
int nc = grid[0].length;
if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
return;
}
grid[r][c] = '0';
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
dfs(grid, r, c);
}
}
}
return num_islands;
}
}
Ставь 👍 и забирай 📚 Базу знаний6 514
Запусти IT-бизнес с доходом от 500 000 ₽/мес за 7 дней!
Что вы получаете:
✅ IT-продукт с рынком 416+ млрд ₽
💰 Доход от 500 000 ₽ в первый месяц
💻 Полностью онлайн — работайте из любой точки мира
Стартовый бюджет: от 200 000 ₽
Окупаемость: 14 дней ⚡
Узнать больше
#реклама
edler.pro
О рекламодателе
6 514
Задача: 1461. Check If a String Contains All Binary Codes of Size K
Сложность: medium
Дана бинарная строка s и целое число k, верните true, если каждый бинарный код длины k является подстрокой s. В противном случае верните false.
Пример:
Input: s = "00110110", k = 2 Output: true Explanation: The binary codes of length 2 are "00", "01", "10" and "11". They can be all found as substrings at indices 0, 1, 3 and 2 respectively.👨💻 Алгоритм: 1⃣Определите количество возможных двоичных кодов длины k. 2⃣Создайте массив для отслеживания, какие коды были найдены. Итерируйте по строке s, вычисляя хэш для текущего окна длины k и обновляя массив отслеживания. 3⃣Возвращайте true, если все возможные коды найдены, иначе false. 😎 Решение:
class Solution {
public static boolean hasAllCodes(String s, int k) {
int need = 1 << k;
boolean[] got = new boolean[need];
int allOne = need - 1;
int hashVal = 0;
for (int i = 0; i < s.length(); i++) {
hashVal = ((hashVal << 1) & allOne) | (s.charAt(i) - '0');
if (i >= k - 1 && !got[hashVal]) {
got[hashVal] = true;
need--;
if (need == 0) {
return true;
}
}
}
return false;
}
}
Ставь 👍 и забирай 📚 Базу знаний6 514
Вакансия удалённый 1C-программист. З/П до 250 000 ₽
Ищем 1С-программиста с опытом от 3-х лет на full-time. Аккредитованная IT-компания. Удалённая работа из любой точки мира. ДМО. Оформление в штат по ТК РФ. Зарплата до 250000 ₽. Помощь в развитии.
Стань частью профессиональной команды Programming Store. Переходи по ссылке и откликайся!
Подать заявку
#реклама
mrqz.me
О рекламодателе
6 514
Задача: 914. X of a Kind in a Deck of Cards
Сложность: easy
Вам дан целочисленный массив deck, где deck[i] - число, написанное на i-й карте. Разделите карты на одну или несколько групп так, чтобы: в каждой группе было ровно x карт, где x > 1, и на всех картах в одной группе было написано одно и то же целое число. Верните true, если такое разделение возможно, или false в противном случае.
Пример:
Input: deck = [1,2,3,4,4,3,2,1] Output: true👨💻 Алгоритм: 1⃣Создать словарь для подсчета частоты каждого числа в массиве deck. 2⃣Найти наибольший общий делитель (НОД) всех частот. 3⃣Проверить, больше ли НОД 1, чтобы определить, можно ли разделить карты на группы. 😎 Решение:
import java.util.*;
import java.util.stream.Collectors;
class Solution {
public boolean hasGroupsSizeX(int[] deck) {
Map<Integer, Integer> count = new HashMap<>();
for (int num : deck) {
count.put(num, count.getOrDefault(num, 0) + 1);
}
int g = count.values().stream().reduce(this::gcd).orElse(0);
return g > 1;
}
private int gcd(int a, int b) {
while (b != 0) {
int temp = a % b;
a = b;
b = temp;
}
return a;
}
}
Ставь 👍 и забирай 📚 Базу знаний6 514
Задача: 1037. Valid Boomerang
Сложность: easy
Если задан массив points, где points[i] = [xi, yi] представляет точку на плоскости X-Y, верните true, если эти точки являются бумерангом. Бумеранг - это набор из трех точек, которые отличаются друг от друга и не являются прямой линией.
Пример:
Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2] Output: false👨💻 Алгоритм: 1⃣Проверка уникальности точек: Убедитесь, что все три точки уникальны. Если любые две точки совпадают, то это не бумеранг. 2⃣Проверка на коллинеарность: Используйте определитель (или площадь параллелограмма) для проверки, находятся ли три точки на одной прямой. Если площадь параллелограмма, образованного тремя точками, равна нулю, то точки коллинеарны. 3⃣Результат: Если точки уникальны и не коллинеарны, верните true. В противном случае, верните false. 😎 Решение:
var isBoomerang = function(points) {
let [x1, y1] = points[0];
let [x2, y2] = points[1];
let [x3, y3] = points[2];
return (x1 !== x2 || y1 !== y2) &&
(x1 !== x3 || y1 !== y3) &&
(x2 !== x3 || y2 !== y3) &&
(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) !== 0;
};
Ставь 👍 и забирай 📚 Базу знаний6 514
Дарим подписку на Яндекс Музыку
Ответьте на 1 вопрос и Яндекс Музыка ваша для вас и 3-х ваших близких.
Кинопоиск и Яндекс Книги тоже в подписке.
Попробуйте бесплатно❤️
Попробовать
#реклама 18+
music.yandex.ru
О рекламодателе
Реклама на Яндексе
6 514
Задача: 685. Redundant Connection II
Сложность: hard
В этой задаче корневое дерево — это направленный граф, в котором существует ровно один узел (корень), для которого все остальные узлы являются потомками этого узла, плюс каждый узел имеет ровно одного родителя, за исключением корневого узла, у которого нет родителей.
Данный ввод представляет собой направленный граф, который изначально был корневым деревом с n узлами (со значениями от 1 до n), и к которому добавлено одно дополнительное направленное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее.
Результирующий граф представлен в виде двумерного массива ребер. Каждый элемент массива edges — это пара [ui, vi], представляющая направленное ребро, соединяющее узлы ui и vi, где ui является родителем ребенка vi.
Верните ребро, которое можно удалить, чтобы результирующий граф стал корневым деревом с n узлами. Если существует несколько ответов, верните ответ, который встречается последним в данном двумерном массиве.
Пример:
Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]
👨💻 Алгоритм:
1⃣Сначала создаем базовый граф, отслеживая ребра, идущие от узлов с несколькими родителями. В итоге у нас будет либо 2, либо 0 кандидатов на удаление ребра.
2⃣Если кандидатов нет, то каждый узел имеет одного родителя, как в случае 1->2->3->4->1->5. От любого узла идем к его родителю, пока не посетим узел повторно — тогда мы окажемся внутри цикла, и любые последующие посещенные узлы будут частью этого цикла. В этом случае удаляем последнее ребро, входящее в цикл.
3⃣Если есть кандидаты, проверяем, является ли граф, созданный из родителей, корневым деревом. Идем от любого узла к его родителю, пока это возможно, затем выполняем обход в глубину (DFS) от этого корня. Если посещаем каждый узел, удаление последнего из двух кандидатов приемлемо. В противном случае удаляем первое из двух ребер-кандидатов.
😎 Решение:
class Solution {
public int[] findRedundantDirectedConnection(int[][] edges) {
int N = edges.length;
Map<Integer, Integer> parent = new HashMap<>();
List<int[]> candidates = new ArrayList<>();
for (int[] edge : edges) {
if (parent.containsKey(edge[1])) {
candidates.add(new int[]{parent.get(edge[1]), edge[1]});
candidates.add(edge);
} else {
parent.put(edge[1], edge[0]);
}
}
int root = orbit(1, parent).node;
if (candidates.isEmpty()) {
Set<Integer> cycle = orbit(root, parent).seen;
for (int[] edge : edges) {
if (cycle.contains(edge[0]) && cycle.contains(edge[1])) {
return edge;
}
}
}
Map<Integer, List<Integer>> children = new HashMap<>();
for (int v : parent.keySet()) {
int pv = parent.get(v);
children.computeIfAbsent(pv, k -> new ArrayList<>()).add(v);
}
boolean[] seen = new boolean[N + 1];
Stack<Integer> stack = new Stack<>();
stack.add(root);
while (!stack.isEmpty()) {
int node = stack.pop();
if (!seen[node]) {
seen[node] = true;
if (children.containsKey(node)) {
stack.addAll(children.get(node));
}
}
}
for (boolean b : seen) {
if (!b) {
return candidates.get(0);
}
}
return candidates.get(1);
}
public OrbitResult orbit(int node, Map<Integer, Integer> parent) {
Set<Integer> seen = new HashSet<>();
while (parent.containsKey(node) && !seen.contains(node)) {
seen.add(node);
node = parent.get(node);
}
return new OrbitResult(node, seen);
}
}
class OrbitResult {
int node;
Set<Integer> seen;
OrbitResult(int n, Set<Integer> s) {
node = n;
seen = s;
}
}
Ставь 👍 и забирай 📚 Базу знаний6 514
📺 Уникальная база IT собеседований
456+ реальных собеседований на программиста, тестировщика, аналитика и прочие IT профы.
Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д.
🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!
6 514
Задача: 338. Counting Bits
Сложность: easy
Дано целое число n, верните массив ans длиной n + 1, такой что для каждого i (0 <= i <= n), ans[i] будет равняться количеству единиц в двоичном представлении числа i.
Пример:
Input: n = 5 Output: [0,1,1,2,1,2] Explanation: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101👨💻 Алгоритм: 1⃣ Инициализация массива: Создайте массив ans длиной n + 1, заполненный нулями. Этот массив будет содержать количество единиц в двоичном представлении каждого числа от 0 до n. 2⃣ Итерация и вычисление: Пройдите в цикле по всем числам от 1 до n. Для каждого числа x используйте битовую операцию x & (x - 1), чтобы убрать последнюю установленную биту, и добавьте 1 к значению ans для этого результата. Это количество единиц в двоичном представлении числа x. 3⃣ Возврат результата: Верните заполненный массив ans, который содержит количество единиц для каждого числа от 0 до n. 😎 Решение:
public class Solution {
public int[] countBits(int num) {
int[] ans = new int[num + 1];
for (int x = 1; x <= num; ++x) {
ans[x] = ans[x & (x - 1)] + 1;
}
return ans;
}
}
Ставь 👍 и забирай 📚 Базу знаний6 514
Задача: 1061. Lexicographically Smallest Equivalent String
Сложность: medium
Даны две строки одинаковой длины s1 и s2, а также строка baseStr.
Мы говорим, что символы s1[i] и s2[i] эквивалентны.
Например, если s1 = "abc" и s2 = "cde", то 'a' == 'c', 'b' == 'd' и 'c' == 'e'. Эквивалентные символы следуют правилам рефлексивности, симметрии и транзитивности.
Верните лексикографически наименьшую эквивалентную строку baseStr, используя информацию об эквивалентности из s1 и s2.
Пример:
Input: s1 = "parker", s2 = "morris", baseStr = "parser"
Output: "makkek"
Explanation: Based on the equivalency information in s1 and s2, we can group their characters as [m,p], [a,o], [k,r,s], [e,i].
The characters in each group are equivalent and sorted in lexicographical order.
So the answer is "makkek".
👨💻 Алгоритм:
1⃣Создайте матрицу смежности adjMatrix размером 26x26 для хранения рёбер и массив visited для отслеживания посещённых символов.
2⃣Итеративно обрабатывайте каждый символ от 0 до 25:
Если символ ещё не посещён, выполните DFS, начиная с этого символа, и сохраните все пройденные символы в векторе component, а минимальный из этих символов в переменной minChar.
Обновите все символы из component до minChar в векторе mappingChar, который хранит окончательное сопоставление символов baseStr.
3⃣Пройдите по baseStr и создайте итоговую строку ans, используя символы из mappingChar.
😎 Решение:
class Solution {
int minChar;
void DFS(int src, Integer[][] adjMatrix, Integer visited[], List<Integer> component) {
// Mark the character as visited.
visited[src] = 1;
// Add it to the list.
component.add(src);
// Update the minimum character in the component.
minChar = Math.min(minChar, src);
for (int i = 0; i < 26; i++) {
// Perform DFS if the edge exists and the node isn't visited yet.
if (adjMatrix[src][i] != null && visited[i] == null) {
DFS(i, adjMatrix, visited, component);
}
}
}
public String smallestEquivalentString(String s1, String s2, String baseStr) {
// Adjacency matrix to store edges.
Integer adjMatrix[][] = new Integer[26][26];
for (int i = 0; i < s1.length(); i++) {
adjMatrix[s1.charAt(i) - 'a'][s2.charAt(i) - 'a'] = 1;
adjMatrix[s2.charAt(i) - 'a'][s1.charAt(i) - 'a'] = 1;
}
// Array to store the final character mappings.
int mappingChar[] = new int[26];
for (int i = 0; i < 26; i++) {
mappingChar[i] = i;
}
// Array to keep visited nodes during DFS.
Integer visited[] = new Integer[26];
for (int c = 0; c < 26; c++) {
if (visited[c] == null) {
// Store the characters in the current component.
List<Integer> component = new ArrayList<>();
// Variable to store the minimum character in the component.
minChar = 27;
DFS(c, adjMatrix, visited, component);
// Map the characters in the component to the minimum character.
for (int vertex : component) {
mappingChar[vertex] = minChar;
}
}
}
String ans = "";
// Create the answer string.
for (char c : baseStr.toCharArray()) {
ans += (char)(mappingChar[c - 'a'] + 'a');
}
return ans;
}
}
Ставь 👍 и забирай 📚 Базу знаний6 514
Задача: 293. Flip Game
Сложность: easy
Вы играете в игру Flip со своим другом.
Вам дана строка currentState, которая содержит только символы '+' и '-'. Вы и ваш друг по очереди переворачиваете две последовательные "++" в "--". Игра заканчивается, когда один из игроков больше не может сделать ход, и, следовательно, другой игрок становится победителем.
Верните все возможные состояния строки currentState после одного допустимого хода. Вы можете вернуть ответы в любом порядке. Если допустимых ходов нет, верните пустой список [].
Пример:
Input: currentState = "++++" Output: ["--++","+--+","++--"]👨💻 Алгоритм: 1⃣Создайте пустой массив nextPossibleStates для хранения всех возможных следующих состояний после одного хода. 2⃣Запустите цикл от index = 0 до currentState.size() - 1. Для каждого индекса: Если символы на позициях index и index + 1 равны '+': Создайте новую строку nextState, заменив две последовательные '+' на '--'. Используйте конкатенацию строк для создания nextState из подстроки до первого '+', "--" и подстроки после второго '+' до конца. Сохраните созданное nextState в массив nextPossibleStates. 3⃣После цикла верните массив nextPossibleStates, содержащий все возможные следующие состояния. 😎 Решение:
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<String> generatePossibleNextMoves(String currentState) {
List<String> nextPossibleStates = new ArrayList<>();
for (int index = 0; index < currentState.length() - 1; index++) {
if (currentState.charAt(index) == '+' && currentState.charAt(index + 1) == '+') {
String nextState = currentState.substring(0, index) + "--" + currentState.substring(index + 2);
nextPossibleStates.add(nextState);
}
}
return nextPossibleStates;
}
}
Ставь 👍 и забирай 📚 Базу знаний6 514
Крупнейший университет искусственного интеллекта
Приглашаем на бесплатный курс по искусственному интеллекту!
Мы подготовили для тебя 5 занятий по теме «Разработка нейро-сотрудников на GPT». Пройди регистрацию для получения полного бесплатного доступа к курсу.
✨ 8 000+ студентов со всего мира
✨ 600+ AI-проектов, созданных студентами
✨ Сборная Университета — победители крупнейших AI-хакатонов России
✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие)
✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие)
Будем рады видеть тебя в наших рядах!
Узнать больше
#реклама 16+
neural-university.ru
О рекламодателе
6 514
Задача: 1087. Brace Expansion
Сложность: medium
Дан список оценок различных студентов, items, где items[i] = [IDi, scorei] представляет собой одну оценку студента с идентификатором IDi. Вычислите среднее значение пяти лучших оценок каждого студента.
Верните ответ в виде массива пар result, где result[j] = [IDj, topFiveAveragej] представляет студента с идентификатором IDj и его среднее значение пяти лучших оценок. Отсортируйте result по IDj в порядке возрастания.
Среднее значение пяти лучших оценок студента вычисляется путем сложения его пяти лучших оценок и деления на 5 с использованием целочисленного деления.
Пример:
Input: s = "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]
👨💻 Алгоритм:
1⃣Вызовите функцию findAllWords(String, Integer) с данной строкой s и значением startPos равным 0. startPos представляет текущую позицию в строке s. Если строка, которую нужно рассмотреть, пуста (startPos == s.length()), верните список, содержащий пустую строку.
2⃣Вызовите функцию storeFirstOptions с строкой s, целым числом startPos и пустым списком firstOptions. Найдите набор символов, начиная с позиции startPos, и сохраните их в списке firstOptions. Это может быть один символ или все символы между скобками. Отсортируйте список firstOptions. Верните обновленное значение startPos, которое теперь указывает на первый индекс следующей группы символов в строке s, которую мы будем рассматривать. Сохраните это значение в переменной remStringStartPos. Сделайте рекурсивный вызов функции findAllWords(String, Integer) с строкой s и remStringStartPos. Сохраните возвращенный список слов в переменной wordsWithRemString.
3⃣Переберите слова в wordsWithRemString и добавьте вышеуказанный символ в начало каждого слова, сохраняя новую строку в списке expandedWords. Верните список expandedWords.
😎 Решение:
class Solution {
private int storeFirstOptions(String s, int startPos, List<Character> firstOptions) {
if (s.charAt(startPos) != '{') {
firstOptions.add(s.charAt(startPos));
} else {
startPos++;
while (s.charAt(startPos) != '}') {
if (Character.isLowerCase(s.charAt(startPos))) {
firstOptions.add(s.charAt(startPos));
}
startPos++;
}
Collections.sort(firstOptions);
}
return startPos + 1;
}
private List<String> findAllWords(String s, int startPos) {
if (startPos == s.length()) {
return Arrays.asList("");
}
List<Character> firstOptions = new ArrayList<>();
int remStringStartPos = storeFirstOptions(s, startPos, firstOptions);
List<String> wordsWithRemString = findAllWords(s, remStringStartPos);
List<String> expandedWords = new ArrayList<>();
for (char c : firstOptions) {
for (String word : wordsWithRemString) {
expandedWords.add(c + word);
}
}
return expandedWords;
}
public List<String> expand(String s) {
return findAllWords(s, 0);
}
}
Ставь 👍 и забирай 📚 Базу знаний6 514
Задача: 661. Image Smoother
Сложность: easy
Дан целочисленный матрица img размером m x n, представляющая градации серого изображения. Верните изображение после применения сглаживания к каждой его ячейке.
Пример:
Input: img = [[1,1,1],[1,0,1],[1,1,1]] Output: [[0,0,0],[0,0,0],[0,0,0]] Explanation: For the points (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0 For the points (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0 For the point (1,1): floor(8/9) = floor(0.88888889) = 0👨💻 Алгоритм: 1⃣Инициализация: Создайте новую матрицу такого же размера, чтобы сохранить результат сглаживания. 2⃣Обработка каждой ячейки: Для каждой ячейки исходной матрицы найдите всех её соседей (включая саму ячейку). Вычислите среднее значение этих ячеек и сохраните его в соответствующей ячейке результирующей матрицы. 3⃣Возврат результата: Верните результирующую матрицу после применения сглаживания ко всем ячейкам. 😎 Решение:
public class Solution {
public int[][] imageSmoother(int[][] img) {
int m = img.length, n = img[0].length;
int[][] result = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int count = 0, total = 0;
for (int ni = Math.max(0, i - 1); ni <= Math.min(m - 1, i + 1); ni++) {
for (int nj = Math.max(0, j - 1); nj <= Math.min(n - 1, j + 1); nj++) {
total += img[ni][nj];
count++;
}
}
result[i][j] = total / count;
}
}
return result;
}
}
Ставь 👍 и забирай 📚 Базу знаний6 514
Дарим подписку на Яндекс Музыку
Ответьте на 1 вопрос и Яндекс Музыка ваша для вас и 3-х ваших близких.
Кинопоиск и Яндекс Книги тоже в подписке.
Попробуйте бесплатно❤️
Попробовать
#реклама 18+
music.yandex.ru
О рекламодателе
Реклама на Яндексе
6 514
Задача: 1245. Tree Diameter
Сложность: medium
Диаметр дерева - это количество ребер в самом длинном пути в этом дереве. Имеется неориентированное дерево из n узлов, помеченных от 0 до n - 1. Вам дан двумерный массив edges, где edges.length == n - 1 и edges[i] = [ai, bi] означает, что между узлами ai и bi в дереве есть неориентированное ребро. Верните диаметр дерева.
Пример:
Input: edges = [[0,1],[0,2]] Output: 2👨💻 Алгоритм: 1⃣Построение графа: Используем представление графа в виде списка смежности. 2⃣Поиск самой удаленной вершины (DFS1): Запускаем DFS от произвольной вершины (например, 0) для нахождения самой удаленной вершины от нее. 3⃣Поиск диаметра (DFS2): Запускаем DFS от найденной на предыдущем шаге самой удаленной вершины и находим самую удаленную вершину от нее. Это расстояние и будет диаметром дерева.reset(playerId): Устанавливаем счет игрока в 0. 😎 Решение:
import java.util.*;
public class Solution {
public int treeDiameter(int[][] edges) {
if (edges.length == 0) return 0;
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int[] edge : edges) {
graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
graph.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(edge[0]);
}
int[] farthestNode = new int[1];
int dfs(int node, int parent) {
int maxDepth = 0;
for (int neighbor : graph.get(node)) {
if (neighbor != parent) {
int depth = dfs(neighbor, node);
if (depth + 1 > maxDepth) {
maxDepth = depth + 1;
farthestNode[0] = neighbor;
}
}
}
return maxDepth;
}
dfs(0, -1);
int startNode = farthestNode[0];
dfs(startNode, -1);
return dfs(farthestNode[0], -1);
}
}
Ставь 👍 и забирай 📚 Базу знаний6 514
Высшее образование дистанционно в Московском ВУЗе
Вы мечтаете получить высшее образование, но не сдали ЕГЭ или получили низкие баллы? У нас есть решение для вас!
Институт Международных Экономических Связей предлагает дистанционное обучение , которое позволяет получать качественные знания из любой точки мира по 10+ направлениям обучения.
✅ Государственный диплом без отметки о дистанте
✅ Удобный личный кабинет студента
✅ Поддержка кураторов на каждом этапе обучения
✅ Можно поступить без ЕГЭ
Узнать больше
#реклама 16+
imes.su
О рекламодателе
