Задача: 947. Most Stones Removed with Same Row or Column
Сложность: medium

Учитывая массив stones длины n, где stones[i] = [xi, yi] представляет местоположение i-го камня, верните наибольшее возможное количество камней, которые могут быть удалены.

Пример:

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5

👨‍💻 Алгоритм:

1⃣Представить каждую строку и столбец как узлы в графе.

2⃣Создать связи между узлами для камней, которые находятся в той же строке или столбце.
Использовать алгоритм поиска в глубину (DFS) или объединение-поиска (Union-Find), чтобы найти компоненты связности.

3⃣Количество камней, которые могут быть удалены, это общее количество камней минус количество компонентов связности.

😎 Решение:

public class Solution {
    public int RemoveStones(int[][] stones) {
        Dictionary<int, int> parent = new Dictionary<int, int>();
        
        int Find(int x) {
            if (!parent.ContainsKey(x)) parent[x] = x;
            if (parent[x] != x) parent[x] = Find(parent[x]);
            return parent[x];
        }
        
        void Union(int x, int y) {
            parent[Find(x)] = Find(y);
        }
        
        foreach (var stone in stones) {
            Union(stone[0], ~stone[1]);
        }
        
        HashSet<int> uniqueRoots = new HashSet<int>();
        foreach (var key in parent.Keys) {
            uniqueRoots.Add(Find(key));
        }
        
        return stones.Length - uniqueRoots.Count;
    }
}

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

Задача: 867. Transpose Matrix
Сложность: easy

Дан двумерный целочисленный массив matrix, верните его транспонированную матрицу.

Транспонированная матрица — это матрица, перевернутая относительно своей главной диагонали, при этом строки и столбцы меняются местами.

Пример:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[1,4,7],[2,5,8],[3,6,9]]

👨‍💻 Алгоритм:

1⃣Инициализируйте новую матрицу ans с размерами C x R, где C — количество столбцов в исходной матрице, а R — количество строк.

2⃣Скопируйте каждую запись исходной матрицы в новую матрицу так, чтобы ans[c][r] = matrix[r][c].

3⃣Верните матрицу ans.

😎 Решение:

public class Solution {
    public int[][] Transpose(int[][] A) {
        int R = A.Length, C = A[0].Length;
        int[][] ans = new int[C][];
        for (int c = 0; c < C; ++c) {
            ans[c] = new int[R];
            for (int r = 0; r < R; ++r)
                ans[c][r] = A[r][c];
        }
        return ans;
    }
}

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

Задача: 340. Longest Substring with At Most K Distinct Characters
Сложность: medium

Дана строка s и целое число k. Верните длину самой длинной подстроки s, которая содержит не более k различных символов.

Пример:

Input: n = 27
Output: true
Explanation: 27 = 3^3

👨‍💻 Алгоритм:

1⃣Инициализация
Используйте два указателя (left и right) для отслеживания текущего окна в строке. Создайте словарь для отслеживания количества каждого символа в текущем окне. Инициализируйте переменные для хранения максимальной длины подстроки (max_length).

2⃣Раздвижение окна
Перемещайте правый указатель (right) по строке и обновляйте словарь. Если количество различных символов в словаре превышает k, перемещайте левый указатель (left) вправо, уменьшая счетчик символов, пока количество различных символов снова не станет меньше или равно k.

3⃣Обновление максимальной длины
На каждом шаге проверяйте и обновляйте максимальную длину подстроки, если текущее окно содержит не более k различных символов. В конце верните максимальную длину подстроки.

😎 Решение:

public class Solution {
    public int LengthOfLongestSubstringKDistinct(string s, int k) {
        int left = 0;
        int right = 0;
        Dictionary<char, int> charCount = new Dictionary<char, int>();
        int maxLength = 0;
        
        while (right < s.Length) {
            if (!charCount.ContainsKey(s[right])) {
                charCount[s[right]] = 0;
            }
            charCount[s[right]]++;
            
            while (charCount.Count > k) {
                charCount[s[left]]--;
                if (charCount[s[left]] == 0) {
                    charCount.Remove(s[left]);
                }
                left++;
            }
            maxLength = Math.Max(maxLength, right - left + 1);
            right++;
        }
        
        return maxLength;
    }
}

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

Задача: 904. Fruit Into Baskets
Сложность: medium

Вы посещаете ферму, где в один ряд слева направо расположены фруктовые деревья. Деревья представлены целочисленным массивом fruits, где fruits[i] - это тип фрукта, который производит i-е дерево. Вы хотите собрать как можно больше фруктов. Однако у владельца есть строгие правила, которым вы должны следовать: у вас есть только две корзины, и каждая корзина может содержать только один тип фруктов. Количество фруктов в каждой корзине не ограничено. Начиная с любого дерева по вашему выбору, вы должны собрать ровно один фрукт с каждого дерева (включая начальное), двигаясь при этом вправо. Собранные фрукты должны поместиться в одну из ваших корзин. Как только вы достигнете дерева с фруктами, которые не могут поместиться в ваши корзины, вы должны остановиться. Учитывая целочисленный массив fruits, верните максимальное количество фруктов, которое вы можете собрать.

