C# | LeetCode

Бесплатный курс по дизайну в FIGMA Онлайн-программа с наставником и чатом. Осторожно! 80% практики. По результату обучения у вас будет портфолио из нескольких работ. Сертификат о прохождении курса. Возможность пройти полное обучение и получить гарантированное трудоустройство! Учитесь дизайну у профессионалов. Переходи по кнопки: "Узнать больше" и начинай свое обучение. Доступ 0 руб. Узнать больше #реклама 16+ yudaevschool24.online О рекламодателе

#medium Задача: 737. Sentence Similarity II Мы можем представить предложение в виде массива слов, например, предложение "I am happy with leetcode" можно представить как arr = ["I", "am",happy", "with", "leetcode"]. Даны два предложения sentence1 и sentence2, каждое из которых представлено в виде массива строк, и массив пар строк similarPairs, где similarPairs[i] = [xi, yi] указывает, что два слова xi и yi похожи. Возвращается true, если предложения sentence1 и sentence2 похожи, или false, если они не похожи. Два предложения похожи, если: у них одинаковая длина (т.е, Заметьте, что слово всегда похоже само на себя, также обратите внимание, что отношение сходства является транзитивным. Например, если слова a и b похожи, а слова b и c похожи, то a и c похожи. Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","good"],["fine","good"],["drama","acting"],["skills","talent"]]
Output: true

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

using System;
using System.Collections.Generic;

public class Solution {
    public bool AreSentencesSimilar(string[] sentence1, string[] sentence2, IList<IList<string>> similarPairs) {
        if (sentence1.Length != sentence2.Length) {
            return false;
        }

        var graph = new Dictionary<string, List<string>>();
        foreach (var pair in similarPairs) {
            if (!graph.ContainsKey(pair[0])) graph[pair[0]] = new List<string>();
            if (!graph.ContainsKey(pair[1])) graph[pair[1]] = new List<string>();
            graph[pair[0]].Add(pair[1]);
            graph[pair[1]].Add(pair[0]);
        }

        for (int i = 0; i < sentence1.Length; i++) {
            if (sentence1[i] != sentence2[i] && !dfs(sentence1[i], sentence2[i], graph, new HashSet<string>())) {
                return false;
            }
        }

        return true;
    }

    private bool dfs(string word1, string word2, Dictionary<string, List<string>> graph, HashSet<string> visited) {
        if (word1 == word2) {
            return true;
        }
        visited.Add(word1);
        foreach (var neighbor in graph.GetValueOrDefault(word1, new List<string>())) {
            if (!visited.Contains(neighbor) && dfs(neighbor, word2, graph, visited)) {
                return true;
            }
        }
        return false;
    }
}

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

Крупнейший университет искусственного интеллекта Учим использовать ChatGPT в профессиональных целях, создавать нейро-сотрудников и зарабатывать на искусственном интеллекте. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя в наших рядах! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

#hard Задача: 736. Parse Lisp Expression Нам дан массив asteroids, состоящий из целых чисел, представляющих астероиды в ряд. Для каждого астероида абсолютное значение обозначает его размер, а знак - направление движения (положительное - вправо, отрицательное - влево). Каждый астероид движется с одинаковой скоростью. Определите состояние астероидов после всех столкновений. Если два астероида столкнутся, меньший из них взорвется. Если оба одинакового размера, то взорвутся оба. Два астероида, движущиеся в одном направлении, никогда не встретятся. Пример:

Input: expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"
Output: 14

👨‍💻 Алгоритм: 1⃣Определите функцию для оценки выражений. 2⃣Используйте рекурсивный подход для обработки различных типов выражений (let, add, mult, и переменных). 3⃣Используйте словарь для отслеживания значений переменных с учетом области видимости. 😎 Решение:

public class Solution {
    public int Evaluate(string expression) {
        return Evaluate(expression, new Dictionary<string, int>());
    }
    
