C# | LeetCode
Відкрити в Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
Показати більше
Сітка:3 168
Підписники
-224 години
-57 днів
-2530 днів
Архів дописів
3 168
Задача: 929. Unique Email Addresses
Сложность: easy
Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока больше не останется ни одного узла, зараженного таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим ровно один узел из initial, полностью удалив его и все связи от этого узла к любому другому узлу. Верните узел, который, если его удалить, минимизирует M(initial). Если для минимизации M(initial) можно удалить несколько узлов, верните такой узел с наименьшим индексом.
Пример:
Input: emails = ["test.email+alex@leetcode.com","test.e.mail+bob.cathy@leetcode.com","testemail+david@lee.tcode.com"] Output: 2👨💻 Алгоритм: 1⃣Создать множество для хранения уникальных обработанных адресов электронной почты. 2⃣Для каждого адреса в emails: Разделить адрес на локальное и доменное имя по символу '@'. Обработать локальное имя: Удалить все точки '.'. Обрезать часть после символа '+'. Объединить обработанное локальное имя и доменное имя. Добавить результат в множество уникальных адресов. 3⃣Вернуть количество уникальных адресов в множестве. 😎 Решение:
using System;
using System.Collections.Generic;
public class Solution {
public int NumUniqueEmails(string[] emails) {
var uniqueEmails = new HashSet<string>();
foreach (var email in emails) {
var parts = email.Split('@');
var local = parts[0].Split('+')[0].Replace(".", "");
uniqueEmails.Add($"{local}@{parts[1]}");
}
return uniqueEmails.Count;
}
}3 168
Задача: 604. Design Compressed String Iterator
Сложность: easy
Разработайте и реализуйте структуру данных для итератора сжатой строки. Данная сжатая строка будет в виде каждой буквы, за которой следует положительное целое число, представляющее количество этой буквы в оригинальной несжатой строке.
Реализуйте класс
StringIterator:
- next(): Возвращает следующий символ, если в оригинальной строке еще остались несжатые символы, в противном случае возвращает пробел.
- hasNext(): Возвращает true, если в оригинальной строке остались символы, которые нужно распаковать, в противном случае возвращает false.
Пример:
Input
["StringIterator", "next", "next", "next", "next", "next", "next", "hasNext", "next", "hasNext"]
[["L1e2t1C1o1d1e1"], [], [], [], [], [], [], [], [], []]
Output
[null, "L", "e", "e", "t", "C", "o", true, "d", true]
Explanation
StringIterator stringIterator = new StringIterator("L1e2t1C1o1d1e1");
stringIterator.next(); // return "L"
stringIterator.next(); // return "e"
stringIterator.next(); // return "e"
stringIterator.next(); // return "t"
stringIterator.next(); // return "C"
stringIterator.next(); // return "o"
stringIterator.hasNext(); // return True
stringIterator.next(); // return "d"
stringIterator.hasNext(); // return Truepublic class StringIterator {
private StringBuilder res = new StringBuilder();
private int ptr = 0;
public StringIterator(string s) {
int i = 0;
while (i < s.Length) {
char ch = s[i++];
int num = 0;
while (i < s.Length && char.IsDigit(s[i])) {
num = num * 10 + (s[i] - '0');
i++;
}
for (int j = 0; j < num; j++)
res.Append(ch);
}
}
public char Next() {
return !HasNext() ? ' ' : res[ptr++];
}
public bool HasNext() {
return ptr != res.Length;
}
}3 168
Задача: 1087. Brace Expansion
Сложность: medium
Дан список оценок различных студентов, items, где items[i] = [IDi, scorei] представляет собой одну оценку студента с идентификатором IDi. Вычислите среднее значение пяти лучших оценок каждого студента.
Верните ответ в виде массива пар result, где result[j] = [IDj, topFiveAveragej] представляет студента с идентификатором IDj и его среднее значение пяти лучших оценок. Отсортируйте result по IDj в порядке возрастания.
Среднее значение пяти лучших оценок студента вычисляется путем сложения его пяти лучших оценок и деления на 5 с использованием целочисленного деления.
Пример:
Input: s = "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]public class Solution {
private int StoreFirstOptions(string s, int startPos, List<char> firstOptions) {
if (s[startPos] != '{') {
firstOptions.Add(s[startPos]);
} else {
startPos++;
while (s[startPos] != '}') {
if (char.IsLower(s[startPos])) {
firstOptions.Add(s[startPos]);
}
startPos++;
}
firstOptions.Sort();
}
return startPos + 1;
}
private List<string> FindAllWords(string s, int startPos) {
if (startPos == s.Length) {
return new List<string> { "" };
}
List<char> firstOptions = new List<char>();
int remStringStartPos = StoreFirstOptions(s, startPos, firstOptions);
List<string> wordsWithRemString = FindAllWords(s, remStringStartPos);
List<string> expandedWords = new List<string>();
foreach (char c in firstOptions) {
foreach (string word in wordsWithRemString) {
expandedWords.Add(c + word);
}
}
return expandedWords;
}
public List<string> Expand(string s) {
return FindAllWords(s, 0);
}
}3 168
Задача: 993. Cousins in Binary Tree
Сложность: easy
Дан корень бинарного дерева с уникальными значениями и значения двух различных узлов дерева x и y. Верните true, если узлы, соответствующие значениям x и y в дереве, являются кузенами, иначе верните false.
Два узла бинарного дерева являются кузенами, если они находятся на одной глубине и имеют разных родителей.
Обратите внимание, что в бинарном дереве корневой узел находится на глубине 0, а дети каждого узла глубины k находятся на глубине k + 1.
Пример:
Input: root = [1,2,3,4], x = 4, y = 3 Output: false👨💻 Алгоритм: 1⃣Поиск глубины и родителя для каждого узла: Используйте поиск в глубину (DFS) для обхода дерева. Для каждого узла сохраняйте его глубину и родителя, если значение узла равно x или y. 2⃣Проверка условий на кузенов: Узлы являются кузенами, если они находятся на одной глубине, но имеют разных родителей. 3⃣Возврат результата: Если узлы удовлетворяют условиям на кузенов, верните true, иначе верните false. 😎 Решение:
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
private TreeNode parentX = null;
private TreeNode parentY = null;
private int depthX = -1;
private int depthY = -1;
public bool IsCousins(TreeNode root, int x, int y) {
Dfs(root, null, 0, x, y);
return depthX == depthY && parentX != parentY;
}
private void Dfs(TreeNode node, TreeNode parent, int depth, int x, int y) {
if (node == null) {
return;
}
if (node.val == x) {
parentX = parent;
depthX = depth;
} else if (node.val == y) {
parentY = parent;
depthY = depth;
} else {
Dfs(node.left, node, depth + 1, x, y);
Dfs(node.right, node, depth + 1, x, y);
}
}
}3 168
Промпт для архитектурного ревью, 12 этапов изучения архитектуры ПО и другие полезные материалы для разработчиков.
Писать код умеют многие. Проектировать системы — единицы.
В Telegram-канале «Игроделы» разработчик с 20-летним опытом, делится практическими материалами по архитектуре ПО, C# и Unity.
Забирайте полезные материалы:
1️⃣ Промпт для архитектурного ревью кода
Поможет посмотреть на свой проект глубже, чем «работает / не работает»: проверить модульную декомпозицию, зависимости и распределение ответственности. Особенно интересно прогнать на коде, написанном с помощью ИИ. Сразу увидите слабые места и не будете доверять ИИ как раньше.
2️⃣ Маршрут изучения архитектуры ПО
12 этапов от DDD до работы с унаследованным кодом. Большой документ с книгами, конкретными главами, пояснениями и критериями усвоения материала.
3️⃣ Подборка книг по архитектуре
Для тех, кто хочет разобраться в проектировании систем и перестать принимать архитектурные решения наугад.
Никакой магии и обещаний написать идеальное приложение за два дня. Только инженерный подход, практика и материалы, которые можно использовать в своей работе.
👉 Забрать материалы — @igrodely36
3 168
🔥 Скрытые вакансии с удаленной работой для C# разработчика, которые нигде больше не публикуются. Напрямую от компаний, с контактами рекрутеров.
🔹 C# .NET Jobs | Вакансии
🔹 Unity Jobs | Вакансии
🔸 Все каналы с вакансиями
3 168
Задача: 1055. Shortest Way to Form String
Сложность: medium
Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (например, "ace" является подпоследовательностью "abcde", а "aec" - нет). Если даны две строки source и target, верните минимальное количество подпоследовательностей source, чтобы их объединение равнялось target. Если задача невыполнима, верните -1.
Пример:
Input: source = "abc", target = "abcbc"
Output: 2public class Solution {
public int MinSubsequences(string source, string target) {
int subsequencesCount = 0;
int targetIndex = 0;
while (targetIndex < target.Length) {
int sourceIndex = 0;
subsequencesCount++;
int startIndex = targetIndex;
while (sourceIndex < source.Length && targetIndex < target.Length) {
if (source[sourceIndex] == target[targetIndex]) {
targetIndex++;
}
sourceIndex++;
}
if (targetIndex == startIndex) {
return -1;
}
}
return subsequencesCount;
}
}3 168
Задача: 842. Split Array into Fibonacci Sequence
Сложность: medium
Вам дана строка цифр num, такая как "123456579". Мы можем разделить её на последовательность, похожую на Фибоначчи [123, 456, 579].
Формально, последовательность, похожая на Фибоначчи, это список f неотрицательных целых чисел, таких что:
0 <= f[i] < 2^31 (то есть каждое число помещается в 32-битный знаковый целый тип),
f.length >= 3, и
f[i] + f[i + 1] == f[i + 2] для всех 0 <= i < f.length - 2.
Обратите внимание, что при разделении строки на части каждая часть не должна иметь лишних ведущих нулей, за исключением случая, если эта часть является числом 0.
Верните любую последовательность, похожую на Фибоначчи, из строки num, или верните [] если это невозможно.
Пример:
Input: num = "1101111" Output: [11,0,11,11] Explanation: The output [110, 1, 111] would also be accepted.👨💻 Алгоритм: 1⃣Переберите все возможные начальные элементы первой и второй части последовательности, проверяя, чтобы не было ведущих нулей. 2⃣Для каждой пары начальных элементов проверяйте, можно ли продолжить последовательность Фибоначчи, создавая следующую часть, которая должна быть суммой двух предыдущих частей. 3⃣Если последовательность Фибоначчи найдена, верните её, иначе продолжайте перебор. 😎 Решение:
public class Solution {
public IList<int> SplitIntoFibonacci(string S) {
int N = S.Length;
for (int i = 0; i < Math.Min(10, N); ++i) {
if (S[0] == '0' && i > 0) break;
long a = long.Parse(S.Substring(0, i + 1));
if (a >= int.MaxValue) break;
for (int j = i + 1; j < Math.Min(i + 10, N); ++j) {
if (S[i + 1] == '0' && j > i + 1) break;
long b = long.Parse(S.Substring(i + 1, j - i));
if (b >= int.MaxValue) break;
List<int> fib = new List<int> { (int)a, (int)b };
int k = j + 1;
while (k < N) {
long nxt = fib[fib.Count - 2] + fib[fib.Count - 1];
if (nxt > int.MaxValue) break;
string nxtS = nxt.ToString();
if (S.Substring(k).StartsWith(nxtS)) {
k += nxtS.Length;
fib.Add((int)nxt);
} else {
break;
}
}
if (fib.Count >= 3) return fib;
}
}
return new List<int>();
}
}3 168
Задача: 1189. Maximum Number of Balloons
Сложность: easy
Дана строка text. Вы хотите использовать символы строки text, чтобы сформировать как можно больше экземпляров слова "balloon".
Каждый символ строки text можно использовать не более одного раза. Верните максимальное количество экземпляров, которые можно сформировать.
Пример:
Input: text = "nlaebolko"
Output: 1public class Solution {
public int MaxNumberOfBalloons(string text) {
int bCount = 0, aCount = 0, lCount = 0, oCount = 0, nCount = 0;
foreach (char c in text) {
if (c == 'b') {
bCount++;
} else if (c == 'a') {
aCount++;
} else if (c == 'l') {
lCount++;
} else if (c == 'o') {
oCount++;
} else if (c == 'n') {
nCount++;
}
}
lCount /= 2;
oCount /= 2;
return Math.Min(bCount, Math.Min(aCount, Math.Min(lCount, Math.Min(oCount, nCount))));
}
}3 168
Задача: 1074. Number of Submatrices That Sum to Target
Сложность: hard
Дана матрица и целевое значение. Верните количество непустых подматриц, сумма элементов которых равна целевому значению.
Подматрица x1, y1, x2, y2 — это набор всех ячеек matrix[x][y] с x1 <= x <= x2 и y1 <= y <= y2.
Две подматрицы (x1, y1, x2, y2) и (x1', y1', x2', y2') различны, если у них есть какая-то различающаяся координата: например, если x1 != x1'.
Пример:
Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output: 4
Explanation: The four 1x1 submatrices that only contain 0.public class Solution {
public int NumSubmatrixSumTarget(int[][] matrix, int target) {
int r = matrix.Length, c = matrix[0].Length;
int[,] ps = new int[r + 1, c + 1];
for (int i = 1; i <= r; ++i) {
for (int j = 1; j <= c; ++j) {
ps[i, j] = ps[i - 1, j] + ps[i, j - 1] - ps[i - 1, j - 1] + matrix[i - 1][j - 1];
}
}
int count = 0;
for (int r1 = 1; r1 <= r; ++r1) {
for (int r2 = r1; r2 <= r; ++r2) {
Dictionary<int, int> h = new Dictionary<int, int>();
h[0] = 1;
for (int col = 1; col <= c; ++col) {
int currSum = ps[r2, col] - ps[r1 - 1, col];
if (h.ContainsKey(currSum - target)) {
count += h[currSum - target];
}
if (h.ContainsKey(currSum)) {
h[currSum]++;
} else {
h[currSum] = 1;
}
}
}
}
return count;
}
}3 168
Задача: 719. Find K-th Smallest Pair Distance
Сложность: hard
Расстояние между парой целых чисел a и b определяется как абсолютная разность между a и b. Учитывая целочисленный массив nums и целое число k, верните k-е наименьшее расстояние среди всех пар nums[i] и nums[j], где 0 <= i < j < nums.length.
Пример:
Input: nums = [1,3,1], k = 1 Output: 0👨💻 Алгоритм: 1⃣Отсортируйте массив nums. 2⃣Определите минимальное и максимальное возможные расстояния. 3⃣Используйте бинарный поиск, чтобы найти k-е наименьшее расстояние, проверяя количество пар с расстоянием меньше или равно текущему среднему значению. 😎 Решение:
public class Solution {
public int SmallestDistancePair(int[] nums, int k) {
Array.Sort(nums);
int left = 0, right = nums[nums.Length - 1] - nums[0];
while (left < right) {
int mid = (left + right) / 2;
if (CountPairs(nums, mid) < k) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
private int CountPairs(int[] nums, int mid) {
int count = 0, j = 0;
for (int i = 0; i < nums.Length; i++) {
while (j < nums.Length && nums[j] - nums[i] <= mid) {
j++;
}
count += j - i - 1;
}
return count;
}
}3 168
Задача: 209. Minimum Size Subarray Sum
Сложность: medium
Дан массив положительных целых чисел nums и положительное целое число target. Верните минимальную длину подмассива, сумма которого больше или равна target. Если такого подмассива нет, верните 0.
Пример:
Input: target = 7, nums = [2,3,1,2,4,3] Output: 2 Explanation: The subarray [4,3] has the minimal length under the problem constraint.👨💻 Алгоритм: 1⃣Инициализация переменных: Создайте три целочисленные переменные left, right и sumOfCurrentWindow. Переменные left и right формируют подмассив, указывая на начальные и конечные индексы текущего подмассива (или окна), а sumOfCurrentWindow хранит сумму этого окна. Инициализируйте все их значением 0. Создайте еще одну переменную res для хранения ответа на задачу. Инициализируйте ее большим целым значением. 2⃣Итерация по массиву: Итерируйте по массиву nums с помощью right, начиная с right = 0 до nums.length - 1, увеличивая right на 1 после каждой итерации. Выполняйте следующее внутри этой итерации: Добавьте элемент с индексом right к текущему окну, увеличив sumOfCurrentWindow на nums[right]. Проверьте, если sumOfCurrentWindow >= target. Если да, у нас есть подмассив, который удовлетворяет условию. В результате, попытайтесь обновить переменную ответа res длиной этого подмассива. Выполните res = min(res, right - left + 1). Затем удалите первый элемент из этого окна, уменьшив sumOfCurrentWindow на nums[left] и увеличив left на 1. Этот шаг повторяется во внутреннем цикле, пока sumOfCurrentWindow >= target. 3⃣Возврат результата: Текущая сумма окна теперь меньше target. Нужно добавить больше элементов в окно. В результате, увеличивается right на 1. Верните res. 😎 Решение:
public class Solution {
public int MinSubArrayLen(int target, int[] nums) {
int left = 0, sumOfCurrentWindow = 0;
int res = int.MaxValue;
for (int right = 0; right < nums.Length; right++) {
sumOfCurrentWindow += nums[right];
while (sumOfCurrentWindow >= target) {
res = Math.Min(res, right - left + 1);
sumOfCurrentWindow -= nums[left];
left++;
}
}
return res == int.MaxValue ? 0 : res;
}
}3 168
Задача: 205. Isomorphic Strings
Сложность: easy
Даны две строки s и t, определите, являются ли они изоморфными.
Две строки s и t являются изоморфными, если символы в s могут быть заменены для получения t.
Все вхождения одного символа должны быть заменены другим символом, сохраняя порядок символов. Два символа не могут отображаться в один и тот же символ, но один символ может отображаться сам на себя.
Пример:
Input: s = "egg", t = "add" Output: true👨💻 Алгоритм: 1⃣Определите два словаря: mapping_s_t для отображения символов из строки s в символы строки t, и mapping_t_s для отображения символов из строки t в символы строки s. 2⃣Итеративно пройдитесь по символам строк s и t. Для каждого символа c1 из s и соответствующего c2 из t, если c1 нет в mapping_s_t и c2 нет в mapping_t_s, добавьте соответствующие отображения; если одно из отображений существует, проверьте, соответствует ли оно ожидаемому значению. 3⃣Если в процессе проверки какое-либо отображение неверно, верните false. Если все проверки пройдены успешно, верните true после окончания итерации по строкам. 😎 Решение:
public class Solution {
public bool IsIsomorphic(string s, string t) {
int[] mappingStoT = new int[256];
int[] mappingTtoS = new int[256];
for (int i = 0; i < s.Length; ++i) {
char c1 = s[i];
char c2 = t[i];
if (mappingStoT[c1] == 0 && mappingTtoS[c2] == 0) {
mappingStoT[c1] = c2;
mappingTtoS[c2] = c1;
} else if (!(mappingStoT[c1] == c2 && mappingTtoS[c2] == c1)) {
return false;
}
}
return true;
}
}3 168
Задача: 1416. Restore The Array
Сложность: hard
Программа должна была напечатать массив целых чисел. Программа забыла напечатать пробелы, и массив напечатан как строка цифр s, и всё, что мы знаем, это что все числа в массиве были в диапазоне [1, k] и в массиве нет ведущих нулей.
Учитывая строку s и целое число k, верните количество возможных массивов, которые могут быть напечатаны как s с использованием упомянутой программы. Так как ответ может быть очень большим, верните его по модулю 10^9 + 7.
Пример:
Input: s = "1000", k = 10000 Output: 1 Explanation: The only possible array is [1000]👨💻 Алгоритм: 1⃣Создать массив dp размера m + 1, чтобы хранить значения dfs(x). 2⃣Для получения значения dfs(start), если dp[start] не равно нулю, вернуть его значение. Иначе: Если s[start] == 0, вернуть 0. Если start = m, вернуть 1. Инициализировать count = 0, чтобы считать количество возможных массивов. Перебрать все возможные конечные индексы end, и если s[start ~ end] представляет допустимое число, продолжить рекурсивный вызов dfs(end + 1) и обновить count как count += dfs(end + 1). Обновить dp[start] значением dfs(start). 3⃣Вернуть dfs(0). 😎 Решение:
public class Solution {
private int mod = 1_000_000_007;
private int Dfs(int[] dp, int start, string s, int k) {
if (dp[start] != 0) return dp[start];
if (start == s.Length) return 1;
if (s[start] == '0') return 0;
long count = 0;
for (int end = start; end < s.Length; ++end) {
string currNumber = s.Substring(start, end - start + 1);
if (long.Parse(currNumber) > k) break;
count = (count + Dfs(dp, end + 1, s, k)) % mod;
}
dp[start] = (int)count;
return (int)count;
}
public int NumberOfArrays(string s, int k) {
int[] dp = new int[s.Length + 1];
return Dfs(dp, 0, s, k);
}
}3 168
Задача: 217. Contains Duplicate
Сложность: easy
Дан массив целых чисел nums. Верните true, если любое значение появляется в массиве хотя бы дважды, и верните false, если каждый элемент уникален.
Пример:
Input: nums = [1,2,3,4] Output: false👨💻 Алгоритм: 1⃣Отсортируйте массив nums по возрастанию. 2⃣Итерируйте по отсортированному массиву и сравнивайте каждое число с следующим. 3⃣Если любое число совпадает с следующим, верните true. Если цикл завершится без совпадений, верните false. 😎 Решение:
public bool ContainsDuplicate(int[] nums) {
Array.Sort(nums);
for (int i = 0; i < nums.Length - 1; ++i) {
if (nums[i] == nums[i + 1]) {
return true;
}
}
return false;
}3 168
Задача: 759. Employee Free Time
Сложность: hard
Нам дан список schedule of employees, который представляет собой рабочее время каждого сотрудника. У каждого сотрудника есть список непересекающихся интервалов, и эти интервалы расположены в отсортированном порядке. Верните список конечных интервалов, представляющих общее свободное время положительной длины для всех сотрудников, также в отсортированном порядке. (Хотя мы представляем интервалы в форме [x, y], объекты внутри них являются интервалами, а не списками или массивами. Например, schedule[0][0].start = 1, schedule[0][0].end = 2, а schedule[0][0][0] не определено).Также мы не будем включать в наш ответ интервалы типа [5, 5], так как они имеют нулевую длину.
Пример:
Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]] Output: [[3,4]]👨💻 Алгоритм: 1⃣Объедините все интервалы всех сотрудников в один список и отсортируйте его по начальным временам. 2⃣Объедините пересекающиеся интервалы в один. 3⃣Найдите промежутки между объединенными интервалами, представляющие свободное время. 😎 Решение:
using System;
using System.Collections.Generic;
public class Interval {
public int start;
public int end;
public Interval() {
start = 0; end = 0;
}
public Interval(int s, int e) {
start = s; end = e;
}
}
public class Solution {
public IList<Interval> EmployeeFreeTime(IList<IList<Interval>> schedule) {
List<Interval> intervals = new List<Interval>();
foreach (var employee in schedule) {
intervals.AddRange(employee);
}
intervals.Sort((a, b) => a.start.CompareTo(b.start));
List<Interval> merged = new List<Interval>();
foreach (var interval in intervals) {
if (merged.Count == 0 || merged[merged.Count - 1].end < interval.start) {
merged.Add(interval);
} else {
merged[merged.Count - 1].end = Math.Max(merged[merged.Count - 1].end, interval.end);
}
}
List<Interval> freeTime = new List<Interval>();
for (int i = 1; i < merged.Count; i++) {
if (merged[i].start > merged[i - 1].end) {
freeTime.Add(new Interval(merged[i - 1].end, merged[i].start));
}
}
return freeTime;
}
}3 168
Задача: 583. Delete Operation for Two Strings
Сложность: medium
Даны две строки word1 и word2, вернуть минимальное количество шагов, необходимых для того, чтобы сделать word1 и word2 одинаковыми.
На одном шаге можно удалить ровно один символ в любой строке.
Пример:
Input: word1 = "sea", word2 = "eat" Output: 2 Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".👨💻 Алгоритм: 1⃣ Инициализация массива: Создайте одномерный массив dp для хранения минимального количества удалений, необходимых для уравнивания строк word1 и word2. 2⃣ Заполнение массива: Используйте временный массив temp для обновления значений dp, представляющих текущую строку. Обновите temp с использованием значений dp предыдущей строки. 3⃣ Обновление и результат: Скопируйте временный массив temp обратно в dp после обработки каждой строки. В конце верните значение из dp, представляющее минимальное количество удалений. 😎 Решение:
public class Solution {
public int MinDistance(string word1, string word2) {
int m = word1.Length;
int n = word2.Length;
int[] dp = new int[n + 1];
for (int i = 0; i <= m; i++) {
int[] temp = new int[n + 1];
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
temp[j] = i + j;
} else if (word1[i - 1] == word2[j - 1]) {
temp[j] = dp[j - 1];
} else {
temp[j] = 1 + Math.Min(dp[j], temp[j - 1]);
}
}
dp = temp;
}
return dp[n];
}
}3 168
Задача: 1252. Cells with Odd Values in a Matrix
Сложность: easy
Имеется матрица m x n, которая инициализирована всеми 0. Имеется двумерный массив indices, в котором каждый indices[i] = [ri, ci] представляет собой местоположение с индексом 0 для выполнения некоторых операций инкремента над матрицей. Для каждого местоположения indices[i] выполните оба следующих действия: увеличьте все ячейки в строке ri. Увеличьте все ячейки в столбце ci. Учитывая m, n и indices, верните количество нечетных ячеек в матрице после применения инкремента ко всем местоположениям в indices.
Пример:
Input: nums = [12,5,7,23] Output: true👨💻 Алгоритм: 1⃣Инициализируйте два массива: один для подсчета количества инкрементов каждой строки, другой - каждого столбца. 2⃣Для каждого элемента в indices увеличьте счетчики соответствующих строк и столбцов. 3⃣Подсчитайте количество нечетных ячеек, используя информацию о количестве инкрементов каждой строки и столбца. 😎 Решение:
public class Solution {
public int OddCells(int m, int n, int[][] indices) {
int[] row_count = new int[m];
int[] col_count = new int[n];
foreach (var index in indices) {
row_count[index[0]]++;
col_count[index[1]]++;
}
int odd_count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if ((row_count[i] + col_count[j]) % 2 == 1) {
odd_count++;
}
}
}
return odd_count;
}
}3 168
Задача: 325. Maximum Size Subarray Sum Equals k
Сложность: medium
Дан целочисленный массив nums и целое число k. Верните максимальную длину подмассива, сумма которого равна k. Если такого подмассива не существует, верните 0.
Пример:
Input: nums = [1,-1,5,-2,3], k = 3 Output: 4 Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.👨💻 Алгоритм: 1⃣Инициализация переменных Инициализируйте prefixSum как 0 для отслеживания префиксной суммы nums. Инициализируйте longestSubarray как 0 для отслеживания самой длинной подмассы с суммой k. Инициализируйте хеш-карту indices для хранения префиксных сумм и их индексов. 2⃣Итерация по массиву На каждом индексе i, добавляйте nums[i] к prefixSum. Проверьте следующие условия: Если prefixSum == k, обновите longestSubarray как i + 1. Если prefixSum - k существует в indices, обновите longestSubarray, если текущая длина подмассива больше. Если текущий prefixSum еще не существует в indices, добавьте indices[prefixSum] = i. 3⃣Возврат результата Верните значение longestSubarray. 😎 Решение:
public class Solution {
public int MaxSubArrayLen(int[] nums, int k) {
int prefixSum = 0;
int longestSubarray = 0;
Dictionary<int, int> indices = new Dictionary<int, int>();
for (int i = 0; i < nums.Length; i++) {
prefixSum += nums[i];
if (prefixSum == k) {
longestSubarray = i + 1;
}
if (indices.ContainsKey(prefixSum - k)) {
longestSubarray = Math.Max(longestSubarray, i - indices[prefixSum - k]);
}
if (!indices.ContainsKey(prefixSum)) {
indices[prefixSum] = i;
}
}
return longestSubarray;
}
}3 168
Задача: 1171. Remove Zero Sum Consecutive Nodes from Linked List
Сложность: medium
Дан указатель на голову связанного списка. Мы многократно удаляем последовательные последовательности узлов, сумма которых равна 0, до тех пор, пока такие последовательности не исчезнут.
После этого верните голову конечного связанного списка. Вы можете вернуть любой такой ответ.
Пример:
Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.public class ListNode {
public int val;
public ListNode next;
public ListNode(int val=0, ListNode next=null) {
this.val = val;
this.next = next;
}
}
public class Solution {
public ListNode RemoveZeroSumSublists(ListNode head) {
ListNode front = new ListNode(0, head);
ListNode start = front;
while (start != null) {
int prefixSum = 0;
ListNode end = start.next;
while (end != null) {
prefixSum += end.val;
if (prefixSum == 0) {
start.next = end.next;
}
end = end.next;
}
start = start.next;
}
return front.next;
}
}