Пример:

Input: fruits = [1,2,1]
Output: 3

👨‍💻 Алгоритм:

1⃣Использовать метод скользящего окна для поддержания текущего подмассива, содержащего не более двух типов фруктов.

2⃣Перемещать правый указатель, расширяя окно, и обновлять количество каждого типа фрукта в окне.
Если количество типов фруктов в окне превышает два, перемещать левый указатель, уменьшая окно, пока в окне снова не будет не более двух типов фруктов.

3⃣Подсчитывать максимальное количество фруктов, собранных на каждом шаге.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int TotalFruit(int[] fruits) {
        var basket = new Dictionary<int, int>();
        int left = 0, maxFruits = 0;

        for (int right = 0; right < fruits.Length; right++) {
            if (!basket.ContainsKey(fruits[right])) {
                basket[fruits[right]] = 0;
            }
            basket[fruits[right]]++;

            while (basket.Count > 2) {
                basket[fruits[left]]--;
                if (basket[fruits[left]] == 0) {
                    basket.Remove(fruits[left]);
                }
                left++;
            }

            maxFruits = Math.Max(maxFruits, right - left + 1);
        }

        return maxFruits;
    }
}

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

Задача: 372. Super Pow
Сложность: medium

Ваша задача — вычислить а^b mod 1337, где a - положительное число, а b - чрезвычайно большое положительное целое число, заданное в виде массива.

Пример:

Input: a = 2, b = [3]
Output: 8

👨‍💻 Алгоритм:

1⃣Разделите задачу на более мелкие задачи: вычислите a^b mod 1337, используя свойства модульной арифметики и степенной функции. Разделите большой показатель b на меньшие части, чтобы обрабатывать их по очереди.

2⃣Используйте метод быстрого возведения в степень (pow) для эффективного вычисления больших степеней с модулем 1337.

3⃣Объедините результаты для каждой части показателя b, используя свойства модульной арифметики: (a^b) % 1337 = ((a^(b1)) % 1337 * (a^(b2)) % 1337 * ...) % 1337.

😎 Решение:

public class Solution {
    public int GetSum(int a, int b) {
        int x = System.Math.Abs(a), y = System.Math.Abs(b);
        if (x < y) return GetSum(b, a);
        int sign = a > 0 ? 1 : -1;

        if (a * b >= 0) {
            while (y != 0) {
                int carry = (x & y) << 1;
                x ^= y;
                y = carry;
            }
        } else {
            while (y != 0) {
                int borrow = ((~x) & y) << 1;
                x ^= y;
                y = borrow;
            }
        }
        return x * sign;
    }
}

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

Задача: 650. 2 Keys Keyboard
Сложность: medium

На экране блокнота есть только один символ 'A'. Для каждого шага можно выполнить одну из двух операций над этим блокнотом: Copy All: скопировать все символы, присутствующие на экране (частичное копирование не допускается). Paste: Вы можете вставить символы, которые были скопированы в прошлый раз. Учитывая целое число n, верните минимальное количество операций, чтобы символ 'A' появился на экране ровно n раз.

Пример:

Input: n = 3
Output: 3

👨‍💻 Алгоритм:

1⃣Используйте динамическое программирование для отслеживания минимального количества операций, необходимых для достижения определенного количества 'A' на экране.

2⃣Итерируйтесь от 1 до n, проверяя все возможные делители текущего числа и обновляя минимальное количество операций для каждого числа.

3⃣Возвращайте значение из таблицы динамического программирования для n.

😎 Решение:

public class Solution {
    public int MinSteps(int n) {
        if (n == 1) return 0;
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            dp[i] = i;
            for (int j = 1; j <= i / 2; j++) {
                if (i % j == 0) {
                    dp[i] = Math.Min(dp[i], dp[j] + i / j);
                }
            }
        }
        return dp[n];
    }
}

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

Задача: 1059. All Paths from Source Lead to Destination
Сложность: medium

Учитывая ребра направленного графа, где edges[i] = [ai, bi] указывает на наличие ребра между вершинами ai и bi, и две вершины source и destination этого графа, определите, все ли пути, начинающиеся из source, заканчиваются в destination, то есть: существует ли хотя бы один путь из source в destination Если существует путь из source в node без исходящих ребер, то этот node равен destination. Количество возможных путей из source в destination - конечное число. Верните true тогда и только тогда, когда все пути из source ведут в destination.

Пример:

Input: n = 3, edges = [[0,1],[0,2]], source = 0, destination = 2
Output: false

👨‍💻 Алгоритм:

