C# | LeetCode

#easy Задача: 290. Word Pattern Дан шаблон и строка s, необходимо определить, следует ли строка s этому шаблону. Здесь "следует" означает полное соответствие, такое что существует биекция между буквой в шаблоне и непустым словом в строке s. Пример:

Input: pattern = "abba", s = "dog cat cat dog"
Output: true

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

using System;
using System.Collections.Generic;

public class Solution {
    public bool WordPattern(string pattern, string s) {
        var mapChar = new Dictionary<char, string>();
        var mapWord = new Dictionary<string, char>();
        var words = s.Split(" ");

        if (words.Length != pattern.Length) {
            return false;
        }

        for (int i = 0; i < pattern.Length; i++) {
            char c = pattern[i];
            string w = words[i];
            if (!mapChar.ContainsKey(c)) {
                if (mapWord.ContainsKey(w)) {
                    return false;
                } else {
                    mapChar[c] = w;
                    mapWord[w] = c;
                }
            } else {
                if (mapChar[c] != w) {
                    return false;
                }
            }
        }

        return true;
    }
}

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

#easy Задача: 292. Nim Game Вы играете в следующую игру Nim со своим другом: Изначально на столе лежит куча камней. Вы и ваш друг поочередно делаете ходы, и вы ходите первым. Каждый ход игрок, чей ход, будет убирать от 1 до 3 камней из кучи. Тот, кто убирает последний камень, становится победителем. Дано n, количество камней в куче. Верните true, если вы можете выиграть игру, предполагая, что и вы, и ваш друг играете оптимально, иначе верните false. Пример:

Input: n = 4
Output: false
Explanation: These are the possible outcomes:
1. You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins.
2. You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins.
3. You remove 3 stones. Your friend removes the last stone. Your friend wins.
In all outcomes, your friend wins.

👨‍💻 Алгоритм: 1⃣Определите базовый случай: Если количество камней n меньше или равно 3, вы всегда можете выиграть, убрав все камни. В этом случае верните true. 2⃣Анализ оставшихся камней: Если количество камней n делится на 4 без остатка (n % 4 == 0), вы не можете выиграть, так как независимо от вашего хода ваш друг всегда сможет оставить вам кратное 4 количество камней. В этом случае верните false. 3⃣Выигрышная стратегия: Если количество камней n не кратно 4 (n % 4 != 0), вы можете выиграть, оставляя вашему другу кратное 4 количество камней после вашего хода. В этом случае верните true. 😎 Решение:

public class Solution {
    public bool CanWinNim(int n) {
        return n % 4 != 0;
    }
}

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

#medium Задача: 294. Flip Game II Вы играете в игру Flip со своим другом. Вам дана строка currentState, которая содержит только символы '+' и '-'. Вы и ваш друг по очереди переворачиваете две последовательные "++" в "--". Игра заканчивается, когда игрок больше не может сделать ход, и, следовательно, другой игрок становится победителем. Верните true, если начальный игрок может гарантировать победу, и false в противном случае. Пример:

Input: currentState = "++++"
Output: true
Explanation: The starting player can guarantee a win by flipping the middle "++" to become "+--+".

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

public class Solution {
    public bool CanWin(string currentState) {
        char[] stateArray = currentState.ToCharArray();
        
        for (int i = 0; i < stateArray.Length - 1; i++) {
            if (stateArray[i] == '+' && stateArray[i + 1] == '+') {
                stateArray[i] = '-';
                stateArray[i + 1] = '-';
                string newState = new string(stateArray);
                
                if (!CanWin(newState)) {
                    stateArray[i] = '+';
                    stateArray[i + 1] = '+';
                    return true;
                }
                
                stateArray[i] = '+';
                stateArray[i + 1] = '+';
            }
        }
        
        return false;
    }
}

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

#hard Задача: 295. Find Median from Data Stream Медиана — это среднее значение в упорядоченном списке целых чисел. Если размер списка четный, то медианы нет, и медиана — это среднее арифметическое двух средних значений. Например, для arr = [2, 3, 4] медиана равна 3. Например, для arr = [2, 3] медиана равна (2 + 3) / 2 = 2.5. Реализуйте класс MedianFinder: MedianFinder() инициализирует объект MedianFinder. void addNum(int num) добавляет целое число num из потока данных в структуру данных. double findMedian() возвращает медиану всех элементов на данный момент. Ответы с точностью до 10^-5 от фактического ответа будут приниматься. Пример:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

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

