C# LeetCode - tareas

Задача: 948. Bag of Tokens Сложность: medium Вы начинаете с начальной силой, равной power, начальным счетом 0 и мешком жетонов, представленным в виде целочисленного массива tokens, где каждый tokens[i] обозначает значение tokeni. Ваша цель - максимизировать общее количество очков, стратегически разыгрывая эти жетоны. За один ход вы можете разыграть неразыгранный жетон одним из двух способов (но не обоими для одного и того же жетона): лицом вверх: Если ваша текущая сила не меньше жетонов[i], вы можете сыграть токени, потеряв силу жетонов[i] и получив 1 очко. Лицом вниз: Если ваш текущий счет не меньше 1, вы можете сыграть токени, получив силу токенов[i] и потеряв 1 счет. Верните максимально возможный счет, который вы можете получить, сыграв любое количество токенов. Пример: Input: tokens = [100], power = 50 Output: 0 👨💻 Алгоритм: 1⃣Отсортировать массив tokens. Использовать два указателя: left и right, чтобы отслеживать начало и конец массива токенов. Инициализировать переменные для текущей силы power, текущего счета score и максимального счета maxScore 2⃣Повторять следующие шаги, пока left не превысит right: Если текущая сила power достаточна для разыгрывания токена tokens[left] лицом вверх, разыграть его и увеличить счет. Если текущая сила недостаточна, но счет больше 0, разыграть токен tokens[right] лицом вниз и уменьшить счет. Обновить максимальный счет, если текущий счет больше максимального. 3⃣Вернуть максимальный счет. 😎 Решение: public class Solution { public int BagOfTokensScore(int[] tokens, int power) { Array.Sort(tokens); int left = 0, right = tokens.Length - 1; int score = 0, maxScore = 0; while (left = tokens[left]) { power -= tokens[left]; score++; left++; maxScore = Math.Max(maxScore, score); } else if (score > 0) { power += tokens[right]; score--; right--; } else { break; } } return maxScore; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1056. Confusing Number Сложность: easy Запутанное число - это число, которое при повороте на 180 градусов становится другим числом, каждая цифра которого действительна. Мы можем повернуть цифры числа на 180 градусов, чтобы получить новые цифры. Когда 0, 1, 6, 8 и 9 поворачиваются на 180 градусов, они становятся 0, 1, 9, 8 и 6 соответственно. При повороте на 180 градусов 2, 3, 4, 5 и 7 становятся недействительными. Обратите внимание, что после поворота числа мы можем игнорировать ведущие нули. Например, после поворота 8000 мы получим 0008, которое считается просто 8. Если задано целое число n, верните true, если это запутанное число, или false в противном случае. Пример: Input: n = 6 Output: true 👨💻 Алгоритм: 1⃣Преобразуй число в строку для удобства работы с его цифрами. Используй словарь для хранения соответствий цифр при повороте на 180 градусов. 2⃣Пройди по цифрам числа, проверяя, что все цифры действительны и заменяя их на соответствующие при повороте. 3⃣Проверь, что перевернутая строка отличается от исходной. 😎 Решение: public class Solution { public bool IsConfusingNumber(int n) { string nStr = n.ToString(); Dictionary rotationMap = new Dictionary { {'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'} }; StringBuilder rotatedStr = new StringBuilder(); foreach (char ch in nStr) { if (!rotationMap.ContainsKey(ch)) { return false; } rotatedStr.Insert(0, rotationMap[ch]); } return rotatedStr.ToString() != nStr; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1101. The Earliest Moment When Everyone Become Friends Сложность: medium В социальной группе есть n человек, пронумерованных от 0 до n - 1. Вам дан массив logs, где logs[i] = [timestampi, xi, yi] указывает, что xi и yi станут друзьями в момент времени timestampi. Дружба является симметричной. Это означает, что если a является другом b, то b является другом a. Также человек a знаком с человеком b, если a является другом b или a является другом кого-то, кто знаком с b. Верните самое раннее время, когда каждый человек стал знаком с каждым другим человеком. Если такого времени не существует, верните -1. Пример: Input: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4 Output: 3 Explanation: At timestamp = 3, all the persons (i.e., 0, 1, 2, and 3) become friends. 👨💻 Алгоритм: 1⃣Отсортируйте логи по времени в хронологическом порядке, так как в задаче не указано, отсортированы ли они. 2⃣Пройдитесь по отсортированным логам, применяя структуру данных "Объединение-Поиск": Для каждого лога объедините двух участников, упомянутых в логе, с помощью функции union(a, b). Каждое объединение добавляет новые связи между участниками. 3⃣Следите за количеством групп: Изначально каждый участник рассматривается как отдельная группа. Количество групп уменьшается с каждым полезным объединением. Момент, когда количество групп уменьшается до одной, является самым ранним моментом, когда все участники становятся связанными (друзьями). Верните этот момент времени. Если такого момента не существует, верните -1. 😎 Решение: public class UnionFind { private int[] parent; private int[] rank; public UnionFind(int n) { parent = new int[n]; rank = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; rank[i] = 1; } } public int Find(int x) { if (parent[x] != x) { parent[x] = Find(parent[x]); } return parent[x]; } public bool Union(int x, int y) { int rootX = Find(x); int rootY = Find(y); if (rootX != rootY) { if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else { parent[rootY] = rootX; rank[rootX]++; } return true; } return false; } } public class Solution { public int EarliestAcq(int[][] logs, int n) { Array.Sort(logs, (a, b) => a[0].CompareTo(b[0])); var uf = new UnionFind(n); int groupCount = n; foreach (var log in logs) { int timestamp = log[0]; int friendA = log[1]; int friendB = log[2]; if (uf.Union(friendA, friendB)) { groupCount--; } if (groupCount == 1) { return timestamp; } } return -1; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 242. Valid Anagram Сложность: easy Даны две строки s и t, верните true, если t является анаграммой s, и false в противном случае. Анаграмма — это слово или фраза, сформированная путём перестановки букв другого слова или фразы, обычно используя все исходные буквы ровно один раз. Пример: Input: s = "anagram", t = "nagaram" Output: true 👨💻 Алгоритм: 1⃣Создайте массив размером 26 для подсчета частот каждой буквы (поскольку s и t содержат только буквы от 'a' до 'z'). 2⃣Пройдитесь по строке s, увеличивая счетчик соответствующей буквы. Затем пройдитесь по строке t, уменьшая счетчик для каждой буквы. 3⃣Проверьте, не опустился ли счетчик ниже нуля во время обхода строки t. Если это произошло, значит в t есть лишняя буква, которой нет в s, и следует вернуть false. Если после проверки всех букв все счетчики равны нулю, возвращайте true, указывая на то, что t является анаграммой s. 😎 Решение: public bool IsAnagram(string s, string t) { if (s.Length != t.Length) { return false; } int[] table = new int[26]; for (int i = 0; i < s.Length; i++) { table[s[i] - 'a']++; table[t[i] - 'a']--; } foreach (int count in table) { if (count != 0) return false; } return true; } Ставь 👍 и забирай 📚 Базу знаний

Задача: 850. Rectangle Area II Сложность: hard Вам дан двумерный массив прямоугольников, выровненных по осям. Каждый прямоугольник[i] = [xi1, yi1, xi2, yi2] обозначает i-й прямоугольник, где (xi1, yi1) — координаты нижнего левого угла, а (xi2, yi2) — координаты верхнего правого угла. Вычислите общую площадь, покрытую всеми прямоугольниками на плоскости. Любая площадь, покрытая двумя или более прямоугольниками, должна учитываться только один раз. Верните общую площадь. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7. Пример: Input: rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]] Output: 6 Explanation: A total area of 6 is covered by all three rectangles, as illustrated in the picture. From (1,1) to (2,2), the green and red rectangles overlap. From (1,0) to (2,3), all three rectangles overlap. 👨💻 Алгоритм: 1⃣Переназначьте каждую x координату на 0, 1, 2, .... Аналогично, переназначьте все y координаты. 2⃣Теперь мы имеем задачу, которую можно решить методом грубой силы: для каждого прямоугольника с переназначенными координатами (rx1, ry1, rx2, ry2) заполним сетку grid[x][y] = True для rx1

Задача: 491. Non-decreasing Subsequences Сложность: medium Дан массив целых чисел nums. Верните все возможные различные неубывающие подпоследовательности данного массива, содержащие как минимум два элемента. Вы можете вернуть ответ в любом порядке. Пример: Input: nums = [4,6,7,7] Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]] 👨💻 Алгоритм: 1⃣Инициализация и запуск функции обратного отслеживания Создайте множество для хранения результатов. Создайте список для хранения текущей последовательности. Запустите рекурсивную функцию обратного отслеживания с начальным индексом 0. 2⃣Функция обратного отслеживания Если текущий индекс равен длине массива, проверьте длину текущей последовательности и добавьте её в результат, если она содержит не менее двух элементов. Если текущая последовательность остаётся неубывающей после добавления текущего элемента массива, добавьте этот элемент, вызовите рекурсивную функцию для следующего индекса и удалите элемент из последовательности (обратное отслеживание). Всегда вызывайте рекурсивную функцию для следующего индекса без добавления текущего элемента. 3⃣Возврат результата После завершения всех рекурсивных вызовов преобразуйте множество результатов в список и верните его. 😎 Решение: public class Solution { public IList FindSubsequences(int[] nums) { var result = new HashSet(); var sequence = new List(); Backtrack(nums, 0, sequence, result); return result.ToList(); } private void Backtrack(int[] nums, int index, List sequence, HashSet result) { if (index == nums.Length) { if (sequence.Count >= 2) { result.Add(new List(sequence)); } return; } if (sequence.Count == 0 || sequence[sequence.Count - 1]

Задача: 136. Single Number Сложность: easy Дан непустой массив целых чисел nums, в котором каждый элемент встречается дважды, кроме одного. Найдите этот единственный элемент. Вы должны реализовать решение с линейной сложностью выполнения и использовать только постоянное дополнительное пространство. Пример: Input: nums = [2,2,1] Output: 1 👨💻 Алгоритм: 1⃣Переберите все элементы в массиве nums. 2⃣Если какое-то число в nums новое для массива, добавьте его. 3⃣Если какое-то число уже есть в массиве, удалите его. 😎 Решение: public class Solution { public int SingleNumber(int[] nums) { List no_duplicate_list = new List(); foreach (int i in nums) { if (!no_duplicate_list.Contains(i)) { no_duplicate_list.Add(i); } else { no_duplicate_list.Remove(i); } } return no_duplicate_list[0]; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1026. Maximum Difference Between Node and Ancestor Сложность: medium Учитывая корень бинарного дерева, найдите максимальное значение v, для которого существуют различные вершины a и b, где v = |a.val - b.val| и a является предком b. Вершина a является предком b, если: любой ребенок a равен b или любой ребенок a является предком b. Пример: Input: root = [8,3,10,1,6,null,14,null,null,4,7,13] Output: 7 👨💻 Алгоритм: 1⃣Рекурсивный обход дерева: Используйте рекурсивную функцию для обхода дерева. Передавайте минимальное и максимальное значения, встреченные на пути от корня к текущему узлу. 2⃣Обновление максимальной разницы: При посещении каждого узла обновляйте минимальное и максимальное значения. Вычисляйте разницу между текущим значением узла и минимальным и максимальным значениями на пути. Обновляйте максимальную разницу, если текущая разница больше. 3⃣Рекурсивный вызов для детей: Рекурсивно вызывайте функцию для левого и правого поддерева, передавая обновленные минимальное и максимальное значения. 😎 Решение: public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int x) { val = x; } } public class Solution { public int MaxAncestorDiff(TreeNode root) { return Dfs(root, root.val, root.val); } private int Dfs(TreeNode node, int minVal, int maxVal) { if (node == null) return maxVal - minVal; minVal = Math.Min(minVal, node.val); maxVal = Math.Max(maxVal, node.val); int left = Dfs(node.left, minVal, maxVal); int right = Dfs(node.right, minVal, maxVal); return Math.Max(left, right); } } Ставь 👍 и забирай 📚 Базу знаний

Задача: №16. 3Sum Closest Сложность: medium Учитывая целочисленный массив nums длины n и целочисленную цель, найдите три целых числа в nums, сумма которых наиболее близка к цели. Возвращает сумму трех целых чисел. Вы можете предположить, что каждый вход будет иметь ровно одно решение. Пример: Input: nums = [-1,2,1,-4], target = 1 Output: 2 👨💻 Алгоритм: 1⃣Отсортировать массив и инициализировать переменные для отслеживания минимальной разницы. 2⃣Использовать два указателя (left и right) для поиска суммы трех чисел, обновляя их в зависимости от текущей суммы. 3⃣Возвращать сумму, которая наиболее близка к target. 😎 Решение: public class Solution { public int ThreeSumClosest(int[] nums, int target) { Array.Sort(nums); int closestSum = nums[0] + nums[1] + nums[2]; for (int i = 0; i < nums.Length - 2; i++) { int left = i + 1, right = nums.Length - 1; while (left < right) { int currentSum = nums[i] + nums[left] + nums[right]; if (Math.Abs(target - currentSum) < Math.Abs(target - closestSum)) { closestSum = currentSum; } if (currentSum < target) { left++; } else { right--; } } } return closestSum; } } Ставь 👍 и забирай 📚 Базу знаний