1⃣Построение графа и проверка путей:
Построить граф на основе входных данных.
Использовать поиск в глубину (DFS) для проверки наличия всех путей от вершины source до вершины destination.

2⃣Проверка конечности путей:
Проверить, что из всех вершин, достижимых от source, либо исходят ребра, либо они являются вершиной destination.
Убедиться, что из любой вершины, не являющейся destination, исходят хотя бы одно ребро.

3⃣Рекурсивная проверка конечности путей:
Рекурсивно проверять, что все пути из source заканчиваются в destination, избегая циклов и проверяя конечность всех путей.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public bool LeadsToDestination(int n, int[][] edges, int source, int destination) {
        var graph = new Dictionary<int, List<int>>();
        foreach (var edge in edges) {
            if (!graph.ContainsKey(edge[0])) graph[edge[0]] = new List<int>();
            graph[edge[0]].Add(edge[1]);
        }
        
        var visited = new int[n];
        
        return Dfs(graph, visited, source, destination);
    }
    
    private bool Dfs(Dictionary<int, List<int>> graph, int[] visited, int node, int destination) {
        if (visited[node] != 0) return visited[node] == 2;
        if (!graph.ContainsKey(node)) return node == destination;
        visited[node] = 1;
        foreach (var neighbor in graph[node]) {
            if (!Dfs(graph, visited, neighbor, destination)) return false;
        }
        visited[node] = 2;
        return true;
    }
}

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

Задача: 1305. All Elements in Two Binary Search Trees
Сложность: medium

Даны два бинарных дерева поиска root1 и root2. Вернуть список, содержащий все целые числа из обоих деревьев, отсортированные в порядке возрастания.

Пример:

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

👨‍💻 Алгоритм:

1⃣Выполните итеративный обход в порядке возрастания обоих деревьев параллельно.

2⃣На каждом шаге добавляйте наименьшее доступное значение в выходной список.

3⃣Верните выходной список.

😎 Решение:

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public IList<int> GetAllElements(TreeNode root1, TreeNode root2) {
        var stack1 = new Stack<TreeNode>();
        var stack2 = new Stack<TreeNode>();
        var output = new List<int>();

        while (root1 != null || root2 != null || stack1.Count > 0 || stack2.Count > 0) {
            while (root1 != null) {
                stack1.Push(root1);
                root1 = root1.left;
            }
            while (root2 != null) {
                stack2.Push(root2);
                root2 = root2.left;
            }
            if (stack2.Count == 0 || (stack1.Count > 0 && stack1.Peek().val <= stack2.Peek().val)) {
                root1 = stack1.Pop();
                output.Add(root1.val);
                root1 = root1.right;
            } else {
                root2 = stack2.Pop();
                output.Add(root2.val);
                root2 = root2.right;
            }
        }
        return output;
    }
}

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

Задача: 604. Design Compressed String Iterator
Сложность: easy

Разработайте и реализуйте структуру данных для итератора сжатой строки. Данная сжатая строка будет в виде каждой буквы, за которой следует положительное целое число, представляющее количество этой буквы в оригинальной несжатой строке.

Реализуйте класс StringIterator:

- next(): Возвращает следующий символ, если в оригинальной строке еще остались несжатые символы, в противном случае возвращает пробел.
- hasNext(): Возвращает true, если в оригинальной строке остались символы, которые нужно распаковать, в противном случае возвращает false.

Пример:

Input
["StringIterator", "next", "next", "next", "next", "next", "next", "hasNext", "next", "hasNext"]
[["L1e2t1C1o1d1e1"], [], [], [], [], [], [], [], [], []]
Output
[null, "L", "e", "e", "t", "C", "o", true, "d", true]

Explanation
StringIterator stringIterator = new StringIterator("L1e2t1C1o1d1e1");
stringIterator.next(); // return "L"
stringIterator.next(); // return "e"
stringIterator.next(); // return "e"
stringIterator.next(); // return "t"
stringIterator.next(); // return "C"
stringIterator.next(); // return "o"
stringIterator.hasNext(); // return True
stringIterator.next(); // return "d"
stringIterator.hasNext(); // return True

👨‍💻 Алгоритм:

1⃣Предварительная обработка
Мы заранее создаем несжатую строку. Для этого проходим по данному сжатому строковому представлению и добавляем несжатые буквы для каждой сжатой буквы в результирующий строковый строитель res. Чтобы найти количество несжатых букв, мы проходим по данному сжатому строковому представлению. Когда находим букву, определяем следующее за ней число, используя десятичную арифметику. Таким образом, получаем два элемента (букву и количество), необходимые для формирования текущего фрагмента несжатой строки.

2⃣Операция next()
Начинаем с проверки, есть ли еще несжатые буквы в строке. Если нет, hasNext() возвращает False, а next() возвращает пробел (' '). В противном случае возвращаем букву, на которую указывает ptr, указывающий на следующую букву для возврата. Перед возвратом буквы также обновляем ptr, чтобы указывать на следующую букву в res.