using System;
using System.Collections.Generic;

public class MedianFinder {
    private List<int> numbers;

    public MedianFinder() {
        numbers = new List<int>();
    }

    public void AddNum(int num) {
        numbers.Add(num);
    }

    public double FindMedian() {
        numbers.Sort();
        int n = numbers.Count;
        if (n % 2 == 0) {
            return (numbers[n / 2 - 1] + numbers[n / 2]) / 2.0;
        } else {
            return numbers[n / 2];
        }
    }
}

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

#hard Задача: 296. Best Meeting Point Дан бинарный сетка размером m x n, где каждая 1 обозначает дом одного друга. Верните минимальное общее расстояние путешествия. Общее расстояние путешествия — это сумма расстояний между домами друзей и точкой встречи. Расстояние рассчитывается по Манхэттенскому расстоянию, где distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|. Пример:

Input: grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 6
Explanation: Given three friends living at (0,0), (0,4), and (2,2).
The point (0,2) is an ideal meeting point, as the total travel distance of 2 + 2 + 2 = 6 is minimal.
So return 6.

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

using System;
using System.Collections.Generic;

public class Solution {
    public int MinTotalDistance(int[][] grid) {
        int minDistance = int.MaxValue;
        for (int row = 0; row < grid.Length; row++) {
            for (int col = 0; col < grid[0].Length; col++) {
                int distance = Search(grid, row, col);
                minDistance = Math.Min(distance, minDistance);
            }
        }
        return minDistance;
    }

    private int Search(int[][] grid, int row, int col) {
        Queue<Tuple<int, int, int>> q = new Queue<Tuple<int, int, int>>();
        q.Enqueue(Tuple.Create(row, col, 0));
        int m = grid.Length;
        int n = grid[0].Length;
        bool[][] visited = new bool[m][];
        for (int i = 0; i < m; i++) {
            visited[i] = new bool[n];
        }
        int totalDistance = 0;

        while (q.Count > 0) {
            var point = q.Dequeue();
            int r = point.Item1;
            int c = point.Item2;
            int d = point.Item3;

            if (r < 0 || c < 0 || r >= m || c >= n || visited[r][c]) {
                continue;
            }

            if (grid[r][c] == 1) {
                totalDistance += d;
            }

            visited[r][c] = true;

            q.Enqueue(Tuple.Create(r + 1, c, d + 1));
            q.Enqueue(Tuple.Create(r - 1, c, d + 1));
            q.Enqueue(Tuple.Create(r, c + 1, d + 1));
            q.Enqueue(Tuple.Create(r, c - 1, d + 1));
        }

        return totalDistance;
    }
}

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

#hard Задача: 297. Serialize and Deserialize Binary Tree Сериализация — это процесс преобразования структуры данных или объекта в последовательность битов, чтобы их можно было сохранить в файле или буфере памяти или передать по сетевому соединению для последующего восстановления в той же или другой компьютерной среде. Разработайте алгоритм для сериализации и десериализации бинарного дерева. Нет ограничений на то, как ваш алгоритм сериализации/десериализации должен работать. Вам нужно просто гарантировать, что бинарное дерево может быть сериализовано в строку, и эта строка может быть десериализована в исходную структуру дерева. Уточнение: формат ввода/вывода такой же, как в LeetCode для сериализации бинарного дерева. Вам не обязательно придерживаться этого формата, так что будьте креативны и придумайте свои подходы. Пример:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

👨‍💻 Алгоритм: 1⃣Сериализация дерева: Используйте рекурсивный обход дерева в порядке root -> left subtree -> right subtree. Для каждого узла добавляйте его значение в строку сериализации. Если узел пустой, добавляйте "None". 2⃣Пример: Начните с корня, узел 1, строка сериализации становится "1,". Переходите к левому поддереву с корнем 2, строка сериализации становится "1,2,". Для узла 2, посетите его левый узел 3 ("1,2,3,None,None,") и правый узел 4 ("1,2,3,None,None,4,None,None"). Возвращайтесь к корню 1 и посетите его правое поддерево, узел 5 ("1,2,3,None,None,4,None,None,5,None,None,"). 3⃣Десериализация строки: Разделите строку на список значений. Используйте рекурсивную функцию для создания узлов дерева, извлекая значения из списка и восстанавливая структуру дерева. Если значение "None", узел пустой. 😎 Решение:

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 Codec {
    private void Rserialize(TreeNode root, StringBuilder str) {
        if (root == null) {
            str.Append("null,");
        } else {
            str.Append(root.val).Append(",");
            Rserialize(root.left, str);
            Rserialize(root.right, str);
        }
    }

    public string Serialize(TreeNode root) {
        StringBuilder str = new StringBuilder();
        Rserialize(root, str);
        return str.ToString();
    }

    private TreeNode Rdeserialize(Queue<string> data) {
        if (data.Peek() == "null") {
            data.Dequeue();
            return null;
        }

        TreeNode root = new TreeNode(int.Parse(data.Dequeue()));
        root.left = Rdeserialize(data);
        root.right = Rdeserialize(data);
        return root;
    }

    public TreeNode Deserialize(string data) {
        Queue<string> dataArray = new Queue<string>(data.Split(','));
        return Rdeserialize(dataArray);
    }
}

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

