C# | LeetCode

#easy Задача: 746. Min Cost Climbing Stairs Вам дан целочисленный массив cost, где cost[i] - стоимость i-й ступеньки на лестнице. После оплаты стоимости вы можете подняться на одну или две ступеньки. Вы можете начать со ступеньки с индексом 0 или со ступеньки с индексом 1. Верните минимальную стоимость достижения вершины этажа. Пример:

Input: cost = [10,15,20]
Output: 15

👨‍💻 Алгоритм: 1⃣Создать массив dp, где dp[i] хранит минимальную стоимость достижения i-й ступеньки. 2⃣Инициализировать dp[0] и dp[1] как cost[0] и cost[1] соответственно. Заполнить dp используя минимальную стоимость подъема с предыдущих ступенек. 3⃣Вернуть минимальную стоимость достижения вершины. 😎 Решение:

public class Solution {
    public int MinCostClimbingStairs(int[] cost) {
        int n = cost.Length;
        int[] dp = new int[n];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < n; i++) {
            dp[i] = cost[i] + Math.Min(dp[i - 1], dp[i - 2]);
        }
        return Math.Min(dp[n - 1], dp[n - 2]);
    }
}

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

Karpov.Сourses. Онлайн-школа востребованных IT-профессий 🎓Удобные форматы обучения: Специализации, симуляторы профессий и бесплатные курсы! Узнать больше #реклама 16+ karpov.courses О рекламодателе

#hard Задача: 745. Prefix and Suffix Search Создайте специальный словарь, в котором поиск слов осуществляется по префиксу и суффиксу. Реализуйте класс WordFilter: WordFilter(string[] words) Инициализирует объект со словами в словаре. f(string pref, string suff) Возвращает индекс слова в словаре, которое имеет префикс pref и суффикс suff. Если существует более одного допустимого индекса, возвращается наибольший из них. Если в словаре нет такого слова, возвращается -1. Пример:

Input: letters = ["c","f","j"], target = "a"
Output: "c"

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

using System;
using System.Collections.Generic;

public class WordFilter {
    private Dictionary<string, int> prefixSuffixMap = new Dictionary<string, int>();
    
    public WordFilter(string[] words) {
        for (int index = 0; index < words.Length; index++) {
            string word = words[index];
            int length = word.Length;
            for (int prefixLength = 1; prefixLength <= length; prefixLength++) {
                for (int suffixLength = 1; suffixLength <= length; suffixLength++) {
                    string prefix = word.Substring(0, prefixLength);
                    string suffix = word.Substring(length - suffixLength);
                    string key = prefix + "#" + suffix;
                    prefixSuffixMap[key] = index;
                }
            }
        }
    }
    
    public int F(string pref, string suff) {
        string key = pref + "#" + suff;
        return prefixSuffixMap.ContainsKey(key) ? prefixSuffixMap[key] : -1;
    }
}

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

Курс "Дизайн карточек для WB и Ozon". Бесплатно и с нуля Дизайнер карточек для маркетплейсов — востребованная и доходная профессия 💰 Научись ей бесплатно! - Бесплатный доступ - Разбор ДЗ от наставника - Мощные кейсы в портфолио Узнать больше #реклама 16+ yudaevschool24.online О рекламодателе

#easy Задача: 744. Find Smallest Letter Greater Than Target Нам дан массив символов letters, отсортированный в неубывающем порядке, и символ target. В массиве letters есть как минимум два разных символа. Возвращается наименьший символ в letters, который лексикографически больше target. Если такого символа не существует, возвращается первый символ в буквах. Пример:

Input: letters = ["c","f","j"], target = "a"
Output: "c"

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

public class Solution {
    public char NextGreatestLetter(char[] letters, char target) {
        int left = 0, right = letters.Length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (letters[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return letters[left % letters.Length];
    }
}

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

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

#medium Задача: 743. Network Delay Time Дана сеть из узлов, помеченных от 1 до n. Также дано times - список времен прохождения сигнала в виде направленных ребер times[i] = (ui, vi, wi), где ui - исходный узел, vi - целевой узел, а wi - время прохождения сигнала от источника до цели. Мы пошлем сигнал из заданного узла k. Верните минимальное время, которое потребуется всем узлам, чтобы получить сигнал. Если все узлы не могут получить сигнал, верните -1. Пример:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

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

using System;
using System.Collections.Generic;

public class Solution {
    public int NetworkDelayTime(int[][] times, int n, int k) {
        var graph = new Dictionary<int, List<int[]>>();
        for (int i = 1; i <= n; i++) {
            graph[i] = new List<int[]>();
        }
        foreach (var time in times) {
            graph[time[0]].Add(new int[]{time[1], time[2]});
        }

        var minHeap = new SortedSet<(int time, int node)>(Comparer<(int, int)>.Create((a, b) => a.time != b.time ? a.time - b.time : a.node - b.node));
        minHeap.Add((0, k));
        var minTime = new Dictionary<int, int>();
        for (int i = 1; i <= n; i++) {
            minTime[i] = int.MaxValue;
        }
        minTime[k] = 0;

        while (minHeap.Count > 0) {
            var (time, node) = minHeap.Min;
            minHeap.Remove(minHeap.Min);
            foreach (var neighbor in graph[node]) {
                int newTime = time + neighbor[1];
                if (newTime < minTime[neighbor[0]]) {
                    minHeap.Remove((minTime[neighbor[0]], neighbor[0]));
                    minTime[neighbor[0]] = newTime;
                    minHeap.Add((newTime, neighbor[0]));
                }
            }
        }

        int maxTime = int.MinValue;
        foreach (var t in minTime.Values) {
            if (t == int.MaxValue) return -1;
            maxTime = Math.Max(maxTime, t);
        }
        return maxTime;
    }
}

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

Курс Аналитика данных с нуля. Теперь со скидкой 50%! 🎓Получите новую профессию и постройте успешную карьеру в IT-сфере с нашим курсом Узнать больше #реклама 16+ karpov.courses О рекламодателе

#medium Задача: 742. Closest Leaf in a Binary Tree Если задан корень бинарного дерева, в котором каждый узел имеет уникальное значение, а также задано целое число k, верните значение ближайшего к цели k узла листа дерева. Ближайший к листу узел означает наименьшее количество ребер, пройденных бинарным деревом, чтобы достичь любого листа дерева. Кроме того, узел называется листом, если у него нет дочерних узлов. Пример:

Input: root = [1,3,2], k = 1
Output: 2

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

using System;
using System.Collections.Generic;

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

public class Solution {
    public int FindClosestLeaf(TreeNode root, int k) {
        List<TreeNode> path = new List<TreeNode>();
        Dictionary<TreeNode, int> leaves = new Dictionary<TreeNode, int>();
        
        FindPath(root, k, path);
        FindLeaves(root, leaves);
        
        Queue<Tuple<TreeNode, int>> queue = new Queue<Tuple<TreeNode, int>>();
        queue.Enqueue(new Tuple<TreeNode, int>(path[path.Count - 1], 0));
        HashSet<TreeNode> visited = new HashSet<TreeNode>();
        
        while (queue.Count > 0) {
            var tuple = queue.Dequeue();
            TreeNode node = tuple.Item1;
            int dist = tuple.Item2;
            if (leaves.ContainsKey(node)) return node.val;
            visited.Add(node);
            if (node.left != null && !visited.Contains(node.left)) queue.Enqueue(new Tuple<TreeNode, int>(node.left, dist + 1));
            if (node.right != null && !visited.Contains(node.right)) queue.Enqueue(new Tuple<TreeNode, int>(node.right, dist + 1));
            if (path.Count > 1) queue.Enqueue(new Tuple<TreeNode, int>(path[path.Count - 2], dist + 1)), path.RemoveAt(path.Count - 1);
        }
        return -1;
    }
    
    private bool FindPath(TreeNode node, int k, List<TreeNode> path) {
        if (node == null) return false;
        path.Add(node);
        if (node.val == k) return true;
        if (FindPath(node.left, k, path) || FindPath(node.right, k, path)) return true;
        path.RemoveAt(path.Count - 1);
        return false;
    }
    
    private void FindLeaves(TreeNode node, Dictionary<TreeNode, int> leaves) {
        if (node == null) return;
        if (node.left == null && node.right == null) leaves[node] = 0;
        FindLeaves(node.left, leaves);
        FindLeaves(node.right, leaves);
    }
}

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

6 свободных мест на курс Коммутаторы MES продвинутый Осталось 6 мест: - 3 очных - 3 дистанционных Использование коммутаторов MES (продвинутый) Даты - 24.03-28.03 (5 дней) Другие курсы: Март: Коммутаторы MES (базовый уровень) - 10.03 - 14.03 - 4 места Апрель: Маршрутизаторы ESR (продвинутый уровень) - 31.03 - 04.04 - 8 мест Коммутаторы MES (базовый уровень) - 07.04 - 11.04 - 8 мест Записаться #реклама 16+ eltexcm.ru О рекламодателе

#hard Задача: 741. Cherry Pickup Вам дана сетка n x n, представляющая поле вишен. Каждая клетка - одно из трех возможных целых чисел. 0 означает, что клетка пуста, и вы можете пройти через нее, 1 означает, что клетка содержит вишню, которую вы можете сорвать и пройти через нее, или -1 означает, что клетка содержит шип, который преграждает вам путь. Верните максимальное количество вишен, которое вы можете собрать, следуя следующим правилам: Начиная с позиции (0, 0) и достигая (n - 1, n - 1) путем перемещения вправо или вниз через допустимые клетки пути (клетки со значением 0 или 1). После достижения (n - 1, n - 1) вернитесь в (0, 0), двигаясь влево или вверх по клеткам с действительными путями. Проходя через клетку пути, содержащую вишню, вы поднимаете ее, и клетка становится пустой клеткой 0. Если между (0, 0) и (n - 1, n - 1) нет действительного пути, то вишни собрать нельзя. Пример:

Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5

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

using System;

public class Solution {
    public int CherryPickup(int[][] grid) {
        int n = grid.Length;
        int[][][] dp = new int[n][][];
        for (int i = 0; i < n; i++) {
            dp[i] = new int[n][];
            for (int j = 0; j < n; j++) {
                dp[i][j] = new int[2 * n - 1];
                Array.Fill(dp[i][j], int.MinValue);
            }
        }
        dp[0][0][0] = grid[0][0];

        for (int k = 1; k < 2 * n - 1; k++) {
            for (int i1 = Math.Max(0, k - n + 1); i1 <= Math.Min(n - 1, k); i1++) {
                for (int i2 = Math.Max(0, k - n + 1); i2 <= Math.Min(n - 1, k); i2++) {
                    int j1 = k - i1, j2 = k - i2;
                    if (j1 < n && j2 < n && grid[i1][j1] != -1 && grid[i2][j2] != -1) {
                        int maxCherries = int.MinValue;
                        if (i1 > 0 && i2 > 0) maxCherries = Math.Max(maxCherries, dp[i1 - 1][i2 - 1][k - 1]);
                        if (i1 > 0) maxCherries = Math.Max(maxCherries, dp[i1 - 1][i2][k - 1]);
                        if (i2 > 0) maxCherries = Math.Max(maxCherries, dp[i1][i2 - 1][k - 1]);
                        maxCherries = Math.Max(maxCherries, dp[i1][i2][k - 1]);
                        if (maxCherries != int.MinValue) {
                            dp[i1][i2][k] = maxCherries + grid[i1][j1];
                            if (i1 != i2) dp[i1][i2][k] += grid[i2][j2];
                        }
                    }
                }
            }
        }

        return Math.Max(0, dp[n - 1][n - 1][2 * n - 1]);
    }
}

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

MBA онлайн с аккредитацией и беспроцентной рассрочкой! Готовы к карьерному рывку? Обучайтесь на программе MBA с международной аккредитацией и выйдите на новый уровень карьеры! ✅ Форматы: онлайн и офлайн ✅ 37+ направлений ✅ Актуальные программы 2025 года ✅ Диплом за 1 год ✅ Беспроцентная рассрочка Не ждите — запишитесь уже сегодня и начните свой путь к успеху! Стань лидером уже сейчас! Только до конца года Скидки до -45% на обучение в Московской Академии Бизнеса! Перейти на сайт #реклама 16+ moscow.mba О рекламодателе

#medium Задача: 740. Delete and Earn Вам дан целочисленный массив nums. Вы хотите максимизировать количество очков, выполнив следующую операцию любое количество раз: Выберите любой элемент nums[i] и удалите его, чтобы заработать nums[i] очков. После этого вы должны удалить каждый элемент, равный nums[i] - 1, и каждый элемент, равный nums[i] + 1. Верните максимальное количество очков, которое вы можете заработать, применив вышеуказанную операцию некоторое количество раз. Пример:

Input: nums = [3,4,2]
Output: 6

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

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

public class Solution {
    public int DeleteAndEarn(int[] nums) {
        var count = new Dictionary<int, int>();
        foreach (var num in nums) {
            if (!count.ContainsKey(num)) {
                count[num] = 0;
            }
            count[num]++;
        }
        
        int avoid = 0, using = 0, prev = -1;
        foreach (var num in count.Keys.OrderBy(x => x)) {
            if (num - 1 != prev) {
                int newAvoid = Math.Max(avoid, using);
                using = num * count[num] + Math.Max(avoid, using);
                avoid = newAvoid;
            } else {
                int newAvoid = Math.Max(avoid, using);
                using = num * count[num] + avoid;
                avoid = newAvoid;
            }
            prev = num;
        }
        
        return Math.Max(avoid, using);
    }
}

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

Онлайн-интенсив для ИТ-специалистов в Открытых школах Т1 Открытые школы — это возможность за месяц прокачать свои навыки и получить оффер в ИТ-холдинг Т1. С тебя — год опыта работы в ИТ, с нас — бесплатный онлайн-интенсив и топовые преподаватели. Что ты получишь? ✅ Уникальный рыночный опыт. Наши проекты ежегодно получают награды на ИТ-конкурсах: Global CIO, Национальной банковской премии и др. ✅ Быстрый рост в ИТ при экспертной поддержке. ✅ Материалы от HR, которые помогут прокачать резюме и подготовиться к интервью в Т1. ✅ Поддержка опытных преподавателей и уникальный карьерный фаст-трек до мидла в Т1 для выпускников интенсива. ✅ Реальный шанс получить оффер в Т1. Подавай заявку до 14 марта и приходи учиться! Старт ИТ-интенсива уже 17 марта. Подать заявку #реклама 16+ t1.ru О рекламодателе

#medium Задача: 739. Daily Temperatures Задав массив целых чисел temperature, представляющих дневные температуры, верните массив answer, такой, что answer[i] - это количество дней, которые нужно подождать после i-го дня, чтобы температура стала теплее. Если в будущем не существует дня, для которого это возможно, сохраните answer[i] == 0. Пример:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

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

public class Solution {
    public int[] DailyTemperatures(int[] T) {
        int n = T.Length;
        int[] answer = new int[n];
        Stack<int> stack = new Stack<int>();
        
        for (int i = 0; i < n; i++) {
            while (stack.Count > 0 && T[i] > T[stack.Peek()]) {
                int j = stack.Pop();
                answer[j] = i - j;
            }
            stack.Push(i);
        }
        
        return answer;
    }
}

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

Как айтишнику быстро получить оффер Бесплатный воркшоп 20 марта Почему одному кандидату предлагают оффер после первого интервью, а другому говорят: «Мы вам перезвоним»? Причина в подаче своего опыта. Записывайся, чтобы узнать: — Как подготовиться к собеседованию — Как презентовать свой опыт так, чтобы тебя запомнили — Как проверяют hard skills и как к этому подготовиться — Как произвести хорошее впечатление, запомнится рекрутеру и сделать так, чтобы захотели работать именно с тобой Приходи на бесплатный воркшоп и узнай, как прокачать навык самопрезентации и получить работу мечты Зарегистрироваться #реклама 16+ my.mts-link.ru О рекламодателе

#medium Задача: 738. Monotone Increasing Digits Целое число имеет монотонно возрастающие цифры тогда и только тогда, когда каждая пара соседних цифр x и y удовлетворяет x <= y. Задав целое число n, верните наибольшее число, которое меньше или равно n с монотонно возрастающими цифрами. Пример:

Input: n = 10
Output: 9

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

public class Solution {
    public int MonotoneIncreasingDigits(int N) {
        var digits = N.ToString().ToCharArray();
        int marker = digits.Length;
        
        for (int i = digits.Length - 1; i > 0; i--) {
            if (digits[i] < digits[i - 1]) {
                marker = i;
                digits[i - 1]--;
            }
        }
        
        for (int i = marker; i < digits.Length; i++) {
            digits[i] = '9';
        }
        
        return int.Parse(new string(digits));
    }
}

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

Бесплатный курс по дизайну в 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 О рекламодателе