3⃣Операция hasNext()
Если указатель ptr выходит за пределы массива res, это указывает на то, что больше несжатых букв нет. В этом случае возвращаем False. В противном случае возвращаем True.

😎 Решение:

public class StringIterator {
    private StringBuilder res = new StringBuilder();
    private int ptr = 0;

    public StringIterator(string s) {
        int i = 0;
        while (i < s.Length) {
            char ch = s[i++];
            int num = 0;
            while (i < s.Length && char.IsDigit(s[i])) {
                num = num * 10 + (s[i] - '0');
                i++;
            }
            for (int j = 0; j < num; j++)
                res.Append(ch);
        }
    }

    public char Next() {
        return !HasNext() ? ' ' : res[ptr++];
    }

    public bool HasNext() {
        return ptr != res.Length;
    }
}

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

Задача: 165. Compare Version Numbers
Сложность: medium

Даны две строки версий, version1 и version2. Сравните их. Строка версии состоит из ревизий, разделенных точками '.'. Значение ревизии — это её целочисленное преобразование с игнорированием ведущих нулей.

Для сравнения строк версий сравнивайте их значения ревизий в порядке слева направо. Если одна из строк версий имеет меньше ревизий, то отсутствующие значения ревизий следует считать равными 0.

Верните следующее:

- Если version1 < version2, верните -1.
- Если version1 > version2, верните 1.
- В противном случае верните 0.

Пример:

Input: version1 = "1.2", version2 = "1.10"
Output: -1
Explanation:
version1's second revision is "2" and version2's second revision is "10": 2 < 10, so version1 < version2.

👨‍💻 Алгоритм:

1⃣Разделение строк: Разделите обе строки по символу точки на два массива.

2⃣Итерация и сравнение: Итерируйте по самому длинному массиву и сравнивайте элементы по одному. Если один из массивов закончился, предполагайте, что все оставшиеся элементы в другом массиве равны нулю, чтобы продолжить сравнение с более длинной строкой.

3⃣Определение результатов сравнения:
Если два сегмента не равны, верните 1 или -1 в зависимости от того, какой сегмент больше.
Если все сегменты равны после завершения цикла, версии считаются равными. Верните 0

😎 Решение:

public class Solution {
    public int CompareVersion(string version1, string version2) {
        string[] nums1 = version1.Split('.');
        string[] nums2 = version2.Split('.');
        int n1 = nums1.Length, n2 = nums2.Length;
        int i1, i2;
        for (int i = 0; i < Math.Max(n1, n2); ++i) {
            i1 = i < n1 ? Int32.Parse(nums1[i]) : 0;
            i2 = i < n2 ? Int32.Parse(nums2[i]) : 0;

            if (i1 != i2)
                return i1 > i2 ? 1 : -1;
        }

        return 0;
    }
}

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

Задача: 350. Intersection of Two Arrays II
Сложность: easy

Даны два целочисленных массива nums1 и nums2. Верните массив их пересечения. Каждый элемент в результате должен появляться столько раз, сколько он встречается в обоих массивах. Вы можете вернуть результат в любом порядке.

Пример:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

👨‍💻 Алгоритм:

1⃣Подсчет частоты элементов:
Используйте хеш-таблицу или словарь для подсчета количества вхождений каждого элемента в nums1.

2⃣Нахождение пересечения:
Пройдите по элементам nums2, и если элемент присутствует в хеш-таблице из шага 1 и его счетчик больше нуля, добавьте этот элемент в результат и уменьшите счетчик.

3⃣Возврат результата:
Верните массив пересечения.

😎 Решение:

public class Solution {
    public int[] Intersect(int[] nums1, int[] nums2) {
        Dictionary<int, int> counts = new Dictionary<int, int>();
        List<int> result = new List<int>();
        
        foreach (int num in nums1) {
            if (counts.ContainsKey(num)) {
                counts[num]++;
            } else {
                counts[num] = 1;
            }
        }
        
        foreach (int num in nums2) {
            if (counts.ContainsKey(num) && counts[num] > 0) {
                result.Add(num);
                counts[num]--;
            }
        }
        
        return result.ToArray();
    }
}

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

Задача: 112. Path Sum
Сложность: easy

Дан корень бинарного дерева и целое число targetSum. Верните true, если в дереве существует путь от корня до листа, такой, что сумма всех значений вдоль пути равна targetSum.

Лист — это узел без детей.

Пример:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.

👨‍💻 Алгоритм:

1⃣Инициализация стека: Начать с помещения в стек корневого узла и соответствующей оставшейся суммы, равной sum - root.val.

2⃣Обработка узлов: Извлечь текущий узел из стека и вернуть True, если оставшаяся сумма равна 0 и узел является листом.