🥰 Как улучшить свой код 🥰 Настрой среду, в которой ты работаешь! 🥰 Многие программисты пишут код на настройках по умолчанию - ошибка. 🥰 Не подключают плагины, которые ускорят работу и увеличат эффективность - фатальная ошибка. 👩‍💻 Канал Visual Studio Сode | Плагины сделает твою рабочую среду универсальным и мощным инструментом. 🥰 Повышай свою эффективность и подписывайся на канал Visual Studio Сode | Плагины

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать #реклама yandex.ru О рекламодателе

#medium Задача: 433. Minimum Genetic Mutation Генетическая строка может быть представлена строкой длиной 8 символов, содержащей символы 'A', 'C', 'G' и 'T'. Предположим, нам нужно исследовать мутацию от генетической строки startGene до генетической строки endGene, где одна мутация определяется как изменение одного символа в генетической строке. Например, "AACCGGTT" --> "AACCGGTA" является одной мутацией. Также существует генетический банк bank, который содержит все допустимые генетические мутации. Генетическая строка должна быть в банке, чтобы считаться допустимой. Даны две генетические строки startGene и endGene и генетический банк bank, верните минимальное количество мутаций, необходимых для мутации от startGene до endGene. Если такой мутации не существует, верните -1. Обратите внимание, что начальная строка считается допустимой, поэтому она может не быть включена в банк. Пример:

Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1

👨‍💻 Алгоритм: 1⃣Инициализируйте очередь и множество seen. Очередь будет использоваться для выполнения BFS, а множество seen будет использоваться для предотвращения повторного посещения одного и того же узла. Изначально в очередь и множество должен быть помещен startGene. 2⃣Выполняйте BFS. На каждом узле, если node == endGene, верните количество шагов, пройденных до этого момента. В противном случае, итеративно заменяйте каждый символ в строке на один из "A", "C", "G", "T" для нахождения соседей. Для каждого соседа, если он еще не был посещен и находится в bank, добавьте его в очередь и в множество seen. 3⃣Если BFS завершился и endGene не был найден, задача невыполнима. Верните -1. 😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int MinMutation(string start, string end, string[] bank) {
        Queue<string> queue = new Queue<string>();
        HashSet<string> seen = new HashSet<string>();
        queue.Enqueue(start);
        seen.Add(start);
        
        int steps = 0;
        while (queue.Count > 0) {
            int nodesInQueue = queue.Count;
            
            for (int j = 0; j < nodesInQueue; j++) {
                string node = queue.Dequeue();
                
                if (node == end) {
                    return steps;
                }
                
                foreach (char c in "ACGT") {
                    for (int i = 0; i < node.Length; i++) {
                        char[] neighborArray = node.ToCharArray();
                        neighborArray[i] = c;
                        string neighbor = new string(neighborArray);
                        if (!seen.Contains(neighbor) && Array.Exists(bank, b => b == neighbor)) {
                            queue.Enqueue(neighbor);
                            seen.Add(neighbor);
                        }
                    }
                }
            }
            
            steps++;
        }
        
        return -1;
    }
}

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

⚡️ IT-обучение теперь в Telegram! В cвязи с недавнем замедлением Ютуба — лучшие обучающие каналы переехали в Telegram Вот каналы для айтишников: 👩‍💻 C#: @Csharp 👩‍💻 С/С++: @Cpp 👩‍💻 Разработка игр: @GameDev 📱 GitHub: @GitHub ⚙️ Backend: @Backend 🤓 Общее айти: @portalToIT 👩‍💻 Python: @Python 👩‍💻 Frontend: @Frontend 👩‍💻 Java: @Java 🖥 Базы Данных & SQL: @SQL 👩‍💻 Golang: @Golang 👩‍💻 PHP: @PHP 👩‍💻 Моб. разработка: @MobDev 👩‍💻 DevOps: @DevOps 🖥 Data Science: @DataScience 🤔 Хакинг & ИБ: @InfoSec 🐞 Тестирование: @QA 📱 Маркетинг: @Marketing 🖥 Дизайн: @Design ➡️ Сохраняйте себе, чтобы не потерять

