C# | LeetCode

#medium Задача: 318. Maximum Product of Word Lengths Дан массив строк words, верните максимальное значение произведения длины word[i] на длину word[j], где два слова не имеют общих букв. Если таких двух слов не существует, верните 0. Пример:

Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".

👨‍💻 Алгоритм: 1⃣Предварительная обработка масок и длин Вычислите битовые маски для всех слов и сохраните их в массиве masks. Сохраните длины всех слов в массиве lens. 2⃣Сравнение слов и проверка общих букв Сравните каждое слово с каждым последующим словом. Если два слова не имеют общих букв (проверка с использованием масок: (masks[i] & masks[j]) == 0), обновите максимальное произведение maxProd. 3⃣Возврат результата Верните максимальное значение произведения maxProd. 😎 Решение:

public class Solution {
    public int MaxProduct(string[] words) {
        int n = words.Length;
        int[] masks = new int[n];
        int[] lens = new int[n];
        
        for (int i = 0; i < n; i++) {
            int bitmask = 0;
            foreach (char ch in words[i]) {
                bitmask |= 1 << (ch - 'a');
            }
            masks[i] = bitmask;
            lens[i] = words[i].Length;
        }
        
        int maxVal = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((masks[i] & masks[j]) == 0) {
                    maxVal = Math.Max(maxVal, lens[i] * lens[j]);
                }
            }
        }
        return maxVal;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

#hard Задача: 317. Shortest Distance from All Buildings Дана сетка m x n, содержащая значения 0, 1 или 2, где: каждое 0 обозначает пустую землю, по которой можно свободно проходить, каждое 1 обозначает здание, через которое нельзя пройти, каждое 2 обозначает препятствие, через которое нельзя пройти. Вы хотите построить дом на пустой земле, чтобы он достиг всех зданий с минимальным суммарным расстоянием. Можно перемещаться только вверх, вниз, влево и вправо. Верните минимальное суммарное расстояние для такого дома. Если построить такой дом невозможно согласно указанным правилам, верните -1. Суммарное расстояние — это сумма расстояний между домами друзей и точкой встречи. Пример:

Input: grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 7

👨‍💻 Алгоритм: 1⃣Инициализация и запуск BFS Для каждой пустой ячейки (0) в сетке grid запустите BFS, обходя все соседние ячейки в 4 направлениях, которые не заблокированы и не посещены, отслеживая расстояние от начальной ячейки. 2⃣Обработка BFS и обновление расстояний При достижении здания (1) увеличьте счетчик достигнутых домов housesReached и суммарное расстояние distanceSum на текущее расстояние. Если housesReached равно общему количеству зданий, верните суммарное расстояние. Если BFS не может достигнуть всех домов, установите значение каждой посещенной пустой ячейки в 2, чтобы не запускать новый BFS из этих ячеек, и верните INT_MAX. 3⃣Обновление и возврат минимального расстояния Обновите минимальное расстояние (minDistance) после каждого вызова BFS. Если возможно достигнуть все дома из любой пустой ячейки, верните найденное минимальное расстояние. В противном случае, верните -1. 😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    private int Bfs(int[][] grid, int row, int col, int totalHouses) {
        int[][] dirs = { new int[] { 1, 0 }, new int[] { -1, 0 }, new int[] { 0, 1 }, new int[] { 0, -1 } };
        int rows = grid.Length, cols = grid[0].Length, distanceSum = 0, housesReached = 0, steps = 0;
        Queue<int[]> q = new Queue<int[]>();
        q.Enqueue(new int[] { row, col });
        bool[,] vis = new bool[rows, cols];
        vis[row, col] = true;

        while (q.Count > 0 && housesReached != totalHouses) {
            int size = q.Count;
            while (size-- > 0) {
                int[] curr = q.Dequeue();
                int r = curr[0], c = curr[1];
                if (grid[r][c] == 1) {
                    distanceSum += steps;
                    housesReached++;
                    continue;
                }
                foreach (var dir in dirs) {
                    int nr = r + dir[0], nc = c + dir[1];
                    if (nr >= 0 && nc >= 0 && nr < rows && nc < cols && !vis[nr, nc] && grid[nr][nc] != 2) {
                        vis[nr, nc] = true;
                        q.Enqueue(new int[] { nr, nc });
                    }
                }
            }
            steps++;
        }

        if (housesReached != totalHouses) {
            for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) if (grid[r][c] == 0 && vis[r, c]) grid[r][c] = 2;
            return int.MaxValue;
        }
        return distanceSum;
    }

    public int ShortestDistance(int[][] grid) {
        int minDistance = int.MaxValue, rows = grid.Length, cols = grid[0].Length, totalHouses = 0;
        foreach (var row in grid) foreach (var cell in row) if (cell == 1) totalHouses++;
        for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) if (grid[r][c] == 0) minDistance = Math.Min(minDistance, Bfs(grid, r, c, totalHouses));
        return minDistance == int.MaxValue ? -1 : minDistance;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Реклама для бизнеса любого уровня в Яндекс Директе Создайте эффективную рекламную кампанию с алгоритмами Яндекс Директа 👌 Начните прямо сейчас ⚡ Зарегистрироваться #реклама direct.yandex.ru О рекламодателе