3⃣Добавление дочерних узлов в стек: Если оставшаяся сумма не равна нулю или узел не является листом, добавить в стек дочерние узлы с соответствующими оставшимися суммами.

😎 Решение:

public class Solution {
    public bool HasPathSum(TreeNode root, int sum) {
        if (root == null)
            return false;
        Stack<TreeNode> nodeStack = new Stack<TreeNode>();
        Stack<int> sumStack = new Stack<int>();
        nodeStack.Push(root);
        sumStack.Push(sum - root.val);
        while (nodeStack.Count > 0) {
            TreeNode node = nodeStack.Pop();
            int currSum = sumStack.Pop();
            if (node.left == null && node.right == null && currSum == 0)
                return true;
            if (node.left != null) {
                nodeStack.Push(node.left);
                sumStack.Push(currSum - node.left.val);
            }

            if (node.right != null) {
                nodeStack.Push(node.right);
                sumStack.Push(currSum - node.right.val);
            }
        }

        return false;
    }
}

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

Задача: 246. Strobogrammatic Number
Сложность: easy

Дана строка num, представляющая собой целое число. Верните true, если num является стробограмматическим числом.

Стробограмматическое число — это число, которое выглядит одинаково при повороте на 180 градусов (если посмотреть вверх ногами).

Пример:

Input: num = "69"
Output: true

👨‍💻 Алгоритм:

1⃣Создайте новую строку, перебирая оригинальную строку num в обратном порядке. Для каждого символа проверьте, является ли он допустимым для поворота (0, 1, 6, 8, 9). Если символ недопустим (2, 3, 4, 5, 7), немедленно верните false.

2⃣Для каждого допустимого символа добавьте его соответствующее значение после поворота (0 ⟶ 0, 1 ⟶ 1, 6 ⟶ 9, 8 ⟶ 8, 9 ⟶ 6) в новую строку.

3⃣Сравните полученную строку с исходной строкой num. Если они равны, верните true, в противном случае верните false.

😎 Решение:

using System.Text;

public class Solution {
    public bool IsStrobogrammatic(string num) {
        StringBuilder rotated = new StringBuilder();
        for (int i = num.Length - 1; i >= 0; i--) {
            char c = num[i];
            if (c == '0' || c == '1' || c == '8') {
                rotated.Append(c);
            } else if (c == '6') {
                rotated.Append('9');
            } else if (c == '9') {
                rotated.Append('6');
            } else {
                return false;
            }
        }
        return num == rotated.ToString();
    }
}

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

Задача: 682. Baseball Game
Сложность: medium

Вы ведете учет очков в бейсбольной игре с необычными правилами. В начале игры у вас пустая запись.

Вам дается список строк operations, где operations[i] — это i-я операция, которую вы должны применить к записи, и она может быть одной из следующих:

Целое число x.
Записать новый счет, равный x.
'+'.
Записать новый счет, который является суммой двух предыдущих очков.
'D'.
Записать новый счет, который в два раза больше предыдущего очка.
'C'.
Аннулировать предыдущее очко, удалив его из записи.
Верните сумму всех очков в записи после применения всех операций.

Тестовые случаи сформированы таким образом, что ответ и все промежуточные вычисления умещаются в 32-битное целое число, и что все операции корректны.

Пример:

Input: ops = ["5","2","C","D","+"]
Output: 30
Explanation:
"5" - Add 5 to the record, record is now [5].
"2" - Add 2 to the record, record is now [5, 2].
"C" - Invalidate and remove the previous score, record is now [5].
"D" - Add 2 * 5 = 10 to the record, record is now [5, 10].
"+" - Add 5 + 10 = 15 to the record, record is now [5, 10, 15].
The total sum is 5 + 10 + 15 = 30.

👨‍💻 Алгоритм:

1⃣Поддерживайте значение каждого действительного раунда в стеке при обработке данных. Используйте стек, так как операции касаются только последнего или предпоследнего действительного раунда.

2⃣Обрабатывайте каждую операцию из списка operations последовательно, выполняя соответствующее действие: добавление, суммирование, удвоение или удаление очков.

3⃣После обработки всех операций верните сумму всех значений в стеке.

😎 Решение:

public class Solution {
    public int CalPoints(string[] ops) {
        Stack<int> stack = new Stack<int>();

        foreach (string op in ops) {
            if (op == "+") {
                int top = stack.Pop();
                int newTop = top + stack.Peek();
                stack.Push(top);
                stack.Push(newTop);
            } else if (op == "C") {
                stack.Pop();
            } else if (op == "D") {
                stack.Push(2 * stack.Peek());
            } else {
                stack.Push(int.Parse(op));
            }
        }

        int ans = 0;
        foreach (int score in stack) {
            ans += score;
        }
        return ans;
    }
}

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

Задача: 1319. Number of Operations to Make Network Connected
Сложность: medium

