C# | LeetCode
الذهاب إلى القناة على Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
إظهار المزيد
الشبكة:3 206
المشتركون
-124 ساعات
-117 أيام
-3630 أيام
أرشيف المشاركات
3 206
Задача: 1028. Recover a Tree From Preorder Traversal
Сложность: hard
Мы запускаем предварительный поиск в глубину (DFS) на корне двоичного дерева. На каждый узел в этом обходе мы выводим D тире (где D - глубина этого узла), а затем выводим значение этого узла.Если глубина узла равна D, то глубина его ближайшего потомка равна D + 1.Глубина корневого узла равна 0. Если у узла есть только один ребенок, то этот ребенок гарантированно является левым ребенком. Учитывая выходной обход этого обхода, восстановите дерево и верните его корень.
Пример:
Input: traversal = "1-2--3--4-5--6--7" Output: [1,2,5,3,4,6,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 TreeNode RecoverFromPreorder(string S) {
var stack = new Stack<TreeNode>();
for (int i = 0; i < S.Length;) {
int level = 0;
while (i < S.Length && S[i] == '-') {
level++;
i++;
}
int value = 0;
while (i < S.Length && char.IsDigit(S[i])) {
value = value * 10 + (S[i] - '0');
i++;
}
TreeNode node = new TreeNode(value);
if (level == stack.Count) {
if (stack.Count > 0) {
stack.Peek().left = node;
}
} else {
while (level != stack.Count) {
stack.Pop();
}
stack.Peek().right = node;
}
stack.Push(node);
}
while (stack.Count > 1) {
stack.Pop();
}
return stack.Peek();
}
}3 206
Задача: 1539. Kth Missing Positive Number
Сложность: easy
Дан массив
arr из положительных целых чисел, отсортированных в строго возрастающем порядке, и целое число k.
Верните k-й положительный целочисленный элемент, который отсутствует в этом массиве.
Пример:
Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.public class Solution {
public int FindKthPositive(int[] arr, int k) {
if (k <= arr[0] - 1) {
return k;
}
k -= arr[0] - 1;
int n = arr.Length;
for (int i = 0; i < n - 1; ++i) {
int currMissing = arr[i + 1] - arr[i] - 1;
if (k <= currMissing) {
return arr[i] + k;
}
k -= currMissing;
}
return arr[n - 1] + k;
}
}3 206
Пожизненный PRO доступ на easyoffer — по цене одного года!
До 2 сентября вы можете купить PRO навсегда.
Покупаешь один раз — пользуешься всю жизнь.
– База вопросов и задач из собеседований
– Примеры видео-ответов на вопросы
– Записи реальных собеседований
– Тренажеры "Проработка вопросов" и "Реальное собеседование"
– Аналитика требований из вакансий
– Автоотклики на вакансии
– Агрегатор вакансий (скоро)
👉 Купить PRO со скидкой 70%: https://easyoffer.ru/pro
3 206
Задача: 1203. Sort Items by Groups Respecting Dependencies
Сложность: hard
Есть n предметов, каждый из которых принадлежит нулевой или одной из m групп, где group[i] — это группа, к которой принадлежит i-й предмет, и равно -1, если i-й предмет не принадлежит никакой группе. Предметы и группы имеют индексацию с нуля. Группа может не иметь ни одного предмета.
Верните отсортированный список предметов таким образом:
Предметы, принадлежащие одной группе, расположены рядом друг с другом в отсортированном списке.
Существуют некоторые отношения между этими предметами, где beforeItems[i] — это список, содержащий все предметы, которые должны быть перед i-м предметом в отсортированном массиве (слева от i-го предмета).
Верните любое решение, если существует более одного решения, и верните пустой список, если решения не существует.
Пример:
Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
Output: [6,3,4,1,5,2,0,7]public class Solution {
public int[] SortItems(int n, int m, int[] group, IList<IList<int>> beforeItems) {
int groupId = m;
for (int i = 0; i < n; i++) if (group[i] == -1) group[i] = groupId++;
var itemGraph = new Dictionary<int, List<int>>();
var groupGraph = new Dictionary<int, List<int>>();
int[] itemIndegree = new int[n], groupIndegree = new int[groupId];
for (int i = 0; i < n; i++) itemGraph[i] = new List<int>();
for (int i = 0; i < groupId; i++) groupGraph[i] = new List<int>();
for (int curr = 0; curr < n; curr++) {
foreach (var prev in beforeItems[curr]) {
itemGraph[prev].Add(curr);
itemIndegree[curr]++;
if (group[curr] != group[prev]) {
groupGraph[group[prev]].Add(group[curr]);
groupIndegree[group[curr]]++;
}
}
}
var itemOrder = TopologicalSort(itemGraph, itemIndegree);
var groupOrder = TopologicalSort(groupGraph, groupIndegree);
if (itemOrder.Count == 0 || groupOrder.Count == 0) return new int[0];
var orderedGroups = new Dictionary<int, List<int>>();
foreach (var item in itemOrder) {
if (!orderedGroups.ContainsKey(group[item])) orderedGroups[group[item]] = new List<int>();
orderedGroups[group[item]].Add(item);
}
var answerList = new List<int>();
foreach (var groupIndex in groupOrder) {
if (orderedGroups.ContainsKey(groupIndex)) answerList.AddRange(orderedGroups[groupIndex]);
}
return answerList.ToArray();
}
private List<int> TopologicalSort(Dictionary<int, List<int>> graph, int[] indegree) {
var visited = new List<int>();
var stack = new Stack<int>();
foreach (var key in graph.Keys) if (indegree[key] == 0) stack.Push(key);
while (stack.Count > 0) {
var curr = stack.Pop();
visited.Add(curr);
foreach (var next in graph[curr]) if (--indegree[next] == 0) stack.Push(next);
}
return visited.Count == graph.Keys.Count ? visited : new List<int>();
}
}3 206
Задача: 360. Sort Transformed Array
Сложность: medium
Дан отсортированный массив целых чисел nums и три целых числа a, b и c. Примените квадратичную функцию вида f(x) = ax^2 + bx + c к каждому элементу nums[i] в массиве и верните массив в отсортированном порядке.
Пример:
Input: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
Output: [3,9,15,33]using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
public int[] SortTransformedArray(int[] nums, int a, int b, int c) {
int[] transformed = nums.Select(x => a * x * x + b * x + c).ToArray();
RadixSort(transformed);
return transformed;
}
private void RadixSort(int[] array) {
int maxElement = array.Select(x => Math.Abs(x)).Max();
int placeValue = 1;
while (maxElement / placeValue > 0) {
CountingSortByDigit(array, placeValue);
placeValue *= 10;
}
var negatives = array.Where(x => x < 0).OrderBy(x => x).ToArray();
var positives = array.Where(x => x >= 0).OrderBy(x => x).ToArray();
Array.Copy(negatives, 0, array, 0, negatives.Length);
Array.Copy(positives, 0, array, negatives.Length, positives.Length);
}
private void CountingSortByDigit(int[] array, int placeValue) {
int n = array.Length;
int[] output = new int[n];
int[] count = new int[10];
foreach (int num in array) {
int digit = (Math.Abs(num) / placeValue) % 10;
count[digit]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
int num = array[i];
int digit = (Math.Abs(num) / placeValue) % 10;
output[count[digit] - 1] = num;
count[digit]--;
}
for (int i = 0; i < n; i++) {
array[i] = output[i];
}
}
}3 206
Задача: 905. Sort Array By Parity
Сложность: easy
Если задан целочисленный массив nums, переместите все четные числа в начало массива, а затем все нечетные. Верните любой массив, удовлетворяющий этому условию.
Пример:
Input: nums = [3,1,2,4] Output: [2,4,3,1]👨💻 Алгоритм: 1⃣Создать два списка: один для четных чисел, другой для нечетных. 2⃣Пройтись по массиву и добавить четные числа в один список, а нечетные в другой. 3⃣Объединить два списка и вернуть результат. 😎 Решение:
public class Solution {
public int[] SortArrayByParity(int[] nums) {
List<int> evens = new List<int>();
List<int> odds = new List<int>();
foreach (int num in nums) {
if (num % 2 == 0) {
evens.Add(num);
} else {
odds.Add(num);
}
}
evens.AddRange(odds);
return evens.ToArray();
}
}3 206
Задача: 674. Longest Continuous Increasing Subsequence
Сложность: easy
Дан неотсортированный массив целых чисел nums, верните длину самой длинной непрерывной возрастающей подпоследовательности (т.е. подмассива). Подпоследовательность должна быть строго возрастающей.
Непрерывная возрастающая подпоследовательность определяется двумя индексами l и r (l < r) так, что она имеет вид [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] и для каждого l <= i < r выполняется nums[i] < nums[i + 1].
Пример:
Input: nums = [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5] with length 3.
Even though [1,3,5,7] is an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element
4.public class Solution {
public int FindLengthOfLCIS(int[] nums) {
int ans = 0, anchor = 0;
for (int i = 0; i < nums.Length; ++i) {
if (i > 0 && nums[i-1] >= nums[i]) anchor = i;
ans = Math.Max(ans, i - anchor + 1);
}
return ans;
}
}3 206
Задача: 1283. Find the Smallest Divisor Given a Threshold
Сложность: medium
Дан массив целых чисел nums и целое число threshold. Мы выберем положительный целый делитель, разделим все элементы массива на него и суммируем результат деления. Найдите наименьший делитель, такой что результат, упомянутый выше, меньше или равен threshold.
Каждый результат деления округляется до ближайшего большего целого числа. (Например: 7/3 = 3 и 10/2 = 5).
Гарантируется, что решение существует.
Пример:
Input: nums = [1,2,5,9], threshold = 6 Output: 5 Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1. If the divisor is 4 we can get a sum of 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2).👨💻 Алгоритм: 1⃣Найдите максимальный элемент массива nums и сохраните его в переменной maxElement. 2⃣Итерация по всем делителям от 1 до maxElement: Инициализируйте две переменные: sumOfDivisionResults для хранения суммы результатов деления и thresholdExceeded для указания, превышен ли порог. Итерация по всем элементам массива nums: добавьте результат деления, округленного до ближайшего большего целого числа, в переменную sumOfDivisionResults. Если сумма превышает threshold, установите thresholdExceeded в true и прекратите итерацию по массиву nums. 3⃣Проверьте, был ли превышен порог: Если порог не был превышен, текущий делитель является наименьшим делителем, поэтому верните его. Если не найдено возможного делителя, верните -1. 😎 Решение:
public class Solution {
public int SmallestDivisor(int[] nums, int threshold) {
int maxElement = nums.Max();
for (int divisor = 1; divisor <= maxElement; divisor++) {
int sumOfDivisionResults = 0;
bool thresholdExceeded = true;
foreach (int num in nums) {
sumOfDivisionResults += (num + divisor - 1) / divisor;
if (sumOfDivisionResults > threshold) {
thresholdExceeded = false;
break;
}
}
if (thresholdExceeded) {
return divisor;
}
}
return -1;
}
}3 206
Задача: 1099. Two Sum Less Than K
Сложность: easy
Дан массив целых чисел nums и целое число k. Верните максимальную сумму, такую что существуют i < j, при которых nums[i] + nums[j] = sum и sum < k. Если не существует таких i и j, удовлетворяющих этому условию, верните -1.
Пример:
Input: nums = [34,23,1,24,75,33,54,8], k = 60 Output: 58 Explanation: We can use 34 and 24 to sum 58 which is less than 60.👨💻 Алгоритм: 1⃣Отсортируйте массив. 2⃣Установите указатели: левый на начало массива, правый на конец. 3⃣Пока левый указатель меньше правого: Если сумма элементов по указателям меньше k, обновите максимальную сумму и сдвиньте левый указатель вправо. Иначе сдвиньте правый указатель влево. Верните максимальную сумму. 😎 Решение:
public class Solution {
public int TwoSumLessThanK(int[] nums, int k) {
int answer = -1;
int[] count = new int[1001];
foreach (int num in nums) {
count[num]++;
}
int lo = 1, hi = 1000;
while (lo <= hi) {
if (lo + hi >= k || count[hi] == 0) {
hi--;
} else {
if (count[lo] > (lo < hi ? 0 : 1)) {
answer = Math.Max(answer, lo + hi);
}
lo++;
}
}
return answer;
}
}3 206
Задача: 1278. Palindrome Partitioning III
Сложность: hard
Вам дана строка s, содержащая строчные буквы, и целое число k. Вам нужно: Сначала заменить некоторые символы s на другие строчные английские буквы. Затем разделить s на k непустых непересекающихся подстрок так, чтобы каждая подстрока была палиндромом. Верните минимальное количество символов, которое нужно изменить, чтобы разделить строку.
Пример:
Input: s = "abc", k = 2 Output: 1👨💻 Алгоритм: 1⃣Используйте динамическое программирование для вычисления количества изменений, необходимых для превращения любой подстроки в палиндром. 2⃣Используйте еще одно динамическое программирование для разбиения строки на k палиндромических подстрок с минимальным количеством изменений. 3⃣Верните минимальное количество изменений, найденное во втором шаге. 😎 Решение:
public class Solution {
public int MinChangesToMakePalindrome(string s, int k) {
int n = s.Length;
int MinChangeToPalindrome(string s, int i, int j) {
int changes = 0;
while (i < j) {
if (s[i] != s[j]) {
changes++;
}
i++;
j--;
}
return changes;
}
int[,] dp1 = new int[n, n];
for (int length = 1; length <= n; length++) {
for (int i = 0; i <= n - length; i++) {
int j = i + length - 1;
dp1[i, j] = MinChangeToPalindrome(s, i, j);
}
}
int[,] dp2 = new int[n + 1, k + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= k; j++) {
dp2[i, j] = int.MaxValue;
}
}
dp2[0, 0] = 0;
for (int i = 1; i <= n; i++) {
for (int kk = 1; kk <= k; kk++) {
for (int j = 0; j < i; j++) {
dp2[i, kk] = Math.Min(dp2[i, kk], dp2[j, kk - 1] + dp1[j, i - 1]);
}
}
}
return dp2[n, k];
}
}3 206
Задача: 338. Counting Bits
Сложность: easy
Дано целое число n, верните массив ans длиной n + 1, такой что для каждого i (0 <= i <= n), ans[i] будет равняться количеству единиц в двоичном представлении числа i.
Пример:
Input: n = 5 Output: [0,1,1,2,1,2] Explanation: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101👨💻 Алгоритм: 1⃣Инициализация массива: Создайте массив ans длиной n + 1, заполненный нулями. Этот массив будет содержать количество единиц в двоичном представлении каждого числа от 0 до n. 2⃣Итерация и вычисление: Пройдите в цикле по всем числам от 1 до n. Для каждого числа x используйте битовую операцию x & (x - 1), чтобы убрать последнюю установленную биту, и добавьте 1 к значению ans для этого результата. Это количество единиц в двоичном представлении числа x. 3⃣Возврат результата: Верните заполненный массив ans, который содержит количество единиц для каждого числа от 0 до n. 😎 Решение:
public class Solution {
public int[] CountBits(int num) {
int[] ans = new int[num + 1];
for (int x = 1; x <= num; ++x) {
ans[x] = ans[x & (x - 1)] + 1;
}
return ans;
}
}3 206
Задача: 442. Find All Duplicates in an Array
Сложность: medium
Дан целочисленный массив nums длины n, где все целые числа nums находятся в диапазоне [1, n], и каждое число появляется один или два раза. Верните массив всех чисел, которые появляются дважды.
Вы должны написать алгоритм, который работает за время O(n) и использует только постоянное дополнительное пространство.
Пример:
Input: nums = [4,3,2,7,8,2,3,1] Output: [2,3]👨💻 Алгоритм: 1⃣Когда мы итерируемся по элементам входного массива, мы можем просто искать любое другое вхождение текущего элемента в оставшейся части массива. 2⃣Поскольку элемент может появляться только один или два раза, нам не нужно беспокоиться о получении дубликатов элементов, которые появляются дважды: Случай I: Если элемент встречается в массиве только один раз, при поиске его в остальной части массива ничего не найдется. Случай II: Если элемент встречается дважды, вы найдете второе вхождение элемента в оставшейся части массива. Когда вы наткнетесь на второе вхождение в более поздней итерации, это будет аналогично случаю I (поскольку больше вхождений этого элемента в оставшейся части массива не будет). 3⃣Таким образом, можно эффективно определить все элементы, которые встречаются дважды, и добавить их в результирующий массив, проходя по каждому элементу массива и проверяя наличие его второго вхождения в оставшейся части массива. 😎 Решение:
public class Solution {
public IList<int> FindDuplicates(int[] nums) {
List<int> ans = new List<int>();
for (int i = 0; i < nums.Length; i++)
for (int j = i + 1; j < nums.Length; j++) {
if (nums[j] == nums[i]) {
ans.Add(nums[i]);
break;
}
}
return ans;
}
}3 206
Задача: 1233. Remove Sub-Folders from the Filesystem
Сложность: medium
Если дан список папок folder, верните папки после удаления всех вложенных папок в этих папках. Вы можете вернуть ответ в любом порядке. Если папка[i] находится внутри другой папки[j], она называется ее вложенной папкой. Формат пути - это одна или несколько скомбинированных строк вида: '/', за которой следует одна или несколько строчных английских букв. Например, "/leetcode" и "/leetcode/problems" являются допустимыми путями, а пустая строка и "/" - нет.
Пример:
Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"] Output: ["/a","/c/d","/c/f"]👨💻 Алгоритм: 1⃣Сортировка папок: Сначала отсортируем список путей в лексикографическом порядке. Это обеспечит, что при обходе отсортированного списка мы всегда будем проверять родительскую папку перед вложенными папками. 2⃣Фильтрация вложенных папок: Будем использовать переменную для отслеживания текущей родительской папки. 3⃣При проходе по отсортированному списку проверим, является ли текущий путь вложенной папкой для отслеживаемой родительской папки. Если нет, обновим отслеживаемую папку и добавим ее в результирующий список. 😎 Решение:
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
public IList<string> RemoveSubfolders(string[] folder) {
Array.Sort(folder);
List<string> result = new List<string>();
string parent = "";
foreach (var path in folder) {
if (parent == "" || !path.StartsWith(parent + "/")) {
parent = path;
result.Add(path);
}
}
return result;
}
}3 206
Задача: 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;
}
}3 206
Задача: 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;
}
}3 206
Задача: 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;
}
}3 206
Задача: 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];
}
}3 206
Задача: 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;
}
}3 206
Задача: 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();
}
}3 206
Задача: 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;
}
}