    private int Evaluate(string expression, Dictionary<string, int> env) {
        if (expression[0] != '(') {
            return int.TryParse(expression, out var result) ? result : env[expression];
        }
        
        var tokens = Tokenize(expression);
        if (tokens[0] == "let") {
            for (int i = 1; i < tokens.Count - 2; i += 2) {
                env[tokens[i]] = Evaluate(tokens[i + 1], env);
            }
            return Evaluate(tokens[^1], env);
        } else if (tokens[0] == "add") {
            return Evaluate(tokens[1], env) + Evaluate(tokens[2], env);
        } else if (tokens[0] == "mult") {
            return Evaluate(tokens[1], env) * Evaluate(tokens[2], env);
        }
        return 0;
    }
    
    private List<string> Tokenize(string expression) {
        var tokens = new List<string>();
        var token = string.Empty;
        int parens = 0;
        foreach (var c in expression) {
            if (c == '(') {
                parens++;
                if (parens == 1) continue;
            } else if (c == ')') {
                parens--;
                if (parens == 0) {
                    tokens.AddRange(Tokenize(token));
                    token = string.Empty;
                    continue;
                }
            } else if (c == ' ' && parens == 1) {
                if (!string.IsNullOrEmpty(token)) {
                    tokens.Add(token);
                    token = string.Empty;
                }
                continue;
            }
            token += c;
        }
        if (!string.IsNullOrEmpty(token)) {
            tokens.Add(token);
        }
        return tokens;
    }
}

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

Думаете, что IT — это сложно? Докажем обратное! Пройдите тест, узнайте, какая роль в IT вам подходит, и получите доступ к мини-курсу. 📱5 уроков в Telegram-боте — легко, увлекательно и бесплатно. ✨Подарки в конце пути ✅Пройдите тест и откройте курс Начать #реклама 16+ free.skillfactory.ru О рекламодателе

#medium Задача: 735. Asteroid Collision Нам дан массив asteroids, состоящий из целых чисел, представляющих астероиды в ряд. Для каждого астероида абсолютное значение обозначает его размер, а знак - направление движения (положительное - вправо, отрицательное - влево). Каждый астероид движется с одинаковой скоростью. Определите состояние астероидов после всех столкновений. Если два астероида столкнутся, меньший из них взорвется. Если оба одинакового размера, то взорвутся оба. Два астероида, движущиеся в одном направлении, никогда не встретятся. Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","fine"],["drama","acting"],["skills","talent"]]
Output: true

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

using System;
using System.Collections.Generic;

public class Solution {
    public int[] AsteroidCollision(int[] asteroids) {
        Stack<int> stack = new Stack<int>();
        
        foreach (int asteroid in asteroids) {
            bool alive = true;
            while (alive && asteroid < 0 && stack.Count > 0 && stack.Peek() > 0) {
                int last = stack.Pop();
                if (last == -asteroid) {
                    alive = false;
                } else if (last > -asteroid) {
                    stack.Push(last);
                    alive = false;
                }
            }
            if (alive) {
                stack.Push(asteroid);
            }
        }
        
        int[] result = new int[stack.Count];
        for (int i = result.Length - 1; i >= 0; i--) {
            result[i] = stack.Pop();
        }
        
        return result;
    }
}

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

Как синхронизировать команду? Пригласить в Битрикс24. Бесплатный онлайн-сервис для бизнеса и совместной работы. Мессенджер, CRM для продаж, Видеозвонки, Задачи, Календарь, Файлы и ИИ-помощник. Заберите бесплатно 10+ инструментов в одном сервисе. Зарегистрироваться #реклама 16+ office-online.bitrix24.ru О рекламодателе

#easy Задача: 734. Sentence Similarity Мы можем представить предложение в виде массива слов, например, предложение "I am happy with leetcode" можно представить как arr = ["I", "am",happy", "with", "leetcode"]. Даны два предложения sentence1 и sentence2, каждое из которых представлено в виде массива строк, и массив пар строк similarPairs, где similarPairs[i] = [xi, yi] указывает, что два слова xi и yi похожи. Возвращается true, если предложения sentence1 и sentence2 похожи, или false, если они не похожи. Два предложения похожи, если: у них одинаковая длина (т.е, Заметьте, что слово всегда похоже само на себя, также обратите внимание, что отношение сходства не является транзитивным. Например, если слова a и b похожи, а слова b и c похожи, то a и c не обязательно похожи. Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","fine"],["drama","acting"],["skills","talent"]]
Output: true

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