Дано n компьютеров, пронумерованных от 0 до n - 1, соединённых Ethernet-кабелями connections, образующими сеть, где connections[i] = [ai, bi] представляет собой соединение между компьютерами ai и bi. Любой компьютер может достичь любого другого компьютера напрямую или косвенно через сеть.

Вам даны начальные соединения сети. Вы можете извлекать определённые кабели между двумя напрямую соединёнными компьютерами и размещать их между любыми парами несоединённых компьютеров, чтобы сделать их напрямую соединёнными.

Верните минимальное количество раз, которое необходимо сделать это, чтобы соединить все компьютеры. Если это невозможно, верните -1.

Пример:

Input: n = 4, connections = [[0,1],[0,2],[1,2]]
Output: 1
Explanation: Remove cable between computer 1 and 2 and place between computers 1 and 3.

👨‍💻 Алгоритм:

1⃣Проверьте размер connections. Если он меньше n - 1, у нас недостаточно ребер, чтобы соединить весь граф. В этом случае возвращаем -1.

2⃣Создайте список смежности с помощью connections, где adj[x] содержит всех соседей узла x. Создайте целое число numberOfConnectedComponents, которое хранит количество компонент связности в графе. Инициализируйте его значением 0.

3⃣Создайте массив visit длиной n для отслеживания посещенных узлов. Пройдите по всем узлам, и для каждого узла i проверьте, был ли он посещен. Если узел i не был посещен, увеличьте numberOfConnectedComponents на 1 и начните обход DFS:

Используйте функцию dfs для выполнения обхода. Для каждого вызова передавайте узел, ребра и visit в качестве параметров, начиная с узла i.
Отметьте узел как посещенный.
Пройдитесь по всем соседям узла. Если какой-либо сосед еще не был посещен, рекурсивно вызовите dfs с этим соседом в качестве узла.
Верните numberOfConnectedComponents - 1.

😎 Решение:

public class Solution {
    private void Dfs(int node, Dictionary<int, List<int>> adj, bool[] visit) {
        visit[node] = true;
        if (!adj.ContainsKey(node)) {
            return;
        }
        foreach (int neighbor in adj[node]) {
            if (!visit[neighbor]) {
                visit[neighbor] = true;
                Dfs(neighbor, adj, visit);
            }
        }
    }

    public int MakeConnected(int n, int[][] connections) {
        if (connections.Length < n - 1) {
            return -1;
        }

        var adj = new Dictionary<int, List<int>>();
        foreach (var connection in connections) {
            if (!adj.ContainsKey(connection[0])) {
                adj[connection[0]] = new List<int>();
            }
            if (!adj.ContainsKey(connection[1])) {
                adj[connection[1]] = new List<int>();
            }
            adj[connection[0]].Add(connection[1]);
            adj[connection[1]].Add(connection[0]);
        }

        int numberOfConnectedComponents = 0;
        bool[] visit = new bool[n];
        for (int i = 0; i < n; i++) {
            if (!visit[i]) {
                numberOfConnectedComponents++;
                Dfs(i, adj, visit);
            }
        }

        return numberOfConnectedComponents - 1;
    }
}

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

Задача: 1530. Number of Good Leaf Nodes Pairs
Сложность: medium

Вам дан корень бинарного дерева и целое число distance. Пара двух различных листовых узлов бинарного дерева называется хорошей, если длина кратчайшего пути между ними меньше или равна distance.

Верните количество хороших пар листовых узлов в дереве.

Пример:

Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.

👨‍💻 Алгоритм:

1⃣Инициализируйте список смежности для преобразования дерева в граф и множество для хранения листовых узлов. Используйте вспомогательный метод traverseTree для обхода дерева, чтобы построить граф и найти листовые узлы. В параметрах поддерживайте текущий узел, а также родительский узел. Если текущий узел является листом, добавьте его в множество. В списке смежности добавьте текущий узел в список соседей родительского узла и наоборот. Рекурсивно вызовите traverseTree для левого и правого дочернего узла текущего узла.

2⃣Инициализируйте переменную ans для подсчета количества хороших пар листовых узлов. Итеративно переберите каждый листовой узел в множестве. Запустите BFS для текущего листового узла. BFS можно прервать досрочно, как только будут обнаружены все узлы, находящиеся на расстоянии от текущего листового узла. Увеличьте ans для каждого листового узла, найденного в каждом запуске BFS.

3⃣Верните ans / 2. Мы считаем каждую пару дважды, поэтому нужно разделить на 2, чтобы получить фактическое количество.

😎 Решение:

public class Solution {
    public int CountPairs(TreeNode root, int distance) {
        var graph = new Dictionary<TreeNode, List<TreeNode>>();
        var leafNodes = new HashSet<TreeNode>();
        TraverseTree(root, null, graph, leafNodes);
        int ans = 0;
        foreach (var leaf in leafNodes) {
            var bfsQueue = new Queue<TreeNode>();
            var seen = new HashSet<TreeNode>();
            bfsQueue.Enqueue(leaf);
            seen.Add(leaf);
            for (int i = 0; i <= distance; i++) {
                int size = bfsQueue.Count;
                for (int j = 0; j < size; j++) {
                    var currNode = bfsQueue.Dequeue();
                    if (leafNodes.Contains(currNode) && currNode != leaf) {
                        ans++;
                    }
                    if (graph.ContainsKey(currNode)) {
                        foreach (var neighbor in graph[currNode]) {
                            if (!seen.Contains(neighbor)) {
                                bfsQueue.Enqueue(neighbor);
                                seen.Add(neighbor);
                            }
                        }
                    }
                }
            }
        }
        return ans / 2;
    }

    private void TraverseTree(TreeNode currNode, TreeNode prevNode,
                              Dictionary<TreeNode, List<TreeNode>> graph, HashSet<TreeNode> leafNodes) {
        if (currNode == null) {
            return;
        }
        if (currNode.left == null && currNode.right == null) {
            leafNodes.Add(currNode);
        }
        if (prevNode != null) {
            if (!graph.ContainsKey(prevNode)) {
                graph[prevNode] = new List<TreeNode>();
            }
            graph[prevNode].Add(currNode);
            if (!graph.ContainsKey(currNode)) {
                graph[currNode] = new List<TreeNode>();
            }
            graph[currNode].Add(prevNode);
        }
        TraverseTree(currNode.left, currNode, graph, leafNodes);
        TraverseTree(currNode.right, currNode, graph, leafNodes);
    }
}

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

Задача: 269. Alien Dictionary
Сложность: hard

Есть новый инопланетный язык, который использует английский алфавит. Однако порядок букв в нем неизвестен.

Вам дан список строк words из словаря инопланетного языка. Утверждается, что строки в words отсортированы лексикографически по правилам этого нового языка.

Если это утверждение неверно и данное расположение строк в words не может соответствовать никакому порядку букв, верните "".

В противном случае верните строку из уникальных букв нового инопланетного языка, отсортированных в лексикографическом порядке по правилам нового языка. Если существует несколько решений, верните любое из них.

Пример:

Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"

👨‍💻 Алгоритм:

1⃣Извлечение отношений порядка и создание списков смежности:
Извлечь отношения порядка между буквами из слов.
Вставить их в список смежности, обрабатывая случаи, когда одно слово является префиксом другого.

2⃣Подсчет числа входящих ребер:
Подсчитать количество входящих ребер (in-degree) для каждой буквы.
Построить исходящий список смежности и одновременно считать входящие ребра для каждой буквы.

3⃣Обход в ширину (BFS):
Инициализировать очередь буквами с нулевым in-degree.
Выполнять BFS, добавляя буквы в результат, когда их in-degree становится нулевым.
Продолжать до тех пор, пока очередь не станет пустой.
Проверить наличие циклов и вернуть результат.

😎 Решение:

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

