C# | LeetCode

Задача: 928. Minimize Malware Spread II Сложность: hard Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока больше не останется ни одного узла, зараженного таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим ровно один узел из initial, полностью удалив его и все связи от этого узла к любому другому узлу. Верните узел, который, если его удалить, минимизирует M(initial). Если для минимизации M(initial) можно удалить несколько узлов, верните такой узел с наименьшим индексом. Пример:

Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0

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

public class Solution {
    public int MinMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.Length;
        var visited = new HashSet<int>();
        var components = new List<HashSet<int>>();
        
        void Dfs(int node) {
            var stack = new Stack<int>();
            stack.Push(node);
            var component = new HashSet<int>();
            while (stack.Count > 0) {
                int u = stack.Pop();
                if (!visited.Contains(u)) {
                    visited.Add(u);
                    component.Add(u);
                    for (int v = 0; v < n; v++) {
                        if (graph[u][v] == 1 && !visited.Contains(v)) {
                            stack.Push(v);
                        }
                    }
                }
            }
            components.Add(component);
        }
        
        for (int i = 0; i < n; i++) {
            if (!visited.Contains(i)) {
                Dfs(i);
            }
        }
        
        int[] infectedInComponent = new int[components.Count];
        int[] nodeToComponent = new int[n];
        Array.Fill(nodeToComponent, -1);
        
        for (int idx = 0; idx < components.Count; idx++) {
            var component = components[idx];
            foreach (int node in component) {
                nodeToComponent[node] = idx;
                if (Array.IndexOf(initial, node) >= 0) {
                    infectedInComponent[idx]++;
                }
            }
        }
        
        int minInfected = int.MaxValue;
        int resultNode = initial.Min();
        
        foreach (int node in initial) {
            int componentIdx = nodeToComponent[node];
            if (infectedInComponent[componentIdx] == 1) {
                int componentSize = components[componentIdx].Count;
                if (componentSize < minInfected || (componentSize == minInfected && node < resultNode)) {
                    minInfected = componentSize;
                    resultNode = node;
                }
            }
        }
        
        return resultNode;
    }
}

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

Задача: 959. Regions Cut By Slashes Сложность: medium n x n сетка состоит из квадратов размером 1 x 1, где каждый квадрат 1 x 1 содержит '/', '', или пустое пространство ' '. Эти символы делят квадрат на смежные области. Дана сетка grid, представленная в виде строкового массива. Верните количество областей. Обратите внимание, что обратные слеши экранированы, поэтому '' представлен как '\'. Пример:

Input: grid = [" /","/ "]
Output: 2

👨‍💻 Алгоритм: 1⃣Создайте 4*N*N узлов для каждой ячейки сетки и соедините их в соответствии с описанием. 2⃣Используйте структуру объединения-поиска (DSU), чтобы найти количество связанных компонентов. 3⃣Пройдите по всем узлам и посчитайте количество корневых узлов, которые представляют количество областей. 😎 Решение:

public class DSU {
    int[] parent;
    public DSU(int N) {
        parent = new int[N];
        for (int i = 0; i < N; ++i)
            parent[i] = i;
    }
    public int Find(int x) {
        if (parent[x] != x) parent[x] = Find(parent[x]);
        return parent[x];
    }
    public void Union(int x, int y) {
        parent[Find(x)] = Find(y);
    }
}

public class Solution {
    public int RegionsBySlashes(string[] grid) {
        int N = grid.Length;
        DSU dsu = new DSU(4 * N * N);
        
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) {
                int root = 4 * (r * N + c);
                char val = grid[r][c];
                
                if (val != '\\') {
                    dsu.Union(root + 0, root + 1);
                    dsu.Union(root + 2, root + 3);
                }
                if (val != '/') {
                    dsu.Union(root + 0, root + 2);
                    dsu.Union(root + 1, root + 3);
                }
                
                if (r + 1 < N) {
                    dsu.Union(root + 3, (root + 4 * N) + 0);
                }
                if (r - 1 >= 0) {
                    dsu.Union(root + 0, (root - 4 * N) + 3);
                }
                if (c + 1 < N) {
                    dsu.Union(root + 2, (root + 4) + 1);
                }
                if (c - 1 >= 0) {
                    dsu.Union(root + 1, (root - 4) + 2);
                }
            }
        }
        
        int ans = 0;
        for (int x = 0; x < 4 * N * N; ++x) {
            if (dsu.Find(x) == x) {
                ++ans;
            }
        }
        
        return ans;
    }
}

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