using System;
using System.Collections.Generic;

public class Solution {
    public bool AreSentencesSimilar(string[] sentence1, string[] sentence2, IList<IList<string>> similarPairs) {
        if (sentence1.Length != sentence2.Length) {
            return false;
        }

        var similar = new Dictionary<string, HashSet<string>>();
        foreach (var pair in similarPairs) {
            var x = pair[0];
            var y = pair[1];
            if (!similar.ContainsKey(x)) {
                similar[x] = new HashSet<string>();
            }
            if (!similar.ContainsKey(y)) {
                similar[y] = new HashSet<string>();
            }
            similar[x].Add(y);
            similar[y].Add(x);
        }

        for (int i = 0; i < sentence1.Length; i++) {
            var w1 = sentence1[i];
            var w2 = sentence2[i];
            if (w1 != w2 && (!similar.ContainsKey(w1) || !similar[w1].Contains(w2))) {
                return false;
            }
        }

        return true;
    }
}

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

Разработка сайтов любой сложности для вашей ниши! Ищете надежного партнера для разработки сайта? Мы предлагаем полный спектр услуг по созданию сайтов любой сложности. От простых лендингов до сложных интернет-магазинов – мы поможем вам создать эффективный инструмент для развития вашего бизнеса. -Разработка лендингов: для быстрых продаж и лидогенерации. -Корпоративные сайты: для представления вашей компании в интернете. -Интернет-магазины: для онлайн-торговли с полным функционалом. ✅Уникальный дизайн: разработанный с учетом ваших целей и задач. ✅Быстрые сроки: от 3 дней до запуска сайта. ✅Официальный договор: гарантия качества и прозрачности. 💰Начните зарабатывать больше с качественным сайтом! 💻Закажите разработку сайта прямо сейчас на kupisite.site Получить предложение #реклама kupisite.site О рекламодателе

#easy Задача: 733. Flood Fill Изображение представлено в виде целочисленной сетки m x n, где image[i][j] - значение пикселя изображения. Вам также даны три целых числа sr, sc и color. Вы должны выполнить заливку изображения, начиная с пикселя image[sr][sc]. Чтобы выполнить заливку, рассмотрите начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с начальным пикселем, того же цвета, что и начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с этими пикселями (также того же цвета), и так далее. Замените цвет всех вышеупомянутых пикселей на цвет. Верните измененное изображение после выполнения заливки. Пример:

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

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

public class Solution {
    public int[][] FloodFill(int[][] image, int sr, int sc, int color) {
        int originalColor = image[sr][sc];
        if (originalColor == color) {
            return image;
        }
        
        DFS(image, sr, sc, originalColor, color);
        return image;
    }
    
    private void DFS(int[][] image, int x, int y, int originalColor, int newColor) {
        if (x < 0 || x >= image.Length || y < 0 || y >= image[0].Length || image[x][y] != originalColor) {
            return;
        }
        image[x][y] = newColor;
        DFS(image, x + 1, y, originalColor, newColor);
        DFS(image, x - 1, y, originalColor, newColor);
        DFS(image, x, y + 1, originalColor, newColor);
        DFS(image, x, y - 1, originalColor, newColor);
    }
}

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

Живи и зарабатывай в Крыму 2 500 000 рублей ежегодно! 👌Поможем подобрать лучшие апартаменты Крыма с собственным пляжем, видом на море и горы 😊Живите сами, отдыхайте здесь с семьей или сдавайте и получайте пассивный доход 2 500 000 рублей в год -Апартаменты на любой вкус а также под ваш бюджет -Акции от застройщиков: рассрочка без переплат, ежемесячный платеж всего 50 тысяч рублей -Старт продаж! -Апартаменты с видом на море или горы - под ваш вкус! 🏠Мы предлагаем несколько способов покупки а также услуги по подбору недвижимости с помощью: ипотеки, рассрочки, дистанционной покупки ✅Узнайте подробнее и получите вкусное предложение Узнать больше Проектная декларация на сайте https://наш.дом.рф/ #реклама mrqz.me О рекламодателе