#medium Задача: 316. Remove Duplicate Letters Дана строка s, удалите повторяющиеся буквы так, чтобы каждая буква появилась один раз и только один раз. Вы должны сделать так, чтобы результат был наименьшим в лексикографическом порядке среди всех возможных результатов. Пример:

Input: s = "bcabc"
Output: "abc"

👨‍💻 Алгоритм: 1⃣Инициализация стека Создайте стек, который будет хранить результат, построенный по мере итерации строки. 2⃣Итерация по строке На каждой итерации добавляйте текущий символ в стек, если он еще не был использован. Перед добавлением текущего символа удаляйте как можно больше символов из вершины стека, если это возможно и улучшает лексикографический порядок. 3⃣Удаление символов Удаляйте символы с вершины стека при выполнении следующих условий: Символ на вершине стека больше текущего символа. Символ может быть удален, так как он встречается позже в строке. На каждом этапе итерации по строке жадно минимизируйте содержимое стека. 😎 Решение:

public class Solution {
    public string RemoveDuplicateLetters(string s) {
        var stack = new Stack<char>();
        var seen = new HashSet<char>();
        var lastOccurrence = new Dictionary<char, int>();
        for (int i = 0; i < s.Length; i++) {
            lastOccurrence[s[i]] = i;
        }

        for (int i = 0; i < s.Length; i++) {
            char c = s[i];
            if (!seen.Contains(c)) {
                while (stack.Count > 0 && c < stack.Peek() && i < lastOccurrence[stack.Peek()]) {
                    seen.Remove(stack.Pop());
                }
                seen.Add(c);
                stack.Push(c);
            }
        }
        return new string(stack.Reverse().ToArray());
    }
}

Ставь 👍 и забирай 📚 Базу знаний

#easy Задача: 404. Sum of Left Leaves Если задан корень бинарного дерева, верните сумму всех левых листьев. Лист - это узел, не имеющий детей. Левый лист - это лист, который является левым ребенком другого узла. Пример:

Input: root = [3,9,20,null,null,15,7]
Output: 24

👨‍💻 Алгоритм: 1⃣Рекурсивный обход дерева Обходите дерево с помощью рекурсивной функции, которая принимает текущий узел и флаг, указывающий, является ли узел левым ребенком. 2⃣Проверка листьев Если текущий узел является листом и флаг указывает, что это левый ребенок, добавьте значение узла к сумме. 3⃣Рекурсивный вызов для детей Рекурсивно вызовите функцию для левого и правого детей текущего узла, передавая соответствующий флаг. 😎 Решение:

public class Solution {
    public int SumOfLeftLeaves(TreeNode root) {
        return Dfs(root, false);
    }
    