Задача: 1165. Single-Row Keyboard Сложность: easy Есть специальная клавиатура, на которой все клавиши расположены в один ряд. Дана строка keyboard длиной 26, указывающая на раскладку клавиатуры (индексирована от 0 до 25). Изначально ваш палец находится на индексе 0. Чтобы напечатать символ, нужно переместить палец на индекс нужного символа. Время, затраченное на перемещение пальца с индекса i на индекс j, равно |i - j|. Вам нужно напечатать строку word. Напишите функцию для расчета времени, необходимого для её набора одним пальцем. Пример:

Input: keyboard = "abcdefghijklmnopqrstuvwxyz", word = "cba"
Output: 4
Explanation: The index moves from 0 to 2 to write 'c' then to 1 to write 'b' then to 0 again to write 'a'.
Total time = 2 + 1 + 1 = 4.

👨‍💻 Алгоритм: 1⃣Клавиатура содержит уникальные строчные английские буквы, поэтому мы можем сопоставить её с массивом размера 26. Создадим массив размера 26, назовём его keyIndices. Сохраните индекс каждой буквы в этом массиве, проходя по строке keyboard. Инициализируйте переменную result значением 0, которая будет хранить сумму всех расстояний. Объявите переменную prev, которая будет хранить индекс предыдущей клавиши. Поскольку начальная позиция равна 0, инициализируйте её значением 0. 2⃣Проходите по строке word буква за буквой. Для каждой буквы c добавьте ∣prev−indexOf(c)∣ к result. Обновите prev до индекса c. 3⃣Повторите шаги 6 и 7 для всех букв. В конце прохода result будет содержать итоговое время, необходимое для набора слова. 😎 Решение:

public class Solution {
    public int CalculateTime(string keyboard, string word) {
        int[] keyIndices = new int[26];
        for (int i = 0; i < keyboard.Length; i++) {
            keyIndices[keyboard[i] - 'a'] = i;
        }
        
        int prev = 0;
        int result = 0;
        
        foreach (char c in word) {
            int index = keyIndices[c - 'a'];
            result += Math.Abs(prev - index);
            prev = index;
        }
        
        return result;
    }
}

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

Задача: 153. Find Minimum in Rotated Sorted Array Сложность: medium Предположим, что массив длиной n, отсортированный в порядке возрастания, повернут от 1 до n раз. Например, массив nums = [0,1,2,4,5,6,7] может стать: [4,5,6,7,0,1,2], если он был повернут 4 раза. [0,1,2,4,5,6,7], если он был повернут 7 раз. Обратите внимание, что поворот массива [a[0], a[1], a[2], ..., a[n-1]] 1 раз приводит к массиву [a[n-1], a[0], a[1], a[2], ..., a[n-2]]. Для данного отсортированного и повернутого массива nums с уникальными элементами верните минимальный элемент этого массива. Вы должны написать алгоритм, который работает за время O(log n). Пример:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

👨‍💻 Алгоритм: 1⃣Нахождение середины массива: Определите элемент, находящийся посередине массива. 2⃣Определение направления поиска: Если элемент в середине больше первого элемента массива, это означает, что точка перегиба (минимальный элемент) находится справа от середины. Если элемент в середине меньше первого элемента массива, это указывает на то, что точка перегиба находится слева от середины. 3⃣Остановка поиска при нахождении точки перегиба: Поиск прекращается, когда найдена точка перегиба, когда выполняется одно из двух условий: nums[mid] > nums[mid + 1] – следовательно, mid+1 является наименьшим элементом. nums[mid - 1] > nums[mid] – следовательно, mid является наименьшим элементом. 😎 Решение:

public class Solution {
    public int FindMin(int[] nums) {
        if (nums.Length == 1) {
            return nums[0];
        }
        int left = 0, right = nums.Length - 1;

        if (nums[right] > nums[0]) {
            return nums[0];
        }

        while (right >= left) {
          
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                return nums[mid + 1];
            }

            if (nums[mid - 1] > nums[mid]) {
                return nums[mid];
            }
            if (nums[mid] > nums[0]) {
                left = mid + 1;
            } else {
                               right = mid - 1;
            }
        }

        return Int32.MaxValue;
    }
}

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

Задача: 1244. Design A Leaderboard Сложность: medium Разработайте класс Leaderboard, который содержит 3 функции: addScore(playerId, score): Обновляет таблицу лидеров, добавляя счет к счету данного игрока. Если в таблице лидеров нет игрока с таким id, добавьте его в таблицу лидеров с заданным счетом. top(K): Возвращает сумму очков K лучших игроков. reset(playerId): Сбрасывает счет игрока с заданным идентификатором в 0 (другими словами, стирает его из таблицы лидеров). Гарантируется, что игрок был добавлен в таблицу лидеров до вызова этой функции. Изначально таблица лидеров пуста. Пример:

