C# | LeetCode

Задача: 278. First Bad Version Сложность: easy Вы являетесь менеджером продукта и в настоящее время возглавляете команду по разработке нового продукта. К сожалению, последняя версия вашего продукта не прошла проверку качества. Поскольку каждая версия разрабатывается на основе предыдущей версии, все версии, вышедшие после плохой версии, также оказываются плохими. Предположим, у вас есть n версий [1, 2, ..., n], и вы хотите выяснить первую плохую версию, которая вызывает все последующие версии быть плохими. Вам предоставлен API bool isBadVersion(version), который возвращает, является ли версия плохой. Реализуйте функцию для нахождения первой плохой версии. Вы должны минимизировать количество вызовов API. Пример: Input: n = 5, bad = 4 Output: 4 Explanation: call isBadVersion(3) -> false call isBadVersion(5) -> true call isBadVersion(4) -> true Then 4 is the first bad version. 👨‍💻 Алгоритм: 1⃣Инициализация границ поиска: Устанавливаем начальные значения левой и правой границ поиска: left = 1 и right = n. 2⃣Бинарный поиск: Пока левая граница меньше правой, находим среднюю точку mid и проверяем, является ли она плохой версией с помощью isBadVersion(mid). Если текущая версия mid плохая, смещаем правую границу к mid, иначе смещаем левую границу на mid + 1. 3⃣Возврат результата: Когда левая граница станет равной правой, возвращаем left как индекс первой плохой версии. 😎 Решение: public class Solution { public int FirstBadVersion(int n) { int left = 1, right = n; while (left < right) { int mid = left + (right - left) / 2; if (IsBadVersion(mid)) { right = mid; } else { left = mid + 1; } } return left; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1323. Maximum 69 Number Сложность: easy Дано положительное целое число num, состоящее только из цифр 6 и 9. Верните максимальное число, которое можно получить, изменив не более одной цифры (6 становится 9, а 9 становится 6). Пример: Input: num = 9669 Output: 9969 Explanation: Changing the first digit results in 6669. Changing the second digit results in 9969. Changing the third digit results in 9699. Changing the fourth digit results in 9666. The maximum number is 9969. 👨‍💻 Алгоритм: 1⃣Преобразуйте входное целое число num в итерируемый и изменяемый объект num_obj. 2⃣Пройдитесь по num_obj и, если найдете цифру 6, замените её на 9 и прекратите итерацию. 3⃣Верните целое число, преобразованное из измененного num_obj. 😎 Решение: public class Solution { public int Maximum69Number (int num) { char[] numArr = num.ToString().ToCharArray(); for (int i = 0; i < numArr.Length; i++) { if (numArr[i] == '6') { numArr[i] = '9'; break; } } return int.Parse(new string(numArr)); } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 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; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 600. Non-negative Integers without Consecutive Ones Сложность: hard Дано положительное целое число n, верните количество чисел в диапазоне [0, n], бинарные представления которых не содержат последовательных единиц. Пример: Input: n = 5 Output: 5 Explanation: Here are the non-negative integers <= 5 with their corresponding binary representations: 0 : 0 1 : 1 2 : 10 3 : 11 4 : 100 5 : 101 Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule. 👨‍💻 Алгоритм: 1⃣Простой метод заключается в переборе всех чисел от 1 до num. Для каждого текущего выбранного числа проверяем все соседние позиции, чтобы выяснить, содержит ли число две последовательные единицы. Если не содержит, увеличиваем количество чисел без последовательных единиц. 2⃣Чтобы проверить, существует ли 1 на позиции x (считая от младшего значащего бита), в текущем числе n, поступаем следующим образом. Сдвигаем двоичную 1 x−1 раз влево, чтобы получить число y, которое имеет 1 только на x-й позиции. Логическое И числа n и y даст результат 1 только если n содержит 1 на позиции x. 3⃣В конце подсчитываем и возвращаем количество чисел в диапазоне [0, n], не содержащих последовательных единиц. 😎 Решение: public class Solution { public int FindIntegers(int num) { int count = 0; for (int i = 0; i <= num; i++) { if (Check(i)) { count++; } } return count; } public bool Check(int n) { int i = 31; while (i > 0) { if ((n & (1 << i)) != 0 && (n & (1 << (i - 1))) != 0) { return false; } i--; } return true; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 787. Cheapest Flights Within K Stops Сложность: medium Есть n городов, соединенных некоторым количеством рейсов. Вам дан массив flights, где flights[i] = [fromi, toi, pricei] указывает на то, что существует рейс из города fromi в город toi с ценой pricei. Также даны три целых числа src, dst и k. Верните самую дешевую цену от src до dst с не более чем k остановками. Если такого маршрута нет, верните -1. Пример: Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1 Output: 700 Explanation: The graph is shown above. The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700. Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops. 👨‍💻 Алгоритм: 1⃣Создайте список смежности, где adj[X] содержит всех соседей узла X и соответствующую цену, которую нужно заплатить, чтобы перейти к соседу. Инициализируйте массив dist, хранящий минимальную цену для достижения узла из узла src. Инициализируйте его большими значениями. Инициализируйте очередь, хранящую пары {node, distance}. Изначально очередь должна содержать только {src, 0}. Создайте переменную stops и установите ее значение равным 0. 2⃣Выполняйте поиск в ширину (BFS), пока очередь не станет пустой или пока stops > k. Итерируйте по всем узлам на определенном уровне. Это будет сделано путем запуска вложенного цикла и посещения всех узлов, которые в данный момент находятся в очереди. В каждой паре {node, distance} итерируйте по всем соседям узла. Для каждого соседа проверьте, меньше ли dist[neighbor] чем distance + цена ребра. Если это так, обновите dist[neighbor] и добавьте {neighbor, dist[neighbor]} в очередь. 3⃣После итерации по всем узлам на текущем уровне увеличьте stops на один. Мы посетили все узлы на определенном уровне и готовы посетить следующий уровень узлов. Когда мы достигнем условия, при котором либо очередь станет пустой, либо stops == k, у нас будет наш ответ в dist[dst]. Если dist[dst] не изменилось с начального большого значения, значит, мы никогда не достигли его, и следует вернуть -1. 😎 Решение: using System; using System.Collections.Generic; public class Solution { public int FindCheapestPrice(int n, int[][] flights, int src, int dst, int k) { var adj = new List<(int, int)>[n]; for (int i = 0; i < n; i++) adj[i] = new List<(int, int)>(); foreach (var flight in flights) { adj[flight[0]].Add((flight[1], flight[2])); } var dist = new int[n]; Array.Fill(dist, int.MaxValue); var q = new Queue<(int node, int distance)>(); q.Enqueue((src, 0)); int stops = 0; while (stops <= k && q.Count > 0) { int sz = q.Count; for (int i = 0; i < sz; i++) { var (node, distance) = q.Dequeue(); foreach (var (neighbour, price) in adj[node]) { if (price + distance >= dist[neighbour]) continue; dist[neighbour] = price + distance; q.Enqueue((neighbour, dist[neighbour])); } } stops++; } return dist[dst] == int.MaxValue ? -1 : dist[dst]; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1197. Minimum Knight Moves Сложность: medium На бесконечной шахматной доске с координатами от -бесконечности до +бесконечности у вас есть конь на клетке [0, 0]. У коня есть 8 возможных ходов. Каждый ход представляет собой два квадрата в кардинальном направлении, затем один квадрат в ортогональном направлении. Верните минимальное количество шагов, необходимых для перемещения коня на клетку [x, y]. Гарантируется, что ответ существует. Пример: Input: x = 5, y = 5 Output: 4 Explanation: [0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5] 👨‍💻 Алгоритм: 1⃣Инициализация структур данных: Инициализируйте две очереди для хранения координат и расстояний: одну для движения от начальной точки, другую — от конечной точки. Инициализируйте две карты для хранения посещенных координат и расстояний: одну для движения от начальной точки, другую — от конечной точки. 2⃣Реализация двунаправленного поиска в ширину (BFS): Выполняйте шаги из очередей, расширяя круги поиска как от начальной, так и от конечной точки. Если круги пересекаются, возвращайте сумму расстояний до точки пересечения. 3⃣ Расширение кругов поиска: Для каждой текущей точки из очередей расширяйте круг поиска по всем возможным ходам коня. Обновляйте расстояния и добавляйте новые точки в очереди, если они еще не были посещены. Увеличивайте units на значение, извлеченное из кучи. 😎 Решение: public class Solution { public int MinKnightMoves(int x, int y) { int[][] offsets = new int[][] { new int[] {1, 2}, new int[] {2, 1}, new int[] {2, -1}, new int[] {1, -2}, new int[] {-1, -2}, new int[] {-2, -1}, new int[] {-2, 1}, new int[] {-1, 2} }; var originQueue = new Queue<int[]>(); originQueue.Enqueue(new int[] {0, 0, 0}); var originDistance = new Dictionary<string, int> {{"0,0", 0}}; var targetQueue = new Queue<int[]>(); targetQueue.Enqueue(new int[] {x, y, 0}); var targetDistance = new Dictionary<string, int> {{$"{x},{y}", 0}}; while (true) { var origin = originQueue.Dequeue(); var originKey = $"{origin[0]},{origin[1]}"; if (targetDistance.ContainsKey(originKey)) { return origin[2] + targetDistance[originKey]; } var target = targetQueue.Dequeue(); var targetKey = $"{target[0]},{target[1]}"; if (originDistance.ContainsKey(targetKey)) { return target[2] + originDistance[targetKey]; } foreach (var offset in offsets) { var nextOrigin = new int[] {origin[0] + offset[0], origin[1] + offset[1], origin[2] + 1}; var nextOriginKey = $"{nextOrigin[0]},{nextOrigin[1]}"; if (!originDistance.ContainsKey(nextOriginKey)) { originQueue.Enqueue(nextOrigin); originDistance[nextOriginKey] = nextOrigin[2]; } var nextTarget = new int[] {target[0] + offset[0], target[1] + offset[1], target[2] + 1}; var nextTargetKey = $"{nextTarget[0]},{nextTarget[1]}"; if (!targetDistance.ContainsKey(nextTargetKey)) { targetQueue.Enqueue(nextTarget); targetDistance[nextTargetKey] = nextTarget[2]; } } } } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 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; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 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; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 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; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 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; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 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; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 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(); } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 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; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 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; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 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; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 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; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 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]; } } Ставь 👍 и забирай 📚 Базу знаний