#medium Задача: 298. Binary Tree Longest Consecutive Sequence Дан корень бинарного дерева, верните длину самого длинного пути последовательных значений. Путь последовательных значений — это путь, где значения увеличиваются на единицу вдоль пути. Обратите внимание, что путь может начинаться с любого узла в дереве, и вы не можете перейти от узла к его родителю на пути. Пример:

Input: root = [1,null,3,2,4,null,null,null,5]
Output: 3
Explanation: Longest consecutive sequence path is 3-4-5, so return 3.

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

public class Solution {
    private int maxLength = 0;

    public int LongestConsecutive(TreeNode root) {
        Dfs(root, null, 0);
        return maxLength;
    }

    private void Dfs(TreeNode node, TreeNode parent, int length) {
        if (node == null) return;
        if (parent != null && node.val == parent.val + 1) {
            length++;
        } else {
            length = 1;
        }
        maxLength = Math.Max(maxLength, length);
        Dfs(node.left, node, length);
        Dfs(node.right, node, length);
    }
}

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

#medium Задача: 299. Bulls and Cows Вы играете в игру "Быки и коровы" со своим другом. Вы записываете секретное число и просите своего друга угадать, что это за число. Когда ваш друг делает предположение, вы даете ему подсказку со следующей информацией: Количество "быков", то есть цифры в предположении, которые находятся на правильной позиции. Количество "коров", то есть цифры в предположении, которые есть в вашем секретном числе, но находятся на неправильной позиции. Конкретно, это не-бычьи цифры в предположении, которые можно переставить так, чтобы они стали быками. Дано секретное число secret и предположение вашего друга guess, верните подсказку для предположения вашего друга. Подсказка должна быть в формате "xAyB", где x — количество быков, а y — количество коров. Обратите внимание, что и secret, и guess могут содержать повторяющиеся цифры. Пример:

Input: secret = "1807", guess = "7810"
Output: "1A3B"
Explanation: Bulls are connected with a '|' and cows are underlined:
"1807"
  |
"7810"

👨‍💻 Алгоритм: 1⃣Инициализация счетчиков: Инициализируйте количество быков и коров значениями ноль. Создайте хеш-таблицу для хранения символов строки secret и их частот. 2⃣Обход строки guess: Для каждого символа ch в строке guess: Если ch присутствует в строке secret: Если текущий символ ch совпадает с символом на той же позиции в secret (ch == secret[idx]): Увеличьте количество быков: bulls += 1. Обновите количество коров, если количество текущего символа в хеш-таблице отрицательное или равно нулю (то есть этот символ уже использовался для коров): cows -= int(h[ch] <= 0). Если текущий символ ch не совпадает с символом на той же позиции в secret (ch != secret[idx]): Увеличьте количество коров, если количество текущего символа в хеш-таблице больше нуля: cows += int(h[ch] > 0). Обновите хеш-таблицу, помечая текущий символ как использованный: h[ch] -= 1. 3⃣Возврат результата: Верните количество быков и коров в формате "xAyB". 😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public string GetHint(string secret, string guess) {
        var h = new Dictionary<char, int>();
        foreach (var ch in secret) {
            if (!h.ContainsKey(ch)) {
                h[ch] = 0;
            }
            h[ch]++;
        }

        int bulls = 0;
        int cows = 0;
        int n = guess.Length;
        var secretArray = secret.ToCharArray();
        var guessArray = guess.ToCharArray();

        for (int idx = 0; idx < n; idx++) {
            var ch = guessArray[idx];
            if (h.ContainsKey(ch)) {
                if (ch == secretArray[idx]) {
                    bulls++;
                    if (h[ch] <= 0) {
                        cows--;
                    }
                } else {
                    if (h[ch] > 0) {
                        cows++;
                    }
                }
                h[ch]--;
            }
        }

        return $"{bulls}A{cows}B";
    }
}

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

Senior-разработчик создал крутейший канал про SQL Благодаря простым картинкам даже новичок научится разрабатывать приложения с использованием баз данных. Присоединяйтесь: @SQL