Input: 
["Leaderboard","addScore","addScore","addScore","addScore","addScore","top","reset","reset","addScore","top"]
[[],[1,73],[2,56],[3,39],[4,51],[5,4],[1],[1],[2],[2,51],[3]]
Output: 
[null,null,null,null,null,null,73,null,null,null,141]

👨‍💻 Алгоритм: 1⃣addScore(playerId, score): Если игрок уже существует в таблице лидеров, добавляем к его текущему счету новое значение. Если игрок не существует, добавляем его с заданным счетом. 2⃣top(K): Сортируем игроков по их счету в порядке убывания. Возвращаем сумму очков K лучших игроков. 3⃣reset(playerId): Устанавливаем счет игрока в 0. 😎 Решение:

using System;
using System.Collections.Generic;
using System.Linq;

public class Leaderboard {
    private Dictionary<int, int> scores;

    public Leaderboard() {
        scores = new Dictionary<int, int>();
    }

    public void AddScore(int playerId, int score) {
        if (scores.ContainsKey(playerId)) {
            scores[playerId] += score;
        } else {
            scores[playerId] = score;
        }
    }

    public int Top(int K) {
        return scores.Values.OrderByDescending(x => x).Take(K).Sum();
    }

    public void Reset(int playerId) {
        if (scores.ContainsKey(playerId)) {
            scores[playerId] = 0;
        }
    }
}

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

Задача: 666. Path Sum IV Сложность: medium Если глубина дерева меньше 5, то это дерево можно представить в виде массива трехзначных чисел. Для каждого числа в этом массиве: Сотни представляют глубину d этого узла, где 1 <= d <= 4. Десятки представляют позицию p этого узла на уровне, которому он принадлежит, где 1 <= p <= 8. Позиция соответствует позиции в полном бинарном дереве. Единицы представляют значение v этого узла, где 0 <= v <= 9. Дан массив возрастающих трехзначных чисел nums, представляющих бинарное дерево с глубиной меньше 5. Верните сумму всех путей от корня к листьям. Гарантируется, что данный массив представляет собой валидное связанное бинарное дерево. Пример:

Input: nums = [113,215,221]
Output: 12
Explanation: The tree that the list represents is shown.
The path sum is (3 + 5) + (3 + 1) = 12.

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

public class Solution {
    public int PathSum(int[] nums) {
        var tree = new Dictionary<int, int>();
        
        foreach (int num in nums) {
            int depth = num / 100;
            int pos = (num / 10) % 10;
            int val = num % 10;
            tree[depth * 10 + pos] = val;
        }
        
        return Dfs(tree, 1, 1, 0);
    }
    
    private int Dfs(Dictionary<int, int> tree, int depth, int pos, int currentSum) {
        int key = depth * 10 + pos;
        if (!tree.ContainsKey(key)) {
            return 0;
        }
        currentSum += tree[key];
        int leftChild = (depth + 1) * 10 + 2 * pos - 1;
        int rightChild = (depth + 1) * 10 + 2 * pos;
        if (!tree.ContainsKey(leftChild) && !tree.ContainsKey(rightChild)) {
            return currentSum;
        }
        return Dfs(tree, depth + 1, 2 * pos - 1, currentSum) + Dfs(tree, depth + 1, 2 * pos, currentSum);
    }
}

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

Главный навык на ближайшие годы — ВАЙБ-КОДИНГ ИИ уже пишет код, чинит баги, генерирует тесты, документацию и помогает запускать продукты быстрее, чем это делали классические команды разработки. И это уже не "будущее когда-нибудь", а реальность, которая меняет рынок уже сегодня И те, кто научится вайбкодить сейчас, будут увереннее конкурировать на рынке и зарабатывать больше тех, кто по-прежнему делает всё вручную. Стартовать с нуля поможет канал Вайб-кодинг. Там ребята круглосуточно мониторят более 320 российских и зарубежных источников и публикуют только главное: релизы, инструменты, гайды, курсы и практические кейсы. Подписывайтесь, нас уже 30 тысяч: @vibecoding_tg

Задача: 318. Maximum Product of Word Lengths Сложность: medium Дан массив строк 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;
    }
}

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

