tgindex

C# | LeetCode

описание

Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv

← к каналу@easy_c_sharp_task
3 221
подписчиков
Охват к подписчикам
6,2%
ERR
Реакции к просмотрам
0,09%
5 на 26 постов
Пересылки к просмотрам
0,09%
5
Постов в день
1,3
всего 26

Где отзываются чаще

доля реакций к просмотрам
  • 13 авг.Задача: 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; } } Ставь 👍 и забирай 📚 Базу знаний0,62%
  • 14 авг.Задача: 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]; } } Ставь 👍 и забирай 📚 Базу знаний0,58%
  • 6 авг.Задача: 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; } } Ставь 👍 и забирай 📚 Базу знаний0,53%
  • 7 авг.Задача: 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; } } Ставь 👍 и забирай 📚 Базу знаний0,50%
  • 5 авг.Задача: 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; } } Ставь 👍 и забирай 📚 Базу знаний0,46%
  • 11:06Задача: 839. Similar String Groups Сложность: hard Две строки, X и Y, считаются похожими, если либо они идентичны, либо мы можем сделать их эквивалентными, поменяв местами не более двух букв (в разных позициях) в строке X. Например, "tars" и "rats" похожи (замена на позициях 0 и 2), и "rats" и "arts" похожи, но "star" не похожа на "tars", "rats" или "arts". Эти строки образуют две связанные группы по сходству: {"tars", "rats", "arts"} и {"star"}. Обратите внимание, что "tars" и "arts" находятся в одной группе, хотя они не похожи друг на друга. Формально, каждая группа такова, что слово находится в группе, если и только если оно похоже хотя бы на одно другое слово в группе. Вам дан список строк strs, где каждая строка в списке является анаграммой каждой другой строки в списке. Сколько групп существует? Пример: Input: strs = ["tars","rats","arts","star"] Output: 2 👨‍💻 Алгоритм: 1⃣Создайте переменную n, хранящую количество слов в strs, и создайте экземпляр UnionFind размера n. 2⃣Для любых двух слов на индексах i и j, которые ведут себя как узлы, проверьте, являются ли слова strs[i] и strs[j] похожими, и выполните операции find и union для объединения различных компонентов в один, если слова похожи. 3⃣Верните количество оставшихся групп. 😎 Решение: public class UnionFind { private int[] parent; private int[] rank; public UnionFind(int size) { parent = new int[size]; rank = new int[size]; for (int i = 0; i < size; ++i) { parent[i] = i; } } public int Find(int x) { if (parent[x] != x) { parent[x] = Find(parent[x]); } return parent[x]; } public void Union(int x, int y) { int rootX = Find(x); int rootY = Find(y); if (rootX != rootY) { if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else { parent[rootY] = rootX; rank[rootX]++; } } } } public class Solution { public bool IsSimilar(string a, string b) { int diff = 0; for (int i = 0; i < a.Length; ++i) { if (a[i] != b[i]) { diff++; } } return diff == 0 || diff == 2; } public int NumSimilarGroups(string[] strs) { int n = strs.Length; UnionFind dsu = new UnionFind(n); int count = n; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (IsSimilar(strs[i], strs[j]) && dsu.Find(i) != dsu.Find(j)) { count--; dsu.Union(i, j); } } } return count; } } Ставь 👍 и забирай 📚 Базу знаний0,00%
  • 16 авг.Задача: 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; } } Ставь 👍 и забирай 📚 Базу знаний0,00%
  • 15 авг.Задача: 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; } } Ставь 👍 и забирай 📚 Базу знаний0,00%
  • 13 авг.Задача: 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(); } } Ставь 👍 и забирай 📚 Базу знаний0,00%
  • 12 авг.Задача: 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; } } Ставь 👍 и забирай 📚 Базу знаний0,00%
  • 11 авг.Задача: 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; } } Ставь 👍 и забирай 📚 Базу знаний0,00%
  • 11 авг.Задача: 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; } } Ставь 👍 и забирай 📚 Базу знаний0,00%