#hard Задача: 732. My Calendar III k-бронирование происходит, когда k событий имеют некоторое непустое пересечение (т.е, дано некоторое время, общее для всех k событий). Даны некоторые события [startTime, endTime), после каждого данного события верните целое число k, представляющее максимальное k-бронирование между всеми предыдущими событиями. Реализация класса MyCalendarThree: MyCalendarThree() Инициализирует объект. int book(int startTime, int endTime) Возвращает целое число k, представляющее наибольшее целое число, при котором в календаре существует k-бронирование. Пример:

Input
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, 1, 1, 2, 3, 3, 3]

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

using System;
using System.Collections.Generic;

public class MyCalendarThree {
    private SortedDictionary<int, int> events;

    public MyCalendarThree() {
        events = new SortedDictionary<int, int>();
    }

    public int Book(int startTime, int endTime) {
        if (!events.ContainsKey(startTime)) {
            events[startTime] = 0;
        }
        if (!events.ContainsKey(endTime)) {
            events[endTime] = 0;
        }
        events[startTime]++;
        events[endTime]--;
        
        int active = 0;
        int maxActive = 0;
        foreach (var count in events.Values) {
            active += count;
            maxActive = Math.Max(maxActive, active);
        }
        
        return maxActive;
    }
}

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

Курс по frontend-разработке с junior до middle Стань специалистом по frontend-разработке с помощью менторов. Оставь заявку! Узнать больше #реклама 16+ ykul.ru О рекламодателе

#medium Задача: 731. My Calendar II Вы создаете программу для использования в качестве календаря. Мы можем добавить новое событие, если его добавление не приведет к тройному бронированию. Тройное бронирование происходит, когда три события имеют некоторое непустое пересечение (т.е, Событие можно представить в виде пары целых чисел start и end, которая представляет собой бронирование на полуоткрытом интервале [start, end), диапазоне вещественных чисел x таких, что start <= x < end. Реализация класса MyCalendarTwo: MyCalendarTwo() Инициализирует объект календаря. boolean book(int start, int end) Возвращает true, если событие может быть успешно добавлено в календарь, не вызывая тройного бронирования. В противном случае возвращается false и событие не добавляется в календарь. Пример:

Input
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, true, true, true, false, true, true]

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

using System;
using System.Collections.Generic;

public class MyCalendarTwo {
    private List<(int, int)> events;
    private List<(int, int)> overlaps;

    public MyCalendarTwo() {
        events = new List<(int, int)>();
        overlaps = new List<(int, int)>();
    }

    public bool Book(int start, int end) {
        foreach (var (os, oe) in overlaps) {
            if (start < oe && end > os) {
                return false;
            }
        }
        foreach (var (es, ee) in events) {
            if (start < ee && end > es) {
                overlaps.Add((Math.Max(start, es), Math.Min(end, ee)));
            }
        }
        events.Add((start, end));
        return true;
    }
}

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

Крупнейший университет искусственного интеллекта Временные ряды — это данные, упорядоченные во времени, например, трафик на дорогах, изменения температуры или спрос на товары. С помощью AI можно предсказывать тренды, выявлять аномалии и оптимизировать процессы. Получите полный доступ к курсу по временным рядам на сайте. Это абсолютно бесплатно. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя среди наших студентов! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

#hard Задача: 730. Count Different Palindromic Subsequences Поскольку ответ может быть очень большим, верните его по модулю 109 + 7. Подпоследовательность строки получается путем удаления из нее нуля или более символов. Последовательность является палиндромной, если она равна последовательности, обращенной назад. Две последовательности a1, a2, ... и b1, b2, ... различны, если существует некоторое i, для которого ai != bi. Пример:

Input: s = "bccb"
Output: 6

👨‍💻 Алгоритм: 1⃣Используйте динамическое программирование для подсчета количества палиндромных подпоследовательностей. 2⃣Введите двумерный массив dp, где dp[i][j] представляет количество палиндромных подпоследовательностей в подстроке от i до j. 3⃣Итерируйте по длине подстрок от 1 до длины строки и обновляйте значения в dp на основе состояния предыдущих подстрок. 😎 Решение:

public class Solution {
    public int CountPalindromicSubsequences(string s) {
        const int MOD = 1000000007;
        int n = s.Length;
        int[,] dp = new int[n, n];

        for (int i = 0; i < n; i++) {
            dp[i, i] = 1;
        }

        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                if (s[i] == s[j]) {
                    int l = i + 1, r = j - 1;
                    while (l <= r && s[l] != s[i]) l++;
                    while (l <= r && s[r] != s[j]) r--;
                    
                    if (l > r) {
                        dp[i, j] = dp[i + 1, j - 1] * 2 + 2;
                    } else if (l == r) {
                        dp[i, j] = dp[i + 1, j - 1] * 2 + 1;
                    } else {
                        dp[i, j] = dp[i + 1, j - 1] * 2 - dp[l + 1, r - 1];
                    }
                } else {
                    dp[i, j] = dp[i + 1, j] + dp[i, j - 1] - dp[i + 1, j - 1];
                }

                dp[i, j] = (dp[i, j] + MOD) % MOD;
            }
        }

        return dp[0, n - 1];
    }
}

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

#hard Задача: 728. Self Dividing Numbers Например, 128 является саморазделяющимся числом, потому что 128 % 1 == 0, 128 % 2 == 0 и 128 % 8 == 0. Саморазделяющееся число не может содержать цифру ноль. Если даны два целых числа left и right, верните список всех саморазделяющихся чисел в диапазоне [left, right]. Пример:

Input: left = 1, right = 22
Output: [1,2,3,4,5,6,7,8,9,11,12,15,22]

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

public class Solution {
    public IList<int> SelfDividingNumbers(int left, int right) {
        List<int> result = new List<int>();
        for (int num = left; num <= right; num++) {
            if (IsSelfDividing(num)) {
                result.Add(num);
            }
        }
        return result;
    }
    
    private bool IsSelfDividing(int num) {
        int n = num;
        while (n > 0) {
            int digit = n % 10;
            if (digit == 0 || num % digit != 0) {
                return false;
            }
            n /= 10;
        }
        return true;
    }
}

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

#hard Задача: 727. Minimum Window Subsequence Если в строках s1 и s2 нет такого окна, которое покрывало бы все символы в s2, верните пустую строку "". Если таких окон минимальной длины несколько, возвращается окно с самым левым начальным индексом. Пример:

Input: s1 = "abcdebdde", s2 = "bde"
Output: "bcde"

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

public class Solution {
    public string MinWindow(string s1, string s2) {
        if (string.IsNullOrEmpty(s1) || string.IsNullOrEmpty(s2)) {
            return "";
        }

        var dictT = new Dictionary<char, int>();
        foreach (char c in s2) {
            if (dictT.ContainsKey(c)) {
                dictT[c]++;
            } else {
                dictT[c] = 1;
            }
        }

        int required = dictT.Count;
        int l = 0, r = 0, formed = 0;
        var windowCounts = new Dictionary<char, int>();
        int[] ans = { int.MaxValue, 0, 0 };

        while (r < s1.Length) {
            char c = s1[r];
            if (windowCounts.ContainsKey(c)) {
                windowCounts[c]++;
            } else {
                windowCounts[c] = 1;
            }

            if (dictT.ContainsKey(c) && windowCounts[c] == dictT[c]) {
                formed++;
            }

            while (l <= r && formed == required) {
                c = s1[l];

                if (r - l + 1 < ans[0]) {
                    ans[0] = r - l + 1;
                    ans[1] = l;
                    ans[2] = r;
                }

                windowCounts[c]--;
                if (dictT.ContainsKey(c) && windowCounts[c] < dictT[c]) {
                    formed--;
                }

                l++;
            }

            r++;
        }

        return ans[0] == int.MaxValue ? "" : s1.Substring(ans[1], ans[0]);
    }
}

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

#hard Задача: 726. Number of Atoms Если задана строковая формула, представляющая химическую формулу, верните количество атомов. Атомный элемент всегда начинается с прописного символа, затем ноль или более строчных букв, представляющих его название. Если количество больше 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();
    }
}

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

Битрикс24 💻Один онлайн-сервис для совместной работы. 📱10+ инструментов. ✅0 денег. Счастливые сотрудники. Прибыльный бизнес. Регистрируйтесь и забирайте себе Зарегистрироваться #реклама 16+ office-online.bitrix24.ru О рекламодателе