#medium Задача: 300. Longest Increasing Subsequence Дан массив целых чисел nums, верните длину самой длинной строго возрастающей подпоследовательности. Пример:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

👨‍💻 Алгоритм: 1⃣Инициализируйте массив dp длиной nums.length, все элементы которого равны 1. dp[i] представляет длину самой длинной возрастающей подпоследовательности, которая заканчивается элементом с индексом i. 2⃣Итерируйтесь от i = 1 до i = nums.length - 1. В каждой итерации используйте второй цикл for для итерации от j = 0 до j = i - 1 (все элементы перед i). Для каждого элемента перед i, проверьте, меньше ли этот элемент, чем nums[i]. Если да, установите dp[i] = max(dp[i], dp[j] + 1). 3⃣Верните максимальное значение из dp. 😎 Решение:

using System;
using System.Linq;

public class Solution {
    public int LengthOfLIS(int[] nums) {
        if (nums.Length == 0) return 0;

        int[] dp = new int[nums.Length];
        Array.Fill(dp, 1);

        for (int i = 1; i < nums.Length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.Max(dp[i], dp[j] + 1);
                }
            }
        }

        return dp.Max();
    }

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

🔥 Ресурсы для подготовки к работе в IT! 🔥 1️⃣ База собеседований IT – это уникальная коллекция собеседований от реальных топовых компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и многие другие! 🏢 Мы собрали 150+ собеседований, чтобы ты мог подготовиться к интервью с уверенностью и успехом. 2️⃣ База тестовых заданий – твоё секретное оружие для успешного прохождения этапов отбора! 📋 Здесь ты найдёшь 121+ тестовых заданий от тех же топовых компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries. Решай реальные задачи и набирайся опыта для будущих собеседований! 🎯 Присоединяйся к базам и прокачай свои шансы на успешное трудоустройство!

#medium Задача: 395. Longest Substring with At Least K Repeating Characters Дана строка s и целое число k, верните длину самой длинной подстроки строки s, такая что частота каждого символа в этой подстроке больше или равна k. Если такой подстроки не существует, верните 0. Пример:

Input: s = "aaabb", k = 3
Output: 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.

👨‍💻 Алгоритм: 1⃣Генерируйте подстроки из строки s, начиная с индекса start и заканчивая индексом end. Используйте массив countMap для хранения частоты каждого символа в подстроке. 2⃣Метод isValid использует countMap для проверки, что каждый символ в подстроке встречается как минимум k раз. Если условие выполняется, текущая подстрока считается допустимой. 3⃣Отслеживайте максимальную длину допустимой подстроки, обновляя её, когда найдена более длинная подстрока, удовлетворяющая условиям. В конце возвращайте длину самой длинной подстроки. 😎 Решение:

public class Solution {
    public int LongestSubstring(string s, int k) {
        if (s.Length == 0 || k > s.Length) {
            return 0;
        }
        int[] countMap = new int[26];
        int n = s.Length;
        int result = 0;
        
        for (int start = 0; start < n; start++) {
            Array.Fill(countMap, 0);
            for (int end = start; end < n; end++) {
                countMap[s[end] - 'a']++;
                if (IsValid(countMap, k)) {
                    result = Math.Max(result, end - start + 1);
                }
            }
        }
        return result;
    }

    private bool IsValid(int[] countMap, int k) {
        int countLetters = 0, countAtLeastK = 0;
        for (int i = 0; i < 26; i++) {
            if (countMap[i] > 0) countLetters++;
            if (countMap[i] >= k) countAtLeastK++;
        }
        return countLetters == countAtLeastK;
    }
}

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

CodHub теперь в Telegram! Бесплатные обучающие материалы, которые лучше платных — книги, ресурсы, статьи и курсы топовых вузов страны тут: 👩‍💻 Материалы по Python 👩‍💻 Материалы по Frontend 👩‍💻 Материалы по Java 👩‍💻 Материалы по С# 👩‍💻 Материалы по C/C++ 👩‍💻 Материалы по Хакингу 🖥 Материалы по SQL 👩‍💻 Материалы по Kotlin/Swift 👩‍💻 Материалы по Linux 🐞 Материалы по QA 👩‍💻 Материалы по Go 👩‍💻 Материалы по PHP Подписываетесь: @CodHub_tg