Задача: 678. Valid Parenthesis String Сложность: medium Создайте карту, которая позволяет выполнять следующие действия: Отображает строковый ключ на заданное значение. Возвращает сумму значений, у которых ключ имеет префикс, равный заданной строке. Реализуйте класс MapSum: Дана строка s, содержащая только три типа символов: '(', ')' и '*'. Вернуть true, если s является допустимой. Следующие правила определяют допустимую строку: Любая открывающая скобка '(' должна иметь соответствующую закрывающую скобку ')'. Любая закрывающая скобка ')' должна иметь соответствующую открывающую скобку '('. Открывающая скобка '(' должна идти перед соответствующей закрывающей скобкой ')'. '*' может рассматриваться как одна закрывающая скобка ')', одна открывающая скобка '(' или пустая строка "". Пример:

Input: s = "()"
Output: true
Example 2:

👨‍💻 Алгоритм: 1⃣Инициализировать 2D вектор memo размером s.size() x s.size() - 1, представляющий неинициализированное состояние. Вызвать вспомогательную функцию isValidString с начальными параметрами index = 0, openCount = 0 и строкой s. Вернуть результат isValidString. 2⃣Вспомогательная функция isValidString. Базовый случай: если index достиг конца строки (index == s.size.), вернуть true, если openCount равен 0 (все скобки сбалансированы), и false в противном случае. Проверить, был ли результат для текущего index и openCount уже вычислен (мемоизирован) в memo. Если да, вернуть мемоизированный результат. Инициализировать isValid как false. Если текущий символ s[index] равен '*': Попробовать трактовать '*' как '(' и вызвать isValidString рекурсивно с index + 1 и openCount + 1. Если рекурсивный вызов вернет true, обновить isValid на true. Если openCount не равен нулю, попробовать трактовать '*' как ')' и вызвать isValidString рекурсивно с index + 1 и openCount - 1. Если рекурсивный вызов вернет true, обновить isValid на true. Попробовать трактовать '*' как пустой символ и вызвать isValidString рекурсивно с index + 1 и тем же openCount. Если рекурсивный вызов вернет true, обновить isValid на true. 3⃣Продолжение функции isValidString. Если текущий символ s[index] равен '(': Вызвать isValidString рекурсивно с index + 1 и openCount + 1. Обновить isValid с результатом рекурсивного вызова. Если текущий символ s[index] равен ')': Если openCount не равен нулю (есть открытые скобки), вызвать isValidString рекурсивно с index + 1 и openCount - 1. Обновить isValid с результатом рекурсивного вызова. Мемоизировать результат isValid в memo[index][openCount]. Вернуть isValid. 😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public bool CheckValidString(string s) {
        int n = s.Length;
        int[][] memo = new int[n][];
        for (int i = 0; i < n; i++) {
            memo[i] = new int[n];
            Array.Fill(memo[i], -1);
        }
        return IsValidString(0, 0, s, memo);
    }

    private bool IsValidString(int index, int openCount, string str, int[][] memo) {
        if (index == str.Length) {
            return openCount == 0;
        }

        if (memo[index][openCount] != -1) {
            return memo[index][openCount] == 1;
        }

        bool isValid = false;

        if (str[index] == '*') {
            isValid = IsValidString(index + 1, openCount + 1, str, memo);
            if (openCount > 0) {
                isValid = isValid || IsValidString(index + 1, openCount - 1, str, memo);
            }
            isValid = isValid || IsValidString(index + 1, openCount, str, memo);
        } else if (str[index] == '(') {
            isValid = IsValidString(index + 1, openCount + 1, str, memo);
        } else if (openCount > 0) {
            isValid = IsValidString(index + 1, openCount - 1, str, memo);
        }

        memo[index][openCount] = isValid ? 1 : 0;
        return isValid;
    }
}

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

Задача: 1469. Find All The Lonely Nodes Сложность: easy В бинарном дереве одиночный узел — это узел, который является единственным ребёнком своего родительского узла. Корень дерева не является одиночным, так как у него нет родительского узла. Дано корневое значение бинарного дерева. Верните массив, содержащий значения всех одиночных узлов в дереве. Верните список в любом порядке. Пример:

Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2]
Output: [6,2]
Explanation: Light blue nodes are lonely nodes.
Please remember that order doesn't matter, [2,6] is also an acceptable answer.

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

using System;
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public void DFS(TreeNode root, bool isLonely, List<int> ans) {
        if (root == null) {
            return;
        }
        
        if (isLonely) {
            ans.Add(root.val);
        }
        
        DFS(root.left, root.right == null, ans);
        DFS(root.right, root.left == null, ans);
    }
    
    public IList<int> GetLonelyNodes(TreeNode root) {
        List<int> ans = new List<int>();
        DFS(root, false, ans);
        return ans;
    }
}

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

