C# | LeetCode

Партнёрская программа рекрутинга в Яндекс Еду Станьте партнёром Яндекс Еды по привлечению курьеров и получите кучу преимуществ: 💰Платим до 47 000 ₽ за успешного кандидата 📞Поддержка на всех этапах 📅Свободное расписание 📊Удобные инструменты для работы Приводите новых курьеров и получайте в среднем 250 000 ₽ в месяц! Зарегистрироваться #реклама eda.yandex.ru О рекламодателе Реклама на Яндексе

Задача: 32. Longest Valid Parentheses Сложность: hard Дана строка, содержащая только символы '(' и ')'. Верните длину самой длинной подстроки с корректными (правильно сформированными) скобками. Пример:

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

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

public class Solution {
    public int LongestValidParentheses(string s) {
        Stack<int> stack = new Stack<int>();
        stack.Push(-1);
        int maxLen = 0;

        for (int i = 0; i < s.Length; i++) {
            if (s[i] == '(') {
                stack.Push(i);
            } else {
                stack.Pop();
                if (stack.Count == 0) {
                    stack.Push(i);
                } else {
                    maxLen = Math.Max(maxLen, i - stack.Peek());
                }
            }
        }

        return maxLen;
    }
}

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

Дарим подписку на Яндекс Музыку Ответьте на 1 вопрос и Яндекс Музыка ваша для вас и 3-х ваших близких. Кинопоиск и Яндекс Книги тоже в подписке. Попробуйте бесплатно❤️ Попробовать #реклама 18+ music.yandex.ru О рекламодателе Реклама на Яндексе

Задача: 1337. The K Weakest Rows in a Matrix Сложность: easy Вам дана бинарная матрица размером m x n mat, состоящая из 1 (представляющих солдат) и 0 (представляющих гражданских лиц). Солдаты расположены перед гражданскими лицами. То есть, все 1 будут расположены слева от всех 0 в каждой строке. Строка i слабее строки j, если выполнено одно из следующих условий: Количество солдат в строке i меньше, чем в строке j. Обе строки имеют одинаковое количество солдат, но i < j. Верните индексы k самых слабых строк в матрице, упорядоченных от самой слабой к самой сильной. Пример:

Input: mat = 
[[1,1,0,0,0],
 [1,1,1,1,0],
 [1,0,0,0,0],
 [1,1,0,0,0],
 [1,1,1,1,1]], 
k = 3
Output: [2,0,3]
Explanation: 
The number of soldiers in each row is: 
- Row 0: 2 
- Row 1: 4 
- Row 2: 1 
- Row 3: 2 
- Row 4: 5 
The rows ordered from weakest to strongest are [2,0,3,1,4].

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

public class Solution {
    public int[] KWeakestRows(int[][] mat, int k) {
        int m = mat.Length;
        int n = mat[0].Length;

        var pairs = new List<(int strength, int index)>();

        for (int i = 0; i < m; i++) {
            int strength = 0;
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) break;
                strength++;
            }
            pairs.Add((strength, i));
        }

        pairs.Sort((a, b) => {
            if (a.strength == b.strength) return a.index - b.index;
            return a.strength - b.strength;
        });

        int[] indexes = new int[k];
        for (int i = 0; i < k; i++) {
            indexes[i] = pairs[i].index;
        }
        return indexes;
    }
}

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

Задача: 40. Combination Sum II Сложность: medium Дан массив candidates и целое число target. Нужно найти все уникальные комбинации чисел из candidates, сумма которых равна target. Каждое число можно использовать только один раз. Решение не должно содержать повторяющихся комбинаций. Пример:

Input: candidates = [10,1,2,7,6,1,5], target = 8  
Output:  
[  
 [1,1,6],  
 [1,2,5],  
 [1,7],  
 [2,6]  
]  

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

public class Solution {
    public IList<IList<int>> CombinationSum2(int[] candidates, int target) {
        Array.Sort(candidates);
        List<IList<int>> results = new List<IList<int>>();
        Backtrack(candidates, target, 0, new List<int>(), results);
        return results;
    }

    private void Backtrack(int[] candidates, int remain, int start, List<int> comb, List<IList<int>> results) {
        if (remain == 0) {
            results.Add(new List<int>(comb));
            return;
        }

        for (int i = start; i < candidates.Length; i++) {
            if (i > start && candidates[i] == candidates[i - 1]) continue; // Пропуск дубликатов

            if (candidates[i] > remain) break; // Оптимизация: остановка, если число больше оставшейся суммы

            comb.Add(candidates[i]);
            Backtrack(candidates, remain - candidates[i], i + 1, comb, results);
            comb.RemoveAt(comb.Count - 1);
        }
    }
}

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

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

Задача: 342. Power of Four Сложность: easy Дано целое число n. Верните true, если оно является степенью числа четыре. В противном случае верните false. Целое число n является степенью числа четыре, если существует целое число x такое, что n == 4^x. Пример:

Input: n = 16
Output: true

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

public class Solution {
    public bool IsPowerOfFour(int n) {
        if (n <= 0) return false;
        double log_n_base_4 = Math.Log(n) / Math.Log(4);
        return log_n_base_4 == Math.Floor(log_n_base_4);
    }
}

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

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

На easyoffer 2.0 появится: Тренажер "Реальное собеседование" 🟠 Сценарии вопросов из реального собеседования 🟠Возможность подготовиться к собеседованию в конкретную компанию 🟠Итоговая статистика (прошёл/не прошёл) Сценарий вопросов взят из реального собеседования. То есть вы тренируетесь на тех вопросах, которые действительно задавались в компании X. Уже в начале следующей недели стартует краудфандинг кампания, чтобы ускорить разработку easyoffer 2.0. Все кто, поддержал проект на этом этапе смогу получить 1 год доступа к сайту по цене месячной подписки. Первые 150 донатеров получать особо-выгодную цену и бонус. Следите за стартом 👉 в этом телеграм канале, в нем информация о старте будет опубликована за 6 часов до официального начала.

Задача: 1335. Minimum Difficulty of a Job Schedule Сложность: hard Вы хотите составить расписание списка заданий на d дней. Задания зависят друг от друга (т.е. чтобы выполнить задание i, вы должны закончить все задания j, где 0 <= j < i). Вы должны выполнять как минимум одно задание каждый день. Сложность расписания заданий — это сумма сложностей каждого дня из d дней. Сложность дня — это максимальная сложность задания, выполненного в этот день. Вам дан массив целых чисел jobDifficulty и целое число d. Сложность i-го задания равна jobDifficulty[i]. Верните минимальную сложность расписания заданий. Если вы не можете найти расписание для заданий, верните -1. Пример:

Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7
Explanation: First day you can finish the first 5 jobs, total difficulty = 6.
Second day you can finish the last job, total difficulty = 1.
The difficulty of the schedule = 6 + 1 = 7 

👨‍💻 Алгоритм: 1⃣Определение состояния: Индекс i (индекс первой задачи на сегодняшний день в массиве jobDifficulty) и день d (количество оставшихся дней) будут определять состояние динамического программирования. min_diff(i, d) обозначает минимальную сложность при начале с i-й задачи с оставшимися d днями. min_diff(0, d) будет окончательным ответом, так как он представляет начало с начала массива задач и завершение всех задач за ровно d дней. 2⃣Функция перехода состояния: Задача с индексом j будет первой задачей на следующий день, следовательно, задачи, которые должны быть завершены сегодня, это все задачи с индексами между i и j, то есть jobDifficulty[i ]. Поскольку сложность дня — это максимальная сложность выполненной в этот день задачи, к сумме сложностей задач будет добавляться максимум из jobDifficulty[i ]. Формулируем функцию перехода состояния следующим образом: min_diff(i, d) = min_diff(j, d - 1) + max(jobDifficulty[i ]) для всех j > i. 3⃣Базовый случай: Когда остается только 1 день, необходимо завершить все незавершенные задачи в этот день и увеличить сложность расписания задач на максимальную сложность этих задач. 😎 Решение:

public class Solution {
    public int MinDifficulty(int[] jobDifficulty, int d) {
        int n = jobDifficulty.Length;
        if (n < d) {
            return -1;
        }

        int[][] mem = new int[n][];
        for (int i = 0; i < n; i++) {
            mem[i] = new int[d + 1];
            for (int j = 0; j <= d; j++) {
                mem[i][j] = -1;
            }
        }

        return MinDiff(0, d, jobDifficulty, mem);
    }

    private int MinDiff(int i, int daysRemaining, int[] jobDifficulty, int[][] mem) {
        if (mem[i][daysRemaining] != -1) {
            return mem[i][daysRemaining];
        }

        if (daysRemaining == 1) {
            int res = 0;
            for (int j = i; j < jobDifficulty.Length; j++) {
                res = Math.Max(res, jobDifficulty[j]);
            }
            return res;
        }

        int result = int.MaxValue;
        int dailyMaxJobDiff = 0;
        for (int j = i; j < jobDifficulty.Length - daysRemaining + 1; j++) {
            dailyMaxJobDiff = Math.Max(dailyMaxJobDiff, jobDifficulty[j]);
            result = Math.Min(result, dailyMaxJobDiff + MinDiff(j + 1, daysRemaining - 1, jobDifficulty, mem));
        }
        mem[i][daysRemaining] = result;
        return result;
    }
}

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

⚡️ Айтишник из «VISION» скупил курсы айти школ и выложил гигабайты материалов к себе Каждый найдет что-то по душе: 1202 ГБ — Python 1811 ГБ — Frontend 1100 ГБ — C / C++ / C# 804 ГБ — Java 411 ГБ — SQL & БД 309 ГБ — DevOps 998 ГБ — ИБ & Хакинг 773 ГБ — Kotlin / Swift 189 ГБ — PHP 201 ГБ — GoLang 170 ГБ — Rust 167 ГБ — QA / Тестирование 310 ГБ — 1C + Лицензии 495 ГБ — Машинное обучение 704 ГБ — Аналитика Данных 991 ГБ — Дизайн Материалы в закрепе, постоянно пополняются👆🏻

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

Задача: 988. Smallest String Starting From Leaf Сложность: medium Дан корень бинарного дерева, где каждый узел имеет значение в диапазоне [0, 25], представляющее буквы от 'a' до 'z'. Верните лексикографически наименьшую строку, которая начинается с листа этого дерева и заканчивается у корня. Напоминаем, что любая более короткая префиксная строка является лексикографически меньшей. Например, "ab" лексикографически меньше, чем "aba". Лист узла - это узел, у которого нет потомков. Пример:

Input: root = [0,1,2,3,4,3,4]
Output: "dba"

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

public class Solution {
    private string ans = "~";

    public string SmallestFromLeaf(TreeNode root) {
        Dfs(root, new StringBuilder());
        return ans;
    }

    private void Dfs(TreeNode node, StringBuilder path) {
        if (node == null) return;
        path.Append((char) (node.val + 'a'));
        if (node.left == null && node.right == null) {
            var s = new string(path.ToString().Reverse().ToArray());
            if (string.Compare(s, ans) < 0) {
                ans = s;
            }
        }
        Dfs(node.left, path);
        Dfs(node.right, path);
        path.Remove(path.Length - 1, 1);
    }
}

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

На easyoffer 2.0 появится новый раздел: Задачи с собеседований 🟠Задачи на Алгоритмические, Live-coding и System Design из реальных собеседований 🟠Вероятность встретить ту или иную задачу 🟠Возможность подготовиться к задачам конкретной компании Есть много сайтов, на которых можно тренироваться решать задачи, но у них у всех одна проблема – сами задачи люди просто выдумывают. На easyoffer 2.0 вы сможете готовиться к live-coding и system design секциям на основе задач из реальных собеседований. Вы можете найдете самые частые задачи и сделаете упор на их решение. Считаные дни остались до старта краудфандинговой кампании, чтобы ускорить разработку easyoffer 2.0. Все кто, поддержал проект на этом этапе смогу получить 1 год доступа к сайту по цене месячной подписки, а те кто поддержат проект раньше других ито дешевле + получат существенный бонус. Следите за стартом 👉 в этом телеграм канале.

Нанимаете аутсорс, подрядчиков, фрилансеров? Попробуйте Битрикс24 Коллабы – платформа для эффективной работы с подрядчиками. Тут обсуждения превращаются в задачи, а видео созвон можно собрать одной кнопкой. Любой проект можно разложить по полочкам с понятным ТЗ и обозначенными сроками. Работайте в Битрикс24 и создавайте Коллабы с подрядчиками. Начать #реклама 16+ collabs.bitrix24.ru О рекламодателе

#hard Задача: 759. Employee Free Time Нам дан список schedule of employees, который представляет собой рабочее время каждого сотрудника. У каждого сотрудника есть список непересекающихся интервалов, и эти интервалы расположены в отсортированном порядке. Верните список конечных интервалов, представляющих общее свободное время положительной длины для всех сотрудников, также в отсортированном порядке. (Хотя мы представляем интервалы в форме [x, y], объекты внутри них являются интервалами, а не списками или массивами. Например, schedule[0][0].start = 1, schedule[0][0].end = 2, а schedule[0][0][0] не определено).Также мы не будем включать в наш ответ интервалы типа [5, 5], так как они имеют нулевую длину. Пример:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]

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

using System;
using System.Collections.Generic;

public class Interval {
    public int start;
    public int end;
    public Interval() {
        start = 0; end = 0;
    }
    public Interval(int s, int e) {
        start = s; end = e;
    }
}

public class Solution {
    public IList<Interval> EmployeeFreeTime(IList<IList<Interval>> schedule) {
        List<Interval> intervals = new List<Interval>();
        foreach (var employee in schedule) {
            intervals.AddRange(employee);
        }
        
        intervals.Sort((a, b) => a.start.CompareTo(b.start));
        
        List<Interval> merged = new List<Interval>();
        foreach (var interval in intervals) {
            if (merged.Count == 0 || merged[merged.Count - 1].end < interval.start) {
                merged.Add(interval);
            } else {
                merged[merged.Count - 1].end = Math.Max(merged[merged.Count - 1].end, interval.end);
            }
        }
        
        List<Interval> freeTime = new List<Interval>();
        for (int i = 1; i < merged.Count; i++) {
            if (merged[i].start > merged[i - 1].end) {
                freeTime.Add(new Interval(merged[i - 1].end, merged[i].start));
            }
        }
        
        return freeTime;
    }
}

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

#medium Задача: 758. Bold Words in String При наличии массива ключевых слов и строки a выделите все ключевые слова [i] жирным шрифтом. Все буквы между тегами <b> и </b> выделяются жирным шрифтом. Возвращает после добавления тегов, выделенных жирным шрифтом. Возвращаемая строка должна содержать как можно меньшее количество тегов, и теги должны образовывать допустимую комбинацию. Пример:

Input: words = ["ab","bc"], s = "aabcd"
Output: "a<b>abc</b>d"

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

public class Solution {
    public string AddBoldTags(string[] keywords, string s) {
        int n = s.Length;
        bool[] bold = new bool[n];
        
        foreach (string word in keywords) {
            int start = s.IndexOf(word);
            while (start != -1) {
                for (int i = start; i < start + word.Length; i++) {
                    bold[i] = true;
                }
                start = s.IndexOf(word, start + 1);
            }
        }
        
        var result = new StringBuilder();
        int j = 0;
        while (j < n) {
            if (bold[j]) {
                result.Append("<b>");
                while (j < n && bold[j]) {
                    result.Append(s[j]);
                    j++;
                }
                result.Append("</b>");
            } else {
                result.Append(s[j]);
                j++;
            }
        }
        
        return result.ToString();
    }
}

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

Бесплатное льготное обучение: 3 месяца Ищем людей, которые хотят обучиться и работать в IT-сфере из дома В конце обучения вы пройдете стажировку и устроитесь на работу с зп от 150.000 рублей Образование, место жительства, трудовой стаж — не важны! Для старта нужно: — пройти короткий тест — заполнить анкету На что можно рассчитывать, после обучения: ✅ удаленная работа ✅ зп от 150.000 рублей (потолка нет) ✅ стабильная подработка, если не хотите уходить с основной работы ⚡ Осталось всего 47 бесплатных мест. Успейте пройти тест и оставить заявку: Узнать больше #реклама 16+ technolium.ru О рекламодателе

#hard Задача: 757. Set Intersection Size At Least Two Вам дан двумерный целочисленный массив intervals, в котором intervals[i] = [starti, endi] представляет все целые числа от starti до endi включительно. Содержащее множество - это массив nums, в котором каждый интервал из intervals содержит не менее двух целых чисел в nums. Например, если intervals = [[1,3], [3,7], [8,9]], то [1,2,4,7,8,9] и [2,3,4,8,9] - содержащие множества. Верните минимально возможный размер содержащего множества. Пример:

Input: intervals = [[1,3],[3,7],[8,9]]
Output: 5

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

using System;
using System.Collections.Generic;

public class Solution {
    public int MinSetSize(int[][] intervals) {
        Array.Sort(intervals, (a, b) => a[1].CompareTo(b[1]));
        var nums = new List<int>();
        foreach (var interval in intervals) {
            int start = interval[0];
            int end = interval[1];
            if (nums.Count == 0 || nums[nums.Count - 1] < start) {
                nums.Add(end - 1);
                nums.Add(end);
            } else if (nums[nums.Count - 1] == end - 1) {
                nums.Add(end);
            }
        }
        return nums.Count;
    }
}

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

Встречайте весну в Абу-Даби! Сделайте эту весну незабываемой: отдыхайте, исследуйте богатую культуру и наполняйтесь яркими впечатлениями #inAbuDhabi! Узнать больше #реклама visitabudhabi.ae О рекламодателе