    private int Dfs(TreeNode node, bool isLeft) {
        if (node == null) return 0;
        if (node.left == null && node.right == null) return isLeft ? node.val : 0;
        return Dfs(node.left, true) + Dfs(node.right, false);
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Москвич 3 – надежно для вас и ваших увлечений Современный городской кроссовер Москвич 3. Ежемесячный платеж 17 500 рублей. Подробности уточняйте на официальном сайте moskvich.ru. Перейти на сайт Финансовые услуги оказывает: АО "Авто Финанс Банк", ПАО "Совкомбанк". #реклама moskvich.ru О рекламодателе

#hard Задача: 403. Frog Jump Если задана строка num, представляющая неотрицательное целое число num, и целое число k, верните наименьшее возможное целое число после удаления k цифр из num. Пример:

Input: stones = [0,1,3,5,6,8,12,17]
Output: true

👨‍💻 Алгоритм: 1⃣Инициализация и структура данных Создайте набор для хранения всех камней для быстрого доступа. Используйте динамическое программирование с помощью словаря для отслеживания достижимых позиций и возможных прыжков. 2⃣Итерация по камням Пройдитесь по каждому камню и для каждого возможного прыжка (k-1, k, k+1) проверьте, если он ведет на существующий камень. Если такой камень существует, добавьте его в набор возможных прыжков. 3⃣Проверка достижения последнего камня Если можно достичь последний камень с помощью одного из возможных прыжков, верните True. Если после всех итераций последний камень не достигнут, верните False.Формирование результата: Постройте итоговое число из цифр в стеке и удалите ведущие нули. 😎 Решение:

public class Solution {
    public bool CanCross(int[] stones) {
        var dp = new Dictionary<int, HashSet<int>>();
        foreach (var stone in stones) {
            dp[stone] = new HashSet<int>();
        }
        dp[0].Add(0);
        
        foreach (var stone in stones) {
            foreach (var jump in dp[stone]) {
                for (int step = jump - 1; step <= jump + 1; step++) {
                    if (step > 0 && dp.ContainsKey(stone + step)) {
                        dp[stone + step].Add(step);
                    }
                }
            }
        }
        
        return dp[stones[stones.Length - 1]].Count > 0;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

#medium Задача: 402. Remove K Digits Если задана строка num, представляющая неотрицательное целое число num, и целое число k, верните наименьшее возможное целое число после удаления k цифр из num. Пример:

Input: num = "1432219", k = 3
Output: "1219"

👨‍💻 Алгоритм: 1⃣Инициализация: Создайте стек для хранения цифр, которые будут образовывать минимальное число. 2⃣Обработка каждой цифры: Перебирайте каждую цифру в строке num. Если текущая цифра меньше верхней цифры в стеке и у вас есть еще возможность удалить цифры (k > 0), удалите верхнюю цифру из стека. Добавьте текущую цифру в стек. Удаление оставшихся цифр: Если после прохождения всей строки k еще больше нуля, удалите оставшиеся цифры из конца стека 3⃣Формирование результата: Постройте итоговое число из цифр в стеке и удалите ведущие нули. 😎 Решение:

public class Solution {
    public string RemoveKdigits(string num, int k) {
        Stack<char> stack = new Stack<char>();
        foreach (char digit in num) {
            while (k > 0 && stack.Count > 0 && stack.Peek() > digit) {
                stack.Pop();
                k--;
            }
            stack.Push(digit);
        }
        char[] resultArray = stack.ToArray();
        Array.Reverse(resultArray);
        string result = new string(resultArray).Substring(0, resultArray.Length - k).TrimStart('0');
        return result == "" ? "0" : result;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Помощь в трудоустройстве в IT-сфере! В России из-за дефицита айтишников запустили бесплатную программу по обучению IT-специалистов. Теперь любой желающий может попробовать себя в IT с полного нуля и начать обучение бесплатно! Узнайте про дальнейшее трудоустройство в ведущие IT-компании для восполнения кадрового дефицита. Для этого нужно: - Перейти по ссылке - Заполнить анкету и ответить на вопросы (занимает менее 3 минут) - На основании ваших ответов вы сразу узнаете, подходит ли вам сфера IT и сможете ли вы в ней работать Перейти на сайт #реклама 16+ urban-university.ru О рекламодателе

#easy Задача: 401. Binary Watch Бинарные часы имеют 4 светодиода сверху для представления часов (0-11) и 6 светодиодов снизу для представления минут (0-59). Каждый светодиод представляет ноль или единицу, при этом младший разряд находится справа. Пример:

Input: turnedOn = 1
Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

👨‍💻 Алгоритм: 1⃣Генерация всех возможных комбинаций: Переберите все возможные значения для часов и минут. Используйте битовые операции для подсчета количества единиц в бинарном представлении числа. 2⃣Проверка количества горящих светодиодов: Для каждой комбинации проверьте, соответствует ли сумма единиц в бинарном представлении часов и минут заданному количеству горящих светодиодов. 3⃣Форматирование результата: Если комбинация часов и минут соответствует условию, отформатируйте их в виде строки "часы:минуты" и добавьте в список результатов. 😎 Решение:

public class Solution {
    public IList<string> ReadBinaryWatch(int turnedOn) {
        var results = new List<string>();
        for (int h = 0; h < 12; h++) {
            for (int m = 0; m < 60; m++) {
                if (CountBits(h) + CountBits(m) == turnedOn) {
                    results.Add($"{h}:{m:D2}");
                }
            }
        }
        return results;
    }

    private int CountBits(int n) {
        int count = 0;
        while (n > 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

#medium Задача: 400. Nth Digit Дано целое число n, вернуть n-ю цифру бесконечной последовательности чисел [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...]. Пример:

Input: n = 3
Output: 3

👨‍💻 Алгоритм: 1⃣Определение диапазона: Начните с определения количества цифр в числах текущего диапазона (1-9, 10-99, 100-999 и т.д.). Уменьшайте значение n, вычитая количество цифр в текущем диапазоне, пока не найдете диапазон, в который попадает n-я цифра. 2⃣Нахождение конкретного числа: Когда определите диапазон, найдите точное число, содержащее n-ю цифру. Определите индекс цифры в этом числе. 3⃣Возвращение n-й цифры: Извлеките и верните n-ю цифру из найденного числа. 😎 Решение:

public class Solution {
    public int FindNthDigit(int n) {
        long length = 1, count = 9, start = 1;
        
        while (n > length * count) {
            n -= (int)(length * count);
            length++;
            count *= 10;
            start *= 10;
        }
        
        start += (n - 1) / length;
        string s = start.ToString();
        return s[(n - 1) % (int)length] - '0';
    }
}

Ставь 👍 и забирай 📚 Базу знаний

ТОП-4 Курса по Программированию ⚡Tutortop — маркетплейс курсов №1 по количеству школ-партнеров, курсов и реальных отзывов студентов. ✅Хотите стать программистом, но не знаете с какого языка начать? Помогаем разобраться в самых популярных и востребованных языках программирования. Подарок в конце подборки! Выбрать #реклама 16+ tutortop.ru О рекламодателе

#medium Задача: 399. Evaluate Division Вам дан массив пар переменных equations и массив вещественных чисел values, где equations[i] = [Ai, Bi] и values[i] представляют уравнение Ai / Bi = values[i]. Каждая Ai или Bi - это строка, представляющая одну переменную. Вам также даны некоторые запросы, где queries[j] = [Cj, Dj] представляет j-й запрос, в котором вы должны найти ответ для Cj / Dj = ?. Верните ответы на все запросы. Если ни один ответ не может быть определен, верните -1.0. Замечание: входные данные всегда действительны. Можно предположить, что вычисление запросов не приведет к делению на ноль и что противоречия нет. Примечание: Переменные, которые не встречаются в списке уравнений, являются неопределенными, поэтому для них ответ не может быть определен. Пример:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]

👨‍💻 Алгоритм: 1⃣Создание графа: Представьте каждую переменную как узел в графе. Используйте уравнения для создания ребер между узлами, где каждое ребро имеет вес, равный значению уравнения (Ai / Bi = values[i]). Создайте также обратные ребра с обратным весом (Bi / Ai = 1 / values[i]). 2⃣Поиск пути: Для каждого запроса используйте поиск в глубину (DFS) или поиск в ширину (BFS) для поиска пути от Cj до Dj. Если путь найден, вычислите произведение весов вдоль пути, чтобы найти значение Cj / Dj. Если путь не найден, верните -1.0. 3⃣Обработка запросов: Пройдитесь по всем запросам и используйте граф для вычисления результатов каждого запроса. 😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public double[] CalcEquation(IList<IList<string>> equations, double[] values, IList<IList<string>> queries) {
        var graph = new Dictionary<string, Dictionary<string, double>>();

        for (int i = 0; i < equations.Count; i++) {
            string A = equations[i][0], B = equations[i][1];
            double value = values[i];
            if (!graph.ContainsKey(A)) graph[A] = new Dictionary<string, double>();
            if (!graph.ContainsKey(B)) graph[B] = new Dictionary<string, double>();
            graph[A][B] = value;
            graph[B][A] = 1.0 / value;
        }

        double Bfs(string start, string end) {
            if (!graph.ContainsKey(start) || !graph.ContainsKey(end)) return -1.0;
            var q = new Queue<(string, double)>();
            q.Enqueue((start, 1.0));
            var visited = new HashSet<string>();
            
            while (q.Count > 0) {
                var (current, curProduct) = q.Dequeue();
                if (current == end) return curProduct;
                visited.Add(current);
                foreach (var neighbor in graph[current]) {
                    if (!visited.Contains(neighbor.Key)) {
                        q.Enqueue((neighbor.Key, curProduct * neighbor.Value));
                    }
                }
            }
            return -1.0;
        }

        var results = new double[queries.Count];
        for (int i = 0; i < queries.Count; i++) {
            string C = queries[i][0], D = queries[i][1];
            results[i] = Bfs(C, D);
        }
        return results;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

#medium Задача: 398. Random Pick Index Из целочисленного массива nums с возможными дубликатами случайным образом выведите индекс заданного целевого числа. Можно предположить, что заданное целевое число должно существовать в массиве. Реализация класса Solution: Solution(int[] nums) Инициализирует объект с массивом nums. int pick(int target) Выбирает случайный индекс i из nums, где nums[i] == target. Если существует несколько допустимых i, то каждый индекс должен иметь равную вероятность возврата. Пример:

Input
["Solution", "pick", "pick", "pick"]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
Output
[null, 4, 0, 2]

👨‍💻 Алгоритм: 1⃣Инициализируйте объект с массивом nums. Сохраните этот массив для дальнейшего использования. 2⃣Реализуйте метод pick(target), который выбирает случайный индекс i из массива nums, где nums[i] равен target. Если таких индексов несколько, каждый из них должен иметь равную вероятность быть выбранным. 3⃣Для реализации метода pick используйте алгоритм reservoir sampling для выбора случайного индекса. 😎 Решение:

public class Solution {
    private int[] nums;
    private Random random;

    public Solution(int[] nums) {
        this.nums = nums;
        this.random = new Random();
    }

    public int Pick(int target) {
        int count = 0;
        int result = -1;
        for (int i = 0; i < nums.Length; i++) {
            if (nums[i] == target) {
                count++;
                if (random.Next(count) == count - 1) {
                    result = i;
                }
            }
        }
        return result;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Обучение на Frontend-разработчика. С нуля за 9 месяцев. На курсе вы получите все навыки, необходимые для старта в профессии Frontend-разработчика. Персональный наставник middle/senior уровня. 14 проектов, лайвкодинг, хакатоны, репетиции техсобеседования. Освоите JavaScript, React, TypeScript Официальный диплом и сертификат школы. Поддержка наставника по JS в течение 3-х месяцев после диплома. Гарантия трудоустройства. Если вы не устроитесь, вернём деньги. Это закреплено в договоре п. 6.14 С 9 по 30 ноября 2024 г. скидка 40% на все программы Result School Узнать больше #реклама 16+ result.school О рекламодателе

😎 База IT собеседований – твоё секретное оружие для успешного прохождения этапов отбора! Собеседования от реальных компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и многие другие! 🏢 Мы собрали 230 собесов, чтобы ты мог подготовиться к интервью с уверенностью и успехом. 🎯 Присоединяйся к базе и прокачай свои шансы на успешное трудоустройство!

#medium Задача: 397. Integer Replacement К положительному целому числу n можно применить одну из следующих операций: если n четное, замените n на n / 2. если n нечетное, замените n на n + 1 или n - 1. верните минимальное количество операций, необходимых для того, чтобы n стало 1. Пример:

Input: n = 8
Output: 3
Explanation: 8 -> 4 -> 2 -> 1

👨‍💻 Алгоритм: 1⃣Начните с данного числа n и выполните одну из следующих операций: Если n четное, замените n на n / 2. Если n нечетное, замените n на n + 1 или n - 1. 2⃣Используйте метод динамического программирования или жадный метод, чтобы найти минимальное количество операций, необходимых для достижения n = 1. Определите, какая операция (n + 1 или n - 1) является более эффективной для минимизации количества шагов. 3⃣Продолжайте выполнять выбранные операции, пока n не станет равным 1. Считайте количество выполненных операций и верните это значение как результат. 😎 Решение:

public class Solution {
    public int IntegerReplacement(int n) {
        Dictionary<long, int> memo = new Dictionary<long, int>();
        return Helper(n, memo);
    }
    
    private int Helper(long n, Dictionary<long, int> memo) {
        if (n == 1) return 0;
        if (memo.ContainsKey(n)) return memo[n];
        
        if (n % 2 == 0) {
            memo[n] = 1 + Helper(n / 2, memo);
        } else {
            memo[n] = 1 + Math.Min(Helper(n + 1, memo), Helper(n - 1, memo));
        }
        
        return memo[n];
    }
}

Ставь 👍 и забирай 📚 Базу знаний

#hard Задача: 305. Number of Islands II Дан пустой двумерный бинарный массив grid размером m x n. Этот массив представляет собой карту, где 0 означает воду, а 1 — сушу. Изначально все ячейки массива — водные (т.е. все ячейки содержат 0). Вы можете выполнить операцию "добавить землю", которая превращает воду в указанной позиции в сушу. Вам дан массив positions, где positions[i] = [ri, ci] — позиция (ri, ci), в которой следует выполнить i-ю операцию. Верните массив целых чисел answer, где answer[i] — количество островов после превращения ячейки (ri, ci) в сушу. Остров окружен водой и образуется путем соединения соседних земель по горизонтали или вертикали. Вы можете считать, что все четыре края сетки окружены водой. Пример:

Input: m = 1, n = 1, positions = [[0,0]]
Output: [1]

👨‍💻 Алгоритм: 1⃣Инициализация: Создайте массивы x[] = { -1, 1, 0, 0 } и y[] = { 0, 0, -1, 1 }, которые будут использоваться для нахождения соседей ячейки. Создайте экземпляр UnionFind, например, dsu(m * n). Инициализируйте всех родителей значением -1. Используйте объединение по рангу, инициализируйте все ранги значением 0. Наконец, инициализируйте count = 0. Создайте список целых чисел answer, где answer[i] будет хранить количество островов, образованных после превращения ячейки positions[i] в сушу. 2⃣Обработка позиций: Итерация по массиву positions. Для каждой позиции в positions: Выполните линейное отображение, чтобы преобразовать двумерную позицию ячейки в landPosition = position[0] * n + position[1]. Используйте операцию addLand(landPosition), чтобы добавить landPosition как узел в граф. Эта функция также увеличит count. Итерация по каждому соседу позиции. Соседа можно определить с помощью neighborX = position[0] + x[i] и neighborY = position[1] + y[i], где neighborX — координата X, а neighborY — координата Y соседней ячейки. Выполните линейное отображение соседней ячейки с помощью neighborPosition = neighborX * n + neighborY. Теперь, если на neighborPosition есть суша, т.е. isLand(neighborPosition) возвращает true, выполните объединение neighborPosition и landPosition. В объединении уменьшите count на 1. 3⃣Определение количества островов: Выполните операцию numberOfIslands, которая возвращает количество островов, образованных после превращения позиции в сушу. Добавьте это значение в answer. Верните answer. 😎 Решение

public class UnionFind {
    private int[] parent, rank;
    private int count;
    public UnionFind(int size) { parent = new int[size]; rank = new int[size]; Array.Fill(parent, -1); count = 0; }
    public void AddLand(int x) { if (parent[x] < 0) { parent[x] = x; count++; } }
    public bool IsLand(int x) { return parent[x] >= 0; }
    public int NumberOfIslands() { return count; }
    public int Find(int x) { return parent[x] != x ? parent[x] = Find(parent[x]) : x; }
    public void UnionSet(int x, int y) { int xset = Find(x), yset = Find(y); if (xset != yset) {
        if (rank[xset] < rank[yset]) parent[xset] = yset; else { parent[yset] = xset; if (rank[xset] == rank[yset]) rank[xset]++; } count--; } }
}

public class Solution {
    public IList<int> NumIslands2(int m, int n, int[][] positions) {
        var dsu = new UnionFind(m * n);
        int[] x = { -1, 1, 0, 0 }, y = { 0, 0, -1, 1 };
        var answer = new List<int>();
        foreach (var pos in positions) {
            int land = pos[0] * n + pos[1];
            dsu.AddLand(land);
            for (int i = 0; i < 4; ++i) {
                int nx = pos[0] + x[i], ny = pos[1] + y[i], neighbor = nx * n + ny;
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && dsu.IsLand(neighbor)) dsu.UnionSet(land, neighbor);
            }
            answer.Add(dsu.NumberOfIslands());
        }
        return answer;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Продажи на автопилоте: настройка триггерных цепочек Как создать триггерные цепочки, которые сами работают на увеличение ваших продаж? 4 декабря CEO REES46 Михаил Кечинов проведёт вебинар для маркетологов и владельцев интернет-магазинов. Он поделится практическими советами и кейсами, как эффективно использовать автоматизацию маркетинга для повышения выручки и лояльности клиентов. 📚 Что вас ждёт на вебинаре: - Какие триггеры работают лучше всего в 2024 году. - Как настроить автоматические цепочки писем и сообщений. - Как измерить эффективность триггерных кампаний. Бонус для всех участников: готовые шаблоны триггерных цепочек и чек-лист для их быстрого внедрения. 📅 Дата: 4 декабря 2024 года ⚡ Время: 19:00 по МСК Не упустите шанс вывести свой бизнес на новый уровень — зарегистрируйтесь на вебинар прямо сейчас! Зарегистрироваться #реклама 16+ rees46.ru О рекламодателе

#medium Задача: 542. 01 Matrix Дана бинарная матрица размера m x n, верните расстояние до ближайшего нуля для каждой ячейки. Расстояние между двумя соседними ячейками равно 1. Пример:

Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]

👨‍💻 Алгоритм: 1⃣Создайте копию матрицы mat, назовем её matrix. Используйте структуру данных seen для пометки уже посещенных узлов и очередь для выполнения BFS. Поместите все узлы с 0 в очередь и отметьте их в seen. 2⃣Выполните BFS: Пока очередь не пуста, извлекайте текущие row, col, steps из очереди. Итеративно пройдите по четырем направлениям. Для каждой nextRow, nextCol проверьте, находятся ли они в пределах границ и не были ли они уже посещены в seen. 3⃣Если так, установите matrix[nextRow][nextCol] = steps + 1 и поместите nextRow, nextCol, steps + 1 в очередь. Также отметьте nextRow, nextCol в seen. Верните matrix. 😎 Решение:

using System.Collections.Generic;

public class Solution {
    private int m;
    private int n;
    private int[][] directions = new int[][] {
        new int[] {0, 1},
        new int[] {1, 0},
        new int[] {0, -1},
        new int[] {-1, 0}
    };

    public int[][] UpdateMatrix(int[][] mat) {
        m = mat.Length;
        n = mat[0].Length;
        int[][] matrix = new int[m][];
        bool[][] seen = new bool[m][];
        Queue<int[]> queue = new Queue<int[]>();

        for (int i = 0; i < m; i++) {
            matrix[i] = new int[n];
            seen[i] = new bool[n];
            for (int j = 0; j < n; j++) {
                matrix[i][j] = mat[i][j];
                if (matrix[i][j] == 0) {
                    queue.Enqueue(new int[] {i, j, 0});
                    seen[i][j] = true;
                }
            }
        }

        while (queue.Count > 0) {
            int[] curr = queue.Dequeue();
            int row = curr[0], col = curr[1], steps = curr[2];

            foreach (var direction in directions) {
                int nextRow = row + direction[0], nextCol = col + direction[1];
                if (IsValid(nextRow, nextCol) && !seen[nextRow][nextCol]) {
                    seen[nextRow][nextCol] = true;
                    queue.Enqueue(new int[] {nextRow, nextCol, steps + 1});
                    matrix[nextRow][nextCol] = steps + 1;
                }
            }
        }

        return matrix;
    }

    private bool IsValid(int row, int col) {
        return 0 <= row && row < m && 0 <= col && col < n;
    }
}

Ставь 👍 и забирай 📚 Базу знаний