Задача: 765. Couples Holding Hands Сложность: hard Есть n пар, сидящих на 2n местах, расположенных в ряд, и они хотят держаться за руки. Люди и места представлены массивом целых чисел row, где row[i] — это ID человека, сидящего на i-м месте. Пары пронумерованы по порядку: первая пара — (0, 1), вторая пара — (2, 3) и так далее, до последней пары — (2n - 2, 2n - 1). Верните минимальное количество перестановок, чтобы каждая пара сидела рядом. Перестановка состоит из выбора любых двух человек, которые встают и меняются местами. Пример:

Input: row = [0,2,1,3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

👨‍💻 Алгоритм: 1⃣Мы могли бы предположить без доказательства, что решение, при котором мы делаем людей на каждом диване счастливыми по порядку, является оптимальным. Это предположение сильнее, чем гипотеза о жадном подходе, но кажется разумным, поскольку при каждом ходе мы делаем хотя бы одну пару счастливой. 2⃣При таком предположении, для какого-то дивана с несчастливыми людьми X и Y, мы либо заменяем Y на партнера X, либо заменяем X на партнера Y. Для каждой из двух возможностей мы можем попробовать оба варианта, используя подход с возвратом. 3⃣Для каждого дивана с двумя возможностями (т.е. оба человека на диване несчастливы) мы попробуем первый вариант, найдем ответ как ans1, затем отменим наш ход и попробуем второй вариант, найдем связанный ответ как ans2, отменим наш ход и затем вернем наименьший ответ. 😎 Решение:

public class Solution {
    int N;
    int[][] pairs;

    public int MinSwapsCouples(int[] row) {
        N = row.Length / 2;
        pairs = new int[N][];
        for (int i = 0; i < N; ++i) {
            pairs[i] = new int[2];
            pairs[i][0] = row[2 * i] / 2;
            pairs[i][1] = row[2 * i + 1] / 2;
        }
        return Solve(0);
    }

    public void Swap(int a, int b, int c, int d) {
        int t = pairs[a][b];
        pairs[a][b] = pairs[c][d];
        pairs[c][d] = t;
    }

    public int Solve(int i) {
        if (i == N) return 0;
        int x = pairs[i][0], y = pairs[i][1];
        if (x == y) return Solve(i + 1);

        int jx = 0, kx = 0, jy = 0, ky = 0;
        for (int j = i + 1; j < N; ++j) {
            for (int k = 0; k <= 1; ++k) {
                if (pairs[j][k] == x) { jx = j; kx = k; }
                if (pairs[j][k] == y) { jy = j; ky = k; }
            }
        }

        Swap(i, 1, jx, kx);
        int ans1 = 1 + Solve(i + 1);
        Swap(i, 1, jx, kx);

        Swap(i, 0, jy, ky);
        int ans2 = 1 + Solve(i + 1);
        Swap(i, 0, jy, ky);

        return Math.Min(ans1, ans2);
    }
}

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

Задача: 267. Palindrome Permutation II Сложность: medium Дана строка s, верните все палиндромные перестановки (без дубликатов) этой строки. Вы можете вернуть ответ в любом порядке. Если у строки s нет палиндромных перестановок, верните пустой список. Пример:

Input: s = "aabb"
Output: ["abba","baab"]

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

using System;
using System.Collections.Generic;
using System.Text;

public class Solution {
    private HashSet<string> set;

    public Solution() {
        set = new HashSet<string>();
    }

    public IList<string> GeneratePalindromes(string s) {
        int[] map = new int[128];
        char[] st = new char[s.Length / 2];
        if (!CanPermutePalindrome(s, map)) {
            return new List<string>();
        }

        char ch = '\0';
        int k = 0;
        for (int i = 0; i < map.Length; i++) {
            if (map[i] % 2 == 1) {
                ch = (char)i;
            }
            for (int j = 0; j < map[i] / 2; j++) {
                st[k++] = (char)i;
            }
        }
        Permute(st, 0, ch);
        return new List<string>(set);
    }

    private bool CanPermutePalindrome(string s, int[] map) {
        int count = 0;
        foreach (char c in s) {
            int index = (int)c;
            map[index]++;
            if (map[index] % 2 == 0) {
                count--;
            } else {
                count++;
            }
        }
        return count <= 1;
    }

    private void Swap(ref char[] s, int i, int j) {
        char temp = s[i];
        s[i] = s[j];
        s[j] = temp;
    }

    private void Permute(char[] s, int l, char ch) {
        if (l == s.Length) {
            StringBuilder sb = new StringBuilder();
            sb.Append(s);
            if (ch != '\0') {
                sb.Append(ch);
            }
            Array.Reverse(s);
            sb.Append(s);
            set.Add(sb.ToString());
            Array.Reverse(s);
        } else {
            for (int i = l; i < s.Length; i++) {
                if (s[l] != s[i] || l == i) {
                    Swap(ref s, l, i);
                    Permute(s, l + 1, ch);
                    Swap(ref s, l, i);
                }
            }
        }
    }
}

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

Задача: 951. Flip Equivalent Binary Trees Сложность: medium Для бинарного дерева T мы можем определить операцию переворота следующим образом: выбираем любой узел и меняем местами левое и правое дочерние поддеревья. Бинарное дерево X эквивалентно бинарному дереву Y тогда и только тогда, когда мы можем сделать X равным Y после некоторого количества операций переворота. Учитывая корни двух бинарных деревьев root1 и root2, верните true, если эти два дерева эквивалентны перевороту, или false в противном случае. Пример:

Input: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
Output: true

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

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public bool FlipEquiv(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) return true;
        if (root1 == null || root2 == null) return false;
        if (root1.val != root2.val) return false;
        
        return (FlipEquiv(root1.left, root2.left) && FlipEquiv(root1.right, root2.right)) ||
               (FlipEquiv(root1.left, root2.right) && FlipEquiv(root1.right, root2.left));
    }
}

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

Задача: 127. Word Ladder Сложность: hard Секвенция трансформации от слова beginWord к слову endWord с использованием словаря wordList представляет собой последовательность слов beginWord -> s1 -> s2 -> ... -> sk, при которой: Каждая пара соседних слов отличается ровно одной буквой. Каждый элемент si для 1 <= i <= k присутствует в wordList. Отметим, что beginWord не обязан быть в wordList. sk равно endWord. Для двух слов, beginWord и endWord, и словаря wordList, верните количество слов в кратчайшей секвенции трансформации от beginWord к endWord, или 0, если такая секвенция не существует. Пример:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

👨‍💻 Алгоритм: 1⃣Препроцессинг списка слов: Осуществите препроцессинг заданного списка слов (wordList), чтобы найти все возможные промежуточные состояния слов. Сохраните эти состояния в словаре, где ключом будет промежуточное слово, а значением — список слов, имеющих то же промежуточное состояние. 2⃣Использование очереди для обхода: Поместите в очередь кортеж, содержащий beginWord и число 1, где 1 обозначает уровень узла. Вам нужно вернуть уровень узла endWord, так как он будет представлять длину кратчайшей последовательности преобразования. Используйте словарь посещений, чтобы избежать циклов. 3⃣Поиск кратчайшего пути через BFS (обход в ширину): Пока в очереди есть элементы, получите первый элемент очереди. Для каждого слова определите все промежуточные преобразования и проверьте, не являются ли эти преобразования также преобразованиями других слов из списка. Для каждого найденного слова, которое имеет общее промежуточное состояние с текущим словом, добавьте в очередь пару (слово, уровень + 1), где уровень — это уровень текущего слова. Если вы достигли искомого слова, его уровень покажет длину кратчайшей последовательности преобразования. 😎 Решение:

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int LadderLength(string beginWord, string endWord, IList<string> wordList) {
        int L = beginWord.Length;
        Dictionary<string, List<string>> allComboDict = new Dictionary<string, List<string>>();
        foreach (string word in wordList) {
            for (int i = 0; i < L; i++) {
                string newWord = word.Substring(0, i) + '*' + word.Substring(i + 1, L - i - 1);
                if (!allComboDict.ContainsKey(newWord))
                    allComboDict[newWord] = new List<string>();
                allComboDict[newWord].Add(word);
            }
        }

        Queue<Tuple<string, int>> Q = new Queue<Tuple<string, int>>();
        Q.Enqueue(new Tuple<string, int>(beginWord, 1));
        Dictionary<string, bool> visited = new Dictionary<string, bool>();
        visited[beginWord] = true;
        while (Q.Any()) {
            var node = Q.Dequeue();
            string word = node.Item1;
            int level = node.Item2;
            for (int i = 0; i < L; i++) {
                string newWord = word.Substring(0, i) + '*' + word.Substring(i + 1, L - i - 1);
                foreach (string adjacentWord in allComboDict.GetValueOrDefault(newWord, new List<string>())) {
                    if (adjacentWord.Equals(endWord))
                        return level + 1;
                    if (!visited.ContainsKey(adjacentWord)) {
                        visited[adjacentWord] = true;
                        Q.Enqueue(new Tuple<string, int>(adjacentWord, level + 1));
                    }
                }
            }
        }

        return 0;
    }
}

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

Задача: 726. Number of Atoms Сложность: hard Если задана строковая формула, представляющая химическую формулу, верните количество атомов. Атомный элемент всегда начинается с прописного символа, затем ноль или более строчных букв, представляющих его название. Если количество больше 1, за ним может следовать одна или более цифр, представляющих количество элементов. Например, "H2O" и "H2O2" возможны, а "H1O2" невозможен. Две формулы объединяются вместе, чтобы получить другую формулу. Например, "H2O2He3Mg4" также является формулой. Формула, заключенная в круглые скобки, и счет (по желанию) также являются формулами. Например, "(H2O2)" и "(H2O2)3" являются формулами. Возвращает количество всех элементов в виде строки в следующем виде: первое имя (в отсортированном порядке), затем его количество (если это количество больше 1), затем второе имя (в отсортированном порядке), затем его количество (если это количество больше 1) и т. д. Тестовые примеры генерируются таким образом, чтобы все значения в выводе помещались в 32-битное целое число. Пример:

Input: formula = "H2O"
Output: "H2O"

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

public class Solution {
    public string CountOfAtoms(string formula) {
        var stack = new Stack<Dictionary<string, int>>();
        stack.Push(new Dictionary<string, int>());
        int n = formula.Length;
        int i = 0;

        while (i < n) {
            if (formula[i] == '(') {
                stack.Push(new Dictionary<string, int>());
                i++;
            } else if (formula[i] == ')') {
                var top = stack.Pop();
                i++;
                int start = i;
                while (i < n && Char.IsDigit(formula[i])) {
                    i++;
                }
                int multiplicity = i > start ? int.Parse(formula.Substring(start, i - start)) : 1;
                foreach (var name in top.Keys) {
                    int count = top[name];
                    if (stack.Peek().ContainsKey(name)) {
                        stack.Peek()[name] += count * multiplicity;
                    } else {
                        stack.Peek()[name] = count * multiplicity;
                    }
                }
            } else {
                int start = i;
                i++;
                while (i < n && Char.IsLower(formula[i])) {
                    i++;
                }
                string name = formula.Substring(start, i - start);
                start = i;
                while (i < n && Char.IsDigit(formula[i])) {
                    i++;
                }
                int multiplicity = i > start ? int.Parse(formula.Substring(start, i - start)) : 1;
                if (stack.Peek().ContainsKey(name)) {
                    stack.Peek()[name] += multiplicity;
                } else {
                    stack.Peek()[name] = multiplicity;
                }
            }
        }

        var countMap = stack.Pop();
        var sb = new StringBuilder();
        foreach (var name in countMap.Keys.OrderBy(x => x)) {
            sb.Append(name);
            int count = countMap[name];
            if (count > 1) {
                sb.Append(count);
            }
        }
        return sb.ToString();
    }
}

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

Задача: 1672. Richest Customer Wealth Сложность: easy Вам дан целочисленный массив размером m x n под названием accounts, где accounts[i][j] — это сумма денег, которую i-й клиент имеет в j-м банке. Верните богатство самого богатого клиента. Богатство клиента — это сумма денег, которую он имеет во всех своих банковских счетах. Самый богатый клиент — это клиент, который имеет максимальное богатство. Пример:

Input: accounts = [[1,2,3],[3,2,1]]
Output: 6
Explanation:
1st customer has wealth = 1 + 2 + 3 = 6
2nd customer has wealth = 3 + 2 + 1 = 6
Both customers are considered the richest with a wealth of 6 each, so return 6.

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

public class Solution {
    public int MaximumWealth(int[][] accounts) {
        int maxWealthSoFar = 0;
        
        foreach (var account in accounts) {
            int currCustomerWealth = account.Sum();
            maxWealthSoFar = Math.Max(maxWealthSoFar, currCustomerWealth);
        }
        
        return maxWealthSoFar;
    }
}

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

Задача: 1238. Circular Permutation in Binary Representation Сложность: medium Вам дан массив строк arr. Строка s образуется конкатенацией подпоследовательности arr, содержащей уникальные символы. Верните максимально возможную длину s. Подпоследовательность - это массив, который может быть получен из другого массива путем удаления некоторых или ни одного элемента без изменения порядка оставшихся элементов. Пример:

Input: arr = ["un","iq","ue"]
Output: 4

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

using System;
using System.Collections.Generic;

public class Solution {
    public int MaxLength(IList<string> arr) {
        return Backtrack(arr, 0, "");
    }

    private bool IsUnique(string s) {
        HashSet<char> charSet = new HashSet<char>(s);
        return charSet.Count == s.Length;
    }

    private int Backtrack(IList<string> arr, int index, string current) {
        if (!IsUnique(current)) return 0;
        int maxLength = current.Length;
        for (int i = index; i < arr.Count; i++) {
            maxLength = Math.Max(maxLength, Backtrack(arr, i + 1, current + arr[i]));
        }
        return maxLength;
    }
}

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

Задача: 997. Find the Town Judge Сложность: easy В городе есть n человек, помеченных от 1 до n. Ходят слухи, что один из этих людей тайно является городским судьей. Если городской судья существует, то: городской судья никому не доверяет. Все (кроме городского судьи) доверяют городскому судье. Существует ровно один человек, удовлетворяющий свойствам 1 и 2. Вам дан массив trust, где trust[i] = [ai, bi], представляющий, что человек, помеченный ai, доверяет человеку, помеченному bi. Если в массиве trust не существует доверительных отношений, то таких отношений не существует. Верните метку городского судьи, если городской судья существует и может быть идентифицирован, или верните -1 в противном случае. Пример:

Input: n = 2, trust = [[1,2]]
Output: 2

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

public class Solution {
    public int FindJudge(int n, int[][] trust) {
        if (trust.Length == 0 && n == 1) {
            return 1;
        }

        int[] trustCount = new int[n + 1];
        int[] trustedBy = new int[n + 1];

        foreach (var t in trust) {
            trustCount[t[0]]++;
            trustedBy[t[1]]++;
        }

        for (int i = 1; i <= n; i++) {
            if (trustCount[i] == 0 && trustedBy[i] == n - 1) {
                return i;
            }
        }

        return -1;
    }
}

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

Задача: 989. Add to Array-Form of Integer Сложность: easy Массивная форма целого числа num - это массив, представляющий его цифры в порядке слева направо. Например, для num = 1321, массивная форма - это [1, 3, 2, 1]. Дано num в массивной форме целого числа и целое число k, верните массивную форму числа num + k. Пример:

Input: num = [1,2,0,0], k = 34
Output: [1,2,3,4]
Explanation: 1200 + 34 = 1234

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

using System;
using System.Collections.Generic;

public class Solution {
    public IList<int> AddToArrayForm(int[] num, int k) {
        List<int> result = new List<int>();
        int n = num.Length;

        for (int i = n - 1; i >= 0; i--) {
            k += num[i];
            result.Add(k % 10);
            k /= 10;
        }
        while (k > 0) {
            result.Add(k % 10);
            k /= 10;
        }
        result.Reverse();
        return result;
    }
}

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

Задача: 924. Minimize Malware Spread Сложность: hard Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока не останется ни одного узла, который можно было бы заразить таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим из initial ровно один узел. Верните тот узел, удаление которого минимизирует M(initial). Если можно удалить несколько узлов, чтобы минимизировать M(initial), верните такой узел с наименьшим индексом. Обратите внимание, что если узел был удален из начального списка зараженных узлов, он все равно может быть заражен позже из-за распространения вредоносного ПО. Пример:

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20

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

using System;
using System.Collections.Generic;

public class Solution {
    public int MinMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.Length;
        HashSet<int> initialSet = new HashSet<int>(initial);
        Array.Sort(initial);
        int minInfected = int.MaxValue;
        int bestNode = initial[0];
        
        foreach (int node in initial) {
            HashSet<int> infected = new HashSet<int>(initialSet);
            infected.Remove(node);
            foreach (int i in initialSet) {
                if (i != node) {
                    Dfs(graph, i, infected);
                }
            }
            if (infected.Count < minInfected) {
                minInfected = infected.Count;
                bestNode = node;
            }
        }
        
        return bestNode;
    }
    
    private void Dfs(int[][] graph, int node, HashSet<int> infected) {
        for (int neighbor = 0; neighbor < graph.Length; neighbor++) {
            if (graph[node][neighbor] == 1 && !infected.Contains(neighbor)) {
                infected.Add(neighbor);
                Dfs(graph, neighbor, infected);
            }
        }
    }
}

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