#hard Задача: 301. Remove Invalid Parentheses Дана строка s, содержащая скобки и буквы. Удалите минимальное количество неверных скобок, чтобы сделать строку допустимой. Верните список уникальных строк, которые являются допустимыми с минимальным количеством удалений. Вы можете вернуть ответ в любом порядке. Пример:

Input: s = "()())()"
Output: ["(())()","()()()"]

👨‍💻 Алгоритм: 1⃣Инициализация: Инициализируйте массив, который будет хранить все допустимые выражения. Начните рекурсию с самой левой скобки в последовательности и двигайтесь вправо. Определите состояние рекурсии переменной index, представляющей текущий обрабатываемый индекс в исходном выражении. Также используйте переменные left_count и right_count для отслеживания количества добавленных левых и правых скобок соответственно. 2⃣Обработка текущего символа: Если текущий символ (S[i]) не является скобкой, добавьте его к окончательному решению для текущей рекурсии. Если текущий символ является скобкой (S[i] == '(' или S[i] == ')'), у вас есть два варианта: либо отбросить этот символ как недопустимый, либо рассмотреть эту скобку как часть окончательного выражения. 3⃣Завершение рекурсии и проверка: Когда все скобки в исходном выражении обработаны, проверьте, является ли текущее выражение допустимым, проверяя значения left_count и right_count (должны быть равны). Если выражение допустимо, проверьте количество удалений (rem_count) и сравните его с минимальным количеством удалений, необходимых для получения допустимого выражения до сих пор. Если текущее значение rem_count меньше, обновите глобальный минимум и добавьте новое выражение в массив допустимых выражений. 😎 Решение:

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

public class Solution {
    private HashSet<string> validExpressions = new HashSet<string>();
    private int minimumRemoved = int.MaxValue;

    private void Reset() {
        validExpressions.Clear();
        minimumRemoved = int.MaxValue;
    }

    private void Recurse(string s, int index, int leftCount, int rightCount, StringBuilder expression, int removedCount) {
        if (index == s.Length) {
            if (leftCount == rightCount) {
                if (removedCount <= minimumRemoved) {
                    string possibleAnswer = expression.ToString();
                    if (removedCount < minimumRemoved) {
                        validExpressions.Clear();
                        minimumRemoved = removedCount;
                    }
                    validExpressions.Add(possibleAnswer);
                }
            }
            return;
        }

        char currentCharacter = s[index];
        int length = expression.Length;

        if (currentCharacter != '(' && currentCharacter != ')') {
            expression.Append(currentCharacter);
            Recurse(s, index + 1, leftCount, rightCount, expression, removedCount);
            expression.Length = length;
        } else {
            Recurse(s, index + 1, leftCount, rightCount, expression, removedCount + 1);
            expression.Append(currentCharacter);

            if (currentCharacter == '(') {
                Recurse(s, index + 1, leftCount + 1, rightCount, expression, removedCount);
            } else if (rightCount < leftCount) {
                Recurse(s, index + 1, leftCount, rightCount + 1, expression, removedCount);
            }

            expression.Length = length;
        }
    }

    public IList<string> RemoveInvalidParentheses(string s) {
        Reset();
        Recurse(s, 0, 0, 0, new StringBuilder(), 0);
        return new List<string>(validExpressions);
    }

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

#medium Задача: 280. Wiggle Sort Дан целочисленный массив nums, упорядочьте его так, чтобы nums[0] <= nums[1] >= nums[2] <= nums[3].... Вы можете считать, что входной массив всегда имеет допустимый ответ. Пример:

Input: nums = [3,5,2,1,6,4]
Output: [3,5,1,6,2,4]
Explanation: [1,6,2,5,3,4] is also accepted.

👨‍💻 Алгоритм: 1⃣Итерируйтесь по каждому элементу с индексом i в массиве nums, начиная с 0 и до nums.length - 2, так как последний элемент не имеет следующего элемента для обмена. 2⃣Проверьте, является ли i четным и nums[i] > nums[i + 1]. Если это так, поменяйте местами nums[i] и nums[i + 1]. 3⃣Проверьте, является ли i нечетным и nums[i] < nums[i + 1]. Если это так, поменяйте местами nums[i] и nums[i + 1]. 😎 Решение:

public class Solution {
    private void Swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void WiggleSort(int[] nums) {
        for (int i = 0; i < nums.Length - 1; i++) {
            if ((i % 2 == 0 && nums[i] > nums[i + 1]) || (i % 2 == 1 && nums[i] < nums[i + 1])) {
                Swap(nums, i, i + 1);
            }
        }
    }
}

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