public class Solution {
    public string AlienOrder(string[] words) {
        var adjList = new Dictionary<char, HashSet<char>>();
        var inDegree = new Dictionary<char, int>();

        foreach (var word in words) {
            foreach (var c in word) {
                inDegree[c] = 0;
            }
        }

        for (int i = 0; i < words.Length - 1; i++) {
            var firstWord = words[i];
            var secondWord = words[i + 1];
            for (int j =

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

Задача: 961. N-Repeated Element in Size 2N Array
Сложность: easy

Вам дан целочисленный массив nums со следующими свойствами:

nums.length == 2 * n.
nums содержит n + 1 уникальных элементов.
Ровно один элемент массива nums повторяется n раз.
Верните элемент, который повторяется n раз.

Пример:

Input: nums = [1,2,3,3]
Output: 3

👨‍💻 Алгоритм:

1⃣Проверить все подмассивы длиной 4. В таком подмассиве обязательно будет главный элемент, повторяющийся n раз.

2⃣Сравнить элементы массива с их соседями на расстоянии 1, 2 и 3. Если найдется повторяющийся элемент, он и будет искомым.

3⃣Вернуть найденный элемент.

😎 Решение:

public class Solution {
    public int RepeatedNTimes(int[] A) {
        for (int k = 1; k <= 3; ++k) {
            for (int i = 0; i < A.Length - k; ++i) {
                if (A[i] == A[i + k]) {
                    return A[i];
                }
            }
        }
        throw new InvalidOperationException("No solution found");
    }
}

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

Задача: 1023. Camelcase Matching
Сложность: medium

Учитывая массив строк queries и строку pattern, верните булевский массив answer, где answer[i] - true, если queries[i] соответствует pattern, и false в противном случае. Слово запроса queries[i] соответствует pattern, если вы можете вставить строчные английские буквы pattern так, чтобы они были равны запросу. Вы можете вставить каждый символ в любую позицию и не можете вставить ни одного символа.

Пример:

Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB"
Output: [true,false,true,true,false]

👨‍💻 Алгоритм:

1⃣Инициализация переменных:
Создайте массив answer для хранения результатов соответствия каждого запроса шаблону.

2⃣Проверка каждого запроса:
Для каждого запроса из queries, проверьте, можно ли вставить строчные буквы в pattern, чтобы они соответствовали запросу.
Используйте два указателя, один для query и один для pattern. Перемещайте оба указателя, пока они не достигнут конца строк. Если текущие символы совпадают, переместите оба указателя. Если символы не совпадают и текущий символ в запросе является строчной буквой, переместите только указатель запроса.

3⃣Возврат результата:
Если указатель шаблона достиг конца строки, добавьте true в answer, иначе добавьте false.
Верните массив answer.

😎 Решение:

public class Solution {
    public bool[] CamelMatch(string[] queries, string pattern) {
        bool Matches(string query, string pattern) {
            int i = 0, j = 0;
            while (i < query.Length) {
                if (j < pattern.Length && query[i] == pattern[j]) {
                    j++;
                } else if (char.IsUpper(query[i])) {
                    return false;
                }
                i++;
            }
            return j == pattern.Length;
        }
        
        bool[] answer = new bool[queries.Length];
        for (int i = 0; i < queries.Length; i++) {
            answer[i] = Matches(queries[i], pattern);
        }
        
        return answer;
    }
}

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

Задача: 819. Most Common Word
Сложность: easy

Дана строка paragraph и массив строк banned, представляющий запрещенные слова. Верните наиболее часто встречающееся слово, которое не запрещено. Гарантируется, что существует хотя бы одно слово, которое не запрещено, и что ответ является уникальным.

Слова в paragraph нечувствительны к регистру, и ответ должен быть возвращен в нижнем регистре.

Пример:

Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"]
Output: "ball"
Explanation: 
"hit" occurs 3 times, but it is a banned word.
"ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. 
Note that words in the paragraph are not case sensitive,
that punctuation is ignored (even if adjacent to words, such as "ball,"), 
and that "hit" isn't the answer even though it occurs more because it is banned.

👨‍💻 Алгоритм:

1⃣Заменяем всю пунктуацию пробелами и одновременно переводим каждую букву в нижний регистр. Это можно сделать и в два этапа, но здесь мы объединяем их в один этап.

2⃣Разбиваем полученный результат на слова, используя пробелы в качестве разделителей.

3⃣Затем итерируемся по словам, чтобы подсчитать количество появлений каждого уникального слова, исключая слова из списка запрещенных. С помощью хеш-таблицы {слово->количество} проходим по всем элементам, чтобы найти слово с наивысшей частотой.

😎 Решение:

public class Solution {
    public string MostCommonWord(string paragraph, IList<string> banned) {
        string normalizedStr = new string(paragraph.Select(c => char.IsLetterOrDigit(c) ? char.ToLower(c) : ' ').ToArray());
        string[] words = normalizedStr.Split(new[] {' '}, StringSplitOptions.RemoveEmptyEntries);
        var wordCount = new Dictionary<string, int>();
        var bannedWords = new HashSet<string>(banned);

        foreach (string word in words) {
            if (!bannedWords.Contains(word)) {
                if (!wordCount.ContainsKey(word)) {
                    wordCount[word] = 0;
                }
                wordCount[word]++;
            }
        }

        return wordCount.OrderByDescending(kv => kv.Value).First().Key;
    }
}

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

Задача: 1018. Binary Prefix Divisible By 5
Сложность: easy

Вам дан двоичный массив nums (индексированный 0). Мы определяем xi как число, двоичным представлением которого является подмассив nums[0..i] (от старшего бита к младшему). Например, если nums = [1,0,1], то x0 = 1, x1 = 2 и x2 = 5. Верните массив булевых чисел answer, где answer[i] истинно, если xi делится на 5.

Пример:

Input: nums = [0,1,1]
Output: [true,false,false]

👨‍💻 Алгоритм:

1⃣Инициализация и вычисление:
Создайте переменную x для хранения текущего числа в десятичной системе.
Создайте пустой массив answer для хранения результатов делимости на 5.

2⃣Итерация по массиву:
Пройдите по всем элементам массива nums. Для каждого элемента:
Обновите значение x, учитывая текущий бит.
Проверяйте, делится ли x на 5, и добавьте результат (true или false) в массив answer.
Чтобы избежать переполнения, используйте модуль 5 для переменной x.

3⃣Возврат результата:
Верните массив answer с результатами проверки делимости на 5.

😎 Решение:

public class Solution {
    public bool[] PrefixesDivBy5(int[] nums) {
        int x = 0;
        bool[] answer = new bool[nums.Length];
        for (int i = 0; i < nums.Length; i++) {
            x = (x * 2 + nums[i]) % 5;
            answer[i] = x == 0;
        }
        return answer;
    }
}

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