C# | LeetCode

Задача: 732. My Calendar III Сложность: hard 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; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1020. Number of Enclaves Сложность: medium Вам дана двоичная матричная сетка m x n, где 0 обозначает морскую ячейку, а 1 - сухопутную. Ход состоит из перехода от одной сухопутной ячейки к другой соседней (в 4-х направлениях) или выхода за границу сетки. Верните количество сухопутных ячеек в сетке, для которых мы не можем выйти за границу сетки за любое количество ходов. Пример: Input: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]] Output: 3 👨‍💻 Алгоритм: 1⃣Обработка граничных сухопутных ячеек: Пройдитесь по всем ячейкам, которые находятся на границе сетки (первый и последний ряды, первый и последний столбцы). Если ячейка содержит 1, начните поиск в глубину (DFS) или поиск в ширину (BFS), чтобы пометить все достижимые из нее сухопутные ячейки как посещенные. 2⃣Проверка всех ячеек: Пройдите по всем ячейкам матрицы, считая количество сухопутных ячеек, которые не были посещены в предыдущем шаге. 3⃣Возврат результата: Верните количество не посещенных сухопутных ячеек. 😎 Решение: public class Solution { public int NumEnclaves(int[][] grid) { int m = grid.Length, n = grid[0].Length; void Dfs(int x, int y) { if (x < 0 || y < 0 || x >= m || y >= n || grid[x][y] != 1) { return; } grid[x][y] = 0; Dfs(x + 1, y); Dfs(x - 1, y); Dfs(x, y + 1); Dfs(x, y - 1); } for (int i = 0; i < m; i++) { if (grid[i][0] == 1) Dfs(i, 0); if (grid[i][n - 1] == 1) Dfs(i, n - 1); } for (int j = 0; j < n; j++) { if (grid[0][j] == 1) Dfs(0, j); if (grid[m - 1][j] == 1) Dfs(m - 1, j); } int count = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { count++; } } } return count; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 343. Integer Break Сложность: medium Дано целое число n. Верните true, если оно является степенью числа четыре. В противном случае верните false. Целое число n является степенью числа четыре, если существует целое число x такое, что n == 4^x. Пример: Input: n = 2 Output: 1 Explanation: 2 = 1 + 1, 1 × 1 = 1. 👨‍💻 Алгоритм: 1⃣Инициализация и базовый случай: Создайте массив dp длиной n + 1, где dp[i] будет хранить максимальное произведение для числа i. Инициализируйте массив нулями. 2⃣Вычисление максимального произведения: Для каждого числа i от 2 до n: Для каждого числа j от 1 до i // 2: Обновите dp[i] как максимальное значение между текущим dp[i], произведением j и i - j, и произведением j и dp[i - j]. 3⃣Возврат результата: Верните значение dp[n], которое будет максимальным произведением для числа n. 😎 Решение: public class Solution { public int IntegerBreak(int n) { if (n <= 1) return 0; int[] dp = new int[n + 1]; for (int i = 2; i <= n; i++) { for (int j = 1; j <= i / 2; j++) { dp[i] = Math.Max(dp[i], Math.Max(j * (i - j), j * dp[i - j])); } } return dp[n]; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1013. Partition Array Into Three Parts With Equal Sum Сложность: easy Если задан массив целых чисел arr, верните true, если мы можем разбить массив на три непустые части с равными суммами. Формально, мы можем разбить массив, если можем найти индексы i + 1 < j с (arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1]) Пример: Input: arr = [0,2,1,-6,6,-7,9,1,2,0,1] Output: true 👨‍💻 Алгоритм: 1⃣Вычисление общей суммы: Вычислите общую сумму всех элементов массива. Если эта сумма не делится на 3 без остатка, вернуть false, так как невозможно разбить массив на три части с равной суммой. 2⃣Поиск первой и второй части: Итерируйте по массиву и ищите первую часть с суммой, равной одной трети от общей суммы. Продолжайте итерацию для поиска второй части с такой же суммой. Убедитесь, что между первой и второй частью есть хотя бы один элемент. 3⃣Проверка третьей части: Убедитесь, что оставшаяся часть массива также имеет ту же сумму, что и две найденные части. Если да, вернуть true, иначе false. 😎 Решение: public class Solution { public bool CanThreePartsEqualSum(int[] arr) { int totalSum = arr.Sum(); if (totalSum % 3 != 0) { return false; } int target = totalSum / 3, partSum = 0, count = 0, n = arr.Length; for (int i = 0; i < n; i++) { partSum += arr[i]; if (partSum == target) { count++; partSum = 0; if (count == 2 && i < n - 1) { return true; } } } return false; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1021. Remove Outermost Parentheses Сложность: easy Например, "", "()", "(" + A + ")" или A + B, где A и B - допустимые строки со скобками, а + означает объединение строк. Все допустимые строки со скобками - "", "()", "(())()" и "(()(())". Допустимая строка со скобками s является примитивной, если она непустая и не существует способа разбить ее на s = A + B, причем A и B - непустые допустимые строки со скобками. Если дана допустимая строка со скобками s, рассмотрим ее примитивное разложение: s = P1 + P2 + ... + Pk, где Pi - примитивные допустимые строки со скобками. Верните s после удаления крайних скобок из каждой примитивной строки в примитивном разложении s. Пример: Input: s = "(()())(())" Output: "()()()" 👨‍💻 Алгоритм: 1⃣Инициализация переменных: Создайте пустую строку для хранения результата. Используйте счетчик для отслеживания уровня вложенности скобок.. 2⃣Обработка строки: Итерируйте по каждому символу строки. Если встречаете (, увеличивайте счетчик уровня вложенности. Если уровень вложенности больше 1, добавьте ( в результат. Если встречаете ), уменьшайте счетчик уровня вложенности. Если уровень вложенности больше 0 перед уменьшением, добавьте ) в результат. 3⃣Возврат результата: Верните результат, содержащий строку без крайних скобок из каждой примитивной строки. 😎 Решение: public class Solution { public string RemoveOuterParentheses(string s) { var result = new StringBuilder(); int level = 0; foreach (char c in s) { if (c == '(') { if (level > 0) { result.Append(c); } level++; } else { level--; if (level > 0) { result.Append(c); } } } return result.ToString(); } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 994. Rotting Oranges Сложность: medium Дан m x n сетка, где каждая ячейка может иметь одно из трех значений: 0, представляющее пустую ячейку, 1, представляющее свежий апельсин, 2, представляющее гнилой апельсин. Каждую минуту любой свежий апельсин, который находится в 4-х направленно смежной ячейке с гнилым апельсином, становится гнилым. Верните минимальное количество минут, которые должны пройти, пока в ячейке не останется свежих апельсинов. Если это невозможно, верните -1. Пример: Input: grid = [[2,1,1],[0,1,1],[1,0,1]] Output: -1 Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally. 👨‍💻 Алгоритм: 1⃣Инициализация очереди и подсчет апельсинов: Пройдите по всей сетке, добавьте все гнилые апельсины в очередь и подсчитайте общее количество свежих апельсинов. Если нет свежих апельсинов, верните 0. 2⃣Использование BFS для распространения гнили: Выполняйте BFS, начиная с всех гнилых апельсинов, добавленных в очередь. Каждый раз, когда апельсин становится гнилым, уменьшайте счетчик свежих апельсинов. Если свежих апельсинов больше не осталось, верните текущее количество минут. 3⃣Проверка оставшихся свежих апельсинов: Если после завершения BFS все еще остаются свежие апельсины, верните -1. 😎 Решение: public class Solution { public int OrangesRotting(int[][] grid) { Queue<(int, int)> queue = new Queue<(int, int)>(); int freshCount = 0; int minutes = 0; int[][] directions = new int[][] { new int[] {0, 1}, new int[] {1, 0}, new int[] {0, -1}, new int[] {-1, 0} }; for (int i = 0; i < grid.Length; i++) { for (int j = 0; j < grid[0].Length; j++) { if (grid[i][j] == 2) { queue.Enqueue((i, j)); } else if (grid[i][j] == 1) { freshCount++; } } } if (freshCount == 0) return 0; while (queue.Count > 0) { int size = queue.Count; for (int i = 0; i < size; i++) { var (x, y) = queue.Dequeue(); foreach (var dir in directions) { int nx = x + dir[0], ny = y + dir[1]; if (nx >= 0 && nx < grid.Length && ny >= 0 && ny < grid[0].Length && grid[nx][ny] == 1) { grid[nx][ny] = 2; freshCount--; queue.Enqueue((nx, ny)); } } } if (queue.Count > 0) { minutes++; } } return freshCount == 0 ? minutes : -1; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 38. Count and Say Сложность: medium Последовательность "считай и скажи" (countAndSay) строится рекурсивно: - countAndSay(1) = "1" - countAndSay(n) — это кодирование длин серий из countAndSay(n - 1). Пример кодирования длин серий (RLE): - "3322251" → "23321511" Для заданного n верните n-й элемент последовательности. Пример: Input: n = 4 Output: "1211" 👨‍💻 Алгоритм: 1⃣Начать с s = "1". 2⃣Для каждого шага n-1 раз: - Пройти по s, группируя одинаковые символы. - Для каждой группы записать количество и сам символ. - Обновить s. 3⃣Вернуть итоговую строку. 😎 Решение: public class Solution { public string CountAndSay(int n) { string s = "1"; for (int i = 0; i < n - 1; i++) { StringBuilder current = new StringBuilder(); for (int j = 0; j < s.Length; j++) { int count = 1; while (j < s.Length - 1 && s[j] == s[j + 1]) { j++; count++; } current.Append(count).Append(s[j]); } s = current.ToString(); } return s; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1004. Max Consecutive Ones III Сложность: medium Если задан двоичный массив nums и целое число k, верните максимальное количество последовательных 1 в массиве, если можно перевернуть не более k 0. Пример: Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2 Output: 6 👨‍💻 Алгоритм: 1⃣Инициализация оконного подхода: Используйте два указателя для создания скользящего окна. Инициализируйте левый указатель в начале массива, правый указатель будет двигаться по массиву. Создайте переменную для подсчета количества нулей в текущем окне. 2⃣Перемещение правого указателя и обновление окна: Перемещайте правый указатель по массиву, обновляя количество нулей в текущем окне. Если количество нулей превышает k, сдвиньте левый указатель вправо до тех пор, пока количество нулей снова не станет допустимым (меньше или равно k). 3⃣Подсчет максимального количества последовательных единиц: На каждом шаге обновляйте максимальное количество последовательных единиц, сравнивая текущую длину окна (разница между правым и левым указателями) с текущим максимумом. 😎 Решение: public class Solution { public int LongestOnes(int[] nums, int k) { int left = 0, maxOnes = 0, zeroCount = 0; for (int right = 0; right < nums.Length; right++) { if (nums[right] == 0) { zeroCount++; } while (zeroCount > k) { if (nums[left] == 0) { zeroCount--; } left++; } maxOnes = Math.Max(maxOnes, right - left + 1); } return maxOnes; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1137. N-th Tribonacci Number Сложность: easy Трибоначчи последовательность Tn определяется следующим образом: T0 = 0, T1 = 1, T2 = 1, и Tn+3 = Tn + Tn+1 + Tn+2 для n >= 0. Дано n, вернуть значение Tn. Пример: Input: n = 4 Output: 4 Explanation: T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4 👨‍💻 Алгоритм: 1⃣Если n < 3, вернуть значение n-го терма, как указано в описании задачи. 2⃣Инициализировать a, b и c как базовые случаи. Установить a = 0, b = 1, c = 1. 3⃣Для следующих n - 2 шагов обновлять a, b, c следующим образом: a = b, b = c, c = a + b + c. Вернуть c. 😎 Решение: public class Solution { public int Tribonacci(int n) { if (n < 3) { return n > 0 ? 1 : 0; } int a = 0, b = 1, c = 1; for (int i = 0; i < n - 2; ++i) { int tmp = a + b + c; a = b; b = c; c = tmp; } return c; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 763. Partition Labels Сложность: medium Вам дана строка s. Мы хотим разбить строку на как можно больше частей так, чтобы каждая буква встречалась не более чем в одной части. Обратите внимание, что разбиение выполняется так, чтобы после конкатенации всех частей по порядку получилась строка s. Верните список целых чисел, представляющих размер этих частей. Пример: Input: s = "ababcbacadefegdehijhklij" Output: [9,7,8] 👨‍💻 Алгоритм: 1⃣Создайте словарь для хранения последней позиции каждой буквы в строке. 2⃣Пройдите по строке, отслеживая максимальную позицию текущей части. 3⃣Когда текущая позиция совпадает с максимальной позицией, завершите часть и начните новую. 😎 Решение: using System; using System.Collections.Generic; public class Solution { public IList<int> PartitionLabels(string s) { int[] lastPos = new int[26]; for (int i = 0; i < s.Length; i++) { lastPos[s[i] - 'a'] = i; } List<int> partitions = new List<int>(); int j = 0, anchor = 0; for (int i = 0; i < s.Length; i++) { j = Math.Max(j, lastPos[s[i] - 'a']); if (i == j) { partitions.Add(i - anchor + 1); anchor = i + 1; } } return partitions; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 565. Array Nesting Сложность: medium Дан массив целых чисел nums длиной n, где nums является перестановкой чисел в диапазоне [0, n - 1]. Вы должны построить множество s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], ...} при соблюдении следующего правила: Первый элемент в s[k] начинается с выбора элемента nums[k] с индексом k. Следующий элемент в s[k] должен быть nums[nums[k]], затем nums[nums[nums[k]]], и так далее. Мы прекращаем добавлять элементы непосредственно перед тем, как в s[k] появится дубликат. Верните длину самого длинного множества s[k]. Пример: Input: nums = [5,4,0,3,1,6,2] Output: 4 Explanation: nums[0] = 5, nums[1] = 4, nums[2] = 0, nums[3] = 3, nums[4] = 1, nums[5] = 6, nums[6] = 2. One of the longest sets s[k]: s[0] = {nums[0], nums[5], nums[6], nums[2]} = {5, 6, 2, 0} 👨‍💻 Алгоритм: 1⃣Создайте массив для отслеживания посещенных элементов. 2⃣Для каждого элемента в nums, если он не посещен, начните формирование множества s[k], последовательно переходя по элементам, пока не встретится уже посещенный элемент. 3⃣Обновите максимальную длину найденного множества. 😎 Решение: public class Solution { public int ArrayNesting(int[] nums) { bool[] visited = new bool[nums.Length]; int maxLength = 0; for (int i = 0; i < nums.Length; i++) { if (!visited[i]) { int start = i; int count = 0; while (!visited[start]) { visited[start] = true; start = nums[start]; count++; } maxLength = Math.Max(maxLength, count); } } return maxLength; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 997. Find the Town Judge Сложность: easy В городе есть n человек, помеченных от 1 до n. Ходят слухи, что один из этих людей тайно является городским судьей. Если городской судья существует, то: городской судья никому не доверяет. Все (кроме городского судьи) доверяют городскому судье. Существует ровно один человек, удовлетворяющий свойствам 1 и 2. Вам дан массив trust, где trust[i] = [ai, bi], представляющий, что человек, помеченный ai, доверяет человеку, помеченному bi. Если в массиве trust не существует доверительных отношений, то таких отношений не существует. Верните метку городского судьи, если городской судья существует и может быть идентифицирован, или верните -1 в противном случае. Пример: Input: n = 2, trust = [[1,2]] Output: 2 👨‍💻 Алгоритм: 1⃣Создание счетчиков доверия: Инициализируйте массив для подсчета количества людей, которым доверяет каждый человек, и массив для подсчета количества людей, которые доверяют каждому человеку. 2⃣Подсчет доверия: Пройдитесь по каждому элементу в массиве trust и обновите счетчики: увеличьте количество доверий для того, кто доверяет, и увеличьте количество доверенных людей для того, кому доверяют. 3⃣Проверка условий судьи: Пройдитесь по массиву людей и найдите того, кто никому не доверяет (количество доверий равно 0) и кому доверяют все остальные (количество доверенных людей равно n-1). Верните метку этого человека. Если такого человека нет, верните -1. 😎 Решение: public class Solution { public int FindJudge(int n, int[][] trust) { if (trust.Length == 0 && n == 1) { return 1; } int[] trustCount = new int[n + 1]; int[] trustedBy = new int[n + 1]; foreach (var t in trust) { trustCount[t[0]]++; trustedBy[t[1]]++; } for (int i = 1; i <= n; i++) { if (trustCount[i] == 0 && trustedBy[i] == n - 1) { return i; } } return -1; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1669. Merge In Between Linked Lists Сложность: medium Вам даны два связанных списка: list1 и list2 размером n и m соответственно. Удалите узлы list1 с ath узла по bth узел и вставьте на их место list2. Синие ребра и узлы на рисунке в вверху поста указывают на результат: Пример: Input: list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002] Output: [10,1,13,1000000,1000001,1000002,5] Explanation: We remove the nodes 3 and 4 and put the entire list2 in their place. The blue edges and nodes in the above figure indicate the result. 👨‍💻 Алгоритм: 1⃣Инициализация и добавление узлов из list1 до узла a в массив: Инициализировать переменную index равную 0 и current1 равную list1. Пока index меньше a, добавлять current1.val в массив mergeArray, перемещаться к следующему узлу current1.next и увеличивать index. 2⃣Добавление узлов из list2 в массив: Инициализировать current2 равную list2. Пока current2 не равен null, добавлять current2.val в mergeArray и перемещаться к следующему узлу current2.next. 3⃣Добавление узлов из list1 от узла b + 1 до конца в массив и создание нового связанного списка: Найти узел на позиции b + 1, перемещая current1 и увеличивая index, пока index меньше b + 1. Добавлять узлы из current1 в массив, пока current1 не станет null. Создать новый связанный список из значений в mergeArray, добавляя узлы в начало списка и возвращая его. 😎 Решение: public class Solution { public ListNode MergeInBetween(ListNode list1, int a, int b, ListNode list2) { var mergeArray = new List<int>(); int index = 0; var current1 = list1; while (index < a) { mergeArray.Add(current1.val); current1 = current1.next; index++; } var current2 = list2; while (current2 != null) { mergeArray.Add(current2.val); current2 = current2.next; } while (index < b + 1) { current1 = current1.next; index++; } while (current1 != null) { mergeArray.Add(current1.val); current1 = current1.next; } ListNode resultList = null; for (int i = mergeArray.Count - 1; i >= 0; i--) { resultList = new ListNode(mergeArray[i], resultList); } return resultList; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1002. Find Common Characters Сложность: easy Если задан массив строк words, верните массив всех символов, которые встречаются во всех строках внутри слов (включая дубликаты). Вы можете вернуть ответ в любом порядке. Пример: Input: words = ["bella","label","roller"] Output: ["e","l","l"] 👨‍💻 Алгоритм: 1⃣Инициализация частотного массива: Создайте массив для хранения минимальной частоты каждого символа, который будет встречаться во всех словах. 2⃣Обработка каждого слова: Для каждого слова создайте временный массив для хранения частоты каждого символа в этом слове. Обновите основной частотный массив, сравнивая его с временным массивом и сохраняя минимальные частоты каждого символа. 3⃣Формирование результата: Создайте результирующий массив, добавляя каждый символ столько раз, сколько его минимальная частота. 😎 Решение: public class Solution { public IList<string> CommonChars(string[] words) { int[] minFreq = new int[26]; Array.Fill(minFreq, int.MaxValue); foreach (string word in words) { int[] freq = new int[26]; foreach (char c in word) { freq[c - 'a']++; } for (int i = 0; i < 26; i++) { minFreq[i] = Math.Min(minFreq[i], freq[i]); } } IList<string> result = new List<string>(); for (int i = 0; i < 26; i++) { for (int j = 0; j < minFreq[i]; j++) { result.Add(((char)('a' + i)).ToString()); } } return result; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 784. Letter Case Permutation Сложность: medium Дан корень дерева поиска (BST). Верните минимальную разницу между значениями любых двух различных узлов в дереве. Пример: Input: s = "a1b2" Output: ["a1b2","a1B2","A1b2","A1B2"] 👨‍💻 Алгоритм: 1⃣Если следующий символ c является буквой, то мы удвоим все слова в нашем текущем ответе, и добавим lowercase(c) к каждому слову в первой половине, и uppercase(c) к каждому слову во второй половине. 2⃣Если c является цифрой, мы добавим его к каждому слову. 3⃣Продолжайте процесс для всех символов в строке, чтобы получить все возможные комбинации. 😎 Решение: public class Solution { public IList<string> LetterCasePermutation(string S) { var ans = new List<List<char>> { new List<char>() }; foreach (var c in S) { int n = ans.Count; if (char.IsLetter(c)) { for (int i = 0; i < n; i++) { var current = new List<char>(ans[i]); ans.Add(current); ans[i].Add(char.ToLower(c)); ans[n + i].Add(char.ToUpper(c)); } } else { for (int i = 0; i < n; i++) { ans[i].Add(c); } } } return ans.Select(list => new string(list.ToArray())).ToList(); } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 340. Longest Substring with At Most K Distinct Characters Сложность: medium Дана строка s и целое число k. Верните длину самой длинной подстроки s, которая содержит не более k различных символов. Пример: Input: n = 27 Output: true Explanation: 27 = 3^3 👨‍💻 Алгоритм: 1⃣Инициализация Используйте два указателя (left и right) для отслеживания текущего окна в строке. Создайте словарь для отслеживания количества каждого символа в текущем окне. Инициализируйте переменные для хранения максимальной длины подстроки (max_length). 2⃣Раздвижение окна Перемещайте правый указатель (right) по строке и обновляйте словарь. Если количество различных символов в словаре превышает k, перемещайте левый указатель (left) вправо, уменьшая счетчик символов, пока количество различных символов снова не станет меньше или равно k. 3⃣Обновление максимальной длины На каждом шаге проверяйте и обновляйте максимальную длину подстроки, если текущее окно содержит не более k различных символов. В конце верните максимальную длину подстроки. 😎 Решение: public class Solution { public int LengthOfLongestSubstringKDistinct(string s, int k) { int left = 0; int right = 0; Dictionary<char, int> charCount = new Dictionary<char, int>(); int maxLength = 0; while (right < s.Length) { if (!charCount.ContainsKey(s[right])) { charCount[s[right]] = 0; } charCount[s[right]]++; while (charCount.Count > k) { charCount[s[left]]--; if (charCount[s[left]] == 0) { charCount.Remove(s[left]); } left++; } maxLength = Math.Max(maxLength, right - left + 1); right++; } return maxLength; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 393. UTF-8 Validation Сложность: medium Дан целочисленный массив data, представляющий данные, верните, является ли это допустимой UTF-8 кодировкой (т.е. переводится в последовательность допустимых UTF-8 закодированных символов). Символ в UTF-8 может быть от 1 до 4 байтов в длину, при этом соблюдаются следующие правила: Для 1-байтового символа первый бит — 0, за которым следует его Unicode код. Для n-байтового символа первые n битов — все единицы, (n + 1)-й бит — 0, за которыми следуют n - 1 байт с наиболее значимыми 2 битами, равными 10. Это работает следующим образом: Количество байтов | UTF-8 Октетная последовательность | (бинарная) --------------------+----------------------------------------- 1 | 0xxxxxxx 2 | 110xxxxx 10xxxxxx 3 | 1110xxxx 10xxxxxx 10xxxxxx 4 | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx x обозначает бит в бинарной форме байта, который может быть как 0, так и 1. Примечание: Вход представляет собой массив целых чисел. Используются только 8 младших значимых битов каждого целого числа. Это означает, что каждое целое число представляет только 1 байт данных. Пример: Input: data = [197,130,1] Output: true Explanation: data represents the octet sequence: 11000101 10000010 00000001. It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character. 👨‍💻 Алгоритм: 1⃣Начните обработку целых чисел в данном массиве одно за другим. Для каждого целого числа получите его двоичное представление в виде строки. Поскольку целые числа могут быть очень большими, следует учитывать только 8 младших значимых битов данных и отбросить остальные, как указано в условии задачи. После этого шага у вас должно быть 8-битное или 1-байтовое строковое представление целого числа. Назовем эту строку bin_rep. 2⃣Далее нужно рассмотреть два сценария. Первый — мы находимся в процессе обработки некоторого UTF-8 закодированного символа. В этом случае нужно просто проверить первые два бита строки и посмотреть, равны ли они "10", т.е. наиболее значимые два бита целого числа равны 1 и 0. bin_rep[:2] == "10". Второй сценарий — мы уже обработали несколько допустимых UTF-8 символов и должны начать обработку нового UTF-8 символа. В этом случае нужно посмотреть на префикс строкового представления и посчитать количество единиц, которые мы встречаем до первой нули. Это скажет нам, каков размер следующего UTF-8 символа. 3⃣Продолжайте обрабатывать целые числа массива таким образом, пока не обработаете их все или не обнаружите недопустимый сценарий. Теперь давайте перейдем к реализации этого алгоритма. 😎 Решение: public class Solution { public bool ValidUtf8(int[] data) { int nBytes = 0; foreach (int num in data) { string binRep = Convert.ToString(num, 2).PadLeft(8, '0').Substring(0, 8); if (nBytes == 0) { foreach (char bit in binRep) { if (bit == '0') break; nBytes++; } if (nBytes == 0) continue; if (nBytes == 1 || nBytes > 4) return false; } else { if (!(binRep[0] == '1' && binRep[1] == '0')) return false; } nBytes--; } return nBytes == 0; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1325. Delete Leaves With a Given Value Сложность: medium Дано корневое дерево root и целое число target. Удалите все листовые узлы со значением target. Обратите внимание, что после удаления листового узла со значением target, если его родительский узел становится листовым узлом и имеет значение target, он также должен быть удален (необходимо продолжать делать это, пока это возможно). Пример: Input: root = [1,2,3,2,null,2,4], target = 2 Output: [1,null,3,null,4] Explanation: Leaf nodes in green with value (target = 2) are removed (Picture in left). After removing, new nodes become leaf nodes with value (target = 2) (Picture in center). 👨‍💻 Алгоритм: 1⃣Базовый случай: Если root равен null, верните null, чтобы обработать условия пустого дерева или прохождения за пределы листовых узлов. 2⃣Рекурсивный обход: Выполните обход в постфиксном порядке, чтобы гарантировать обработку всех потомков перед текущим узлом (root): — Рекурсивно вызовите removeLeafNodes для левого дочернего узла root и обновите левый дочерний узел возвращаемым значением. — Аналогично, рекурсивно вызовите removeLeafNodes для правого дочернего узла root и обновите правый дочерний узел возвращаемым значением. 3⃣Оценка узла: — Проверьте, является ли текущий узел root листовым узлом и совпадает ли его значение с target. Если оба условия выполнены, верните null, чтобы эффективно удалить узел, не присоединяя его к родителю. — Если узел не является листом или не совпадает с target, верните сам root. 😎 Решение: public class Solution { public TreeNode RemoveLeafNodes(TreeNode root, int target) { if (root == null) { return null; } root.left = RemoveLeafNodes(root.left, target); root.right = RemoveLeafNodes(root.right, target); if (root.left == null && root.right == null && root.val == target) { return null; } return root; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 957. Prison Cells After N Days Сложность: medium Есть 8 тюремных камер в ряду, и каждая камера либо занята, либо пуста. Каждый день статус камеры, занята она или пуста, меняется по следующим правилам: Если у камеры два соседних соседа, которые оба заняты или оба пусты, то камера становится занятой. В противном случае, она становится пустой. Учтите, что поскольку тюрьма — это ряд, у первой и последней камер в ряду не может быть двух соседних соседей. Вам дан целочисленный массив cells, где cells[i] == 1, если i-я камера занята, и cells[i] == 0, если i-я камера пуста, и вам дано целое число n. Верните состояние тюрьмы после n дней (т.е. после n таких изменений, описанных выше). Пример: Input: cells = [0,1,0,1,1,0,0,1], n = 7 Output: [0,0,1,1,0,0,0,0] Explanation: The following table summarizes the state of the prison on each day: Day 0: [0, 1, 0, 1, 1, 0, 0, 1] Day 1: [0, 1, 1, 0, 0, 0, 0, 0] Day 2: [0, 0, 0, 0, 1, 1, 1, 0] Day 3: [0, 1, 1, 0, 0, 1, 0, 0] Day 4: [0, 0, 0, 0, 0, 1, 0, 0] Day 5: [0, 1, 1, 1, 0, 1, 0, 0] Day 6: [0, 0, 1, 0, 1, 1, 0, 0] Day 7: [0, 0, 1, 1, 0, 0, 0, 0] 👨‍💻 Алгоритм: 1⃣Преобразуйте текущее состояние камер в целое число с помощью битовой маски. Это позволит удобно отслеживать повторяющиеся состояния. 2⃣Симулируйте изменение состояния камер день за днем, записывая каждое состояние в хэш-таблицу. Если обнаруживается повторяющееся состояние, вычислите длину цикла и уменьшите количество оставшихся дней с учетом этого цикла. 3⃣Продолжайте симуляцию, пока не достигнете заданного числа дней, либо используйте цикл для ускорения процесса. 😎 Решение: public class Solution { protected int CellsToBitmap(int[] cells) { int stateBitmap = 0; foreach (int cell in cells) { stateBitmap = (stateBitmap << 1) | cell; } return stateBitmap; } protected int[] NextDay(int[] cells) { int[] newCells = new int[cells.Length]; for (int i = 1; i < cells.Length - 1; ++i) { newCells[i] = (cells[i - 1] == cells[i + 1]) ? 1 : 0; } return newCells; } public int[] PrisonAfterNDays(int[] cells, int N) { Dictionary<int, int> seen = new Dictionary<int, int>(); bool isFastForwarded = false; while (N > 0) { if (!isFastForwarded) { int stateBitmap = CellsToBitmap(cells); if (seen.ContainsKey(stateBitmap)) { N %= seen[stateBitmap] - N; isFastForwarded = true; } else { seen[stateBitmap] = N; } } if (N > 0) { N--; cells = NextDay(cells); } } return cells; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 146. LRU Cache Сложность: medium Реализуйте класс LRUCache: LRUCache(int capacity) - инициализирует LRU-кэш с положительным размером capacity. int get(int key) - возвращает значение по ключу, если ключ существует, в противном случае возвращает -1. void put(int key, int value) - обновляет значение по ключу, если ключ существует. В противном случае добавляет пару ключ-значение в кэш. Если количество ключей превышает установленную емкость после этой операции, удаляет наименее недавно использованный ключ. Функции get и put должны выполняться за среднее время O(1). Пример: Input ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] Output [null, null, null, 1, null, -1, null, -1, 3, 4] 👨‍💻 Алгоритм: 1⃣Метод добавления узла в конец связного списка (add): Получите текущий узел в конце списка, это "реальный" хвост: tail.prev, обозначим его как previousEnd. Вставьте node после previousEnd, установив previousEnd.next = node. Настройте указатели узла: node.prev = previousEnd и node.next = tail. Обновите tail.prev = node, делая node новым "реальным" хвостом списка. 2⃣Метод удаления узла из связного списка (remove): Узел node должен быть удален из списка. Для этого определите узлы nextNode = node.next и prevNode = node.prev. Чтобы удалить node, переназначьте prevNode.next = nextNode и nextNode.prev = prevNode, эффективно исключая node из списка. Это превратит, например, последовательность A <-> B <-> C в A <-> C, где prevNode = A и nextNode = C. 3⃣Методы get и put: get(int key): Проверьте, существует ли ключ в хэш-карте. Если нет, верните -1. Иначе, получите узел, связанный с ключом, переместите его в конец списка с помощью remove(node) и add(node). Верните node.val. put(int key, int value): Если ключ уже существует, найдите соответствующий узел и удалите его методом remove. Создайте новый узел с key и value, добавьте его в хэш-карту и в конец списка методом add(node). Если размер кэша превышает установленную емкость после добавления, удалите самый редко используемый узел (который находится в голове списка после фиктивного узла head), затем удалите соответствующий ключ из хэш-карты. 😎 Решение: public class Node { public int key { get; set; } public int value { get; set; } public Node next { get; set; } public Node prev { get; set; } public Node(int key, int value) { this.key = key; this.value = value; } } public class LRUCache { private int capacity; private Dictionary<int, Node> dic; private Node head; private Node tail; public LRUCache(int capacity) { this.capacity = capacity; dic = new Dictionary<int, Node>(); head = new Node(-1, -1); tail = new Node(-1, -1); head.next = tail; tail.prev = head; } public int Get(int key) { if (!dic.ContainsKey(key)) { return -1; } Node node = dic[key]; Remove(node); Add(node); return node.value; } public void Put(int key, int value) { if (dic.ContainsKey(key)) { Node oldNode = dic[key]; Remove(oldNode); } Node node = new Node(key, value); dic[key] = node; Add(node); if (dic.Count > capacity) { Node nodeToDelete = head.next; Remove(nodeToDelete); dic.Remove(nodeToDelete.key); } } private void Add(Node node) { Node previousEnd = tail.prev; previousEnd.next = node; node.prev = previousEnd; node.next = tail; tail.prev = node; } private void Remove(Node node) { node.prev.next = node.next; node.next.prev = node.prev; } } Ставь 👍 и забирай 📚 Базу знаний