C# LeetCode - задачи

Задача: 233. Number of Digit One Сложность: hard Дано целое число n, посчитайте общее количество единиц, встречающихся во всех неотрицательных числах, меньших или равных n. Пример: Input: n = 13 Output: 6 👨💻 Алгоритм: 1⃣Итерация по степеням 10: Итеративно увеличивайте значение i от 1 до n, увеличивая i в 10 раз на каждом шаге. Это позволяет анализировать каждую цифру числа n. 2⃣Подсчет групповых единиц: Для каждой итерации добавляйте (n / (i * 10)) * i к счетчику countr, что представляет собой количество единиц, встречающихся в группах размера i после каждого интервала (i * 10). 3⃣Добавление дополнительных единиц: Для каждой итерации добавляйте min(max((n % (i * 10)) - i + 1, 0), i) к счетчику countr, что представляет собой дополнительные единицы, зависящие от цифры на позиции i. 😎 Решение: public class Solution { public int CountDigitOne(int n) { int countr = 0; for (long i = 1; i

Задача: 665. Non-decreasing Array Сложность: medium Дан массив nums из n целых чисел. Ваша задача - проверить, можно ли сделать его неубывающим, изменив не более одного элемента. Мы определяем массив как неубывающий, если для каждого i (индексация с 0), такого что 0 nums[i + 2], то возвращаем false. 3⃣Возврат результата: Если количество изменений не превышает 1, вернуть true. 😎 Решение: public class Solution { public bool CheckPossibility(int[] nums) { int count = 0; for (int i = 1; i < nums.Length; i++) { if (nums[i] < nums[i - 1]) { if (count > 0) { return false; } count++; if (i == 1 || nums[i] >= nums[i - 2]) { nums[i - 1] = nums[i]; } else { nums[i] = nums[i - 1]; } } } return true; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1493. Longest Subarray of 1's After Deleting One Element Сложность: medium Дан бинарный массив nums, из которого следует удалить один элемент. Верните размер самой длинной непустой подмассивы, содержащей только 1, в результирующем массиве. Верните 0, если такого подмассива не существует. Пример: Input: nums = [0,1,1,1,0,1,1,0,1] Output: 5 Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1]. 👨💻 Алгоритм: 1⃣Инициализация переменных: zeroCount для подсчёта нулей в текущем окне, longestWindow для хранения максимальной длины окна, содержащего не более одного нуля, и start для левой границы окна. 2⃣Итерация по массиву: При каждом элементе увеличиваем zeroCount, если это ноль. Если zeroCount превышает 1, сокращаем окно, перемещая левую границу вправо и уменьшая zeroCount, пока количество нулей не станет меньше или равно 1. Обновляем longestWindow текущей длиной окна i - start. 3⃣ Возврат результата: Вернуть longestWindow. 😎 Решение: public class Solution { public int LongestSubarray(int[] nums) { int zeroCount = 0; int longestWindow = 0; int start = 0; for (int i = 0; i < nums.Length; i++) { if (nums[i] == 0) { zeroCount++; } while (zeroCount > 1) { if (nums[start] == 0) { zeroCount--; } start++; } longestWindow = Math.Max(longestWindow, i - start); } return longestWindow; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 976. Largest Perimeter Triangle Сложность: easy Дан целочисленный массив nums. Верните наибольший периметр треугольника с ненулевой площадью, образованный из трех этих длин. Если невозможно образовать треугольник с ненулевой площадью, верните 0. Пример: Input: nums = [1,2,1,10] Output: 0 Explanation: You cannot use the side lengths 1, 1, and 2 to form a triangle. You cannot use the side lengths 1, 1, and 10 to form a triangle. You cannot use the side lengths 1, 2, and 10 to form a triangle. As we cannot use any three side lengths to form a triangle of non-zero area, we return 0. 👨💻 Алгоритм: 1⃣Отсортируйте массив nums в порядке возрастания. 2⃣Для каждого элемента c в массиве, начиная с конца: Выберите два наибольших возможных значения a и b, которые находятся перед c в отсортированном массиве (т.е. значения, смежные с c). Проверьте, образуют ли a, b и c треугольник (условие треугольника: a + b > c). Если образуют, верните их сумму как периметр треугольника. 3⃣Если не удалось найти такие значения, верните 0. 😎 Решение: public class Solution { public int LargestPerimeter(int[] A) { Array.Sort(A); for (int i = A.Length - 3; i >= 0; --i) if (A[i] + A[i + 1] > A[i + 2]) return A[i] + A[i + 1] + A[i + 2]; return 0; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 599. Minimum Index Sum of Two Lists Сложность: easy Даны два массива строк list1 и list2, необходимо найти общие строки с наименьшей суммой индексов. Общая строка - это строка, которая появляется и в list1, и в list2. Общая строка с наименьшей суммой индексов - это общая строка, такая, что если она появилась в list1[i] и list2[j], то i + j должно быть минимальным значением среди всех других общих строк. Верните все общие строки с наименьшей суммой индексов. Верните ответ в любом порядке. Пример: Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"] Output: ["Shogun"] Explanation: The only common string is "Shogun". 👨💻 Алгоритм: 1⃣Для каждой строки из list1, сравниваем её с каждой строкой из list2, обходя весь список list2. Используем хэш-таблицу map, которая содержит элементы в виде (сумма: список строк). Здесь сумма относится к сумме индексов совпадающих элементов, а список строк соответствует списку совпадающих строк, чья сумма индексов равна этой сумме. 2⃣Во время сравнений, когда находится совпадение строки на i-м индексе из list1 и j-м индексе из list2, создаём запись в map, соответствующую сумме i + j, если такая запись ещё не существует. Если запись с этой суммой уже существует, добавляем текущую строку в список строк, соответствующих сумме i + j. 3⃣В конце обходим ключи в map и находим список строк, соответствующих ключу с минимальной суммой. 😎 Решение: using System; using System.Collections.Generic; public class Solution { public string[] FindRestaurant(string[] list1, string[] list2) { var map = new Dictionary(); for (int i = 0; i • (); } map[i + j].Add(list1[i]); } } } int minIndexSum = int.MaxValue; foreach (var key in map.Keys) { minIndexSum = Math.Min(minIndexSum, key); } return map[minIndexSum].ToArray(); } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 811. Subdomain Visit Count Сложность: medium Веб-сайт с доменом "discuss.leetcode.com" состоит из различных поддоменов. На верхнем уровне у нас есть "com", на следующем уровне - "leetcode.com", и на самом нижнем уровне - "discuss.leetcode.com". Когда мы посещаем домен, такой как "discuss.leetcode.com", мы также автоматически посещаем родительские домены "leetcode.com" и "com". Домен с парным счетчиком - это домен, который имеет один из двух форматов "rep d1.d2.d3" или "rep d1.d2", где rep - это количество посещений домена, а d1.d2.d3 - это сам домен. Например, "9001 discuss.leetcode.com" - это домен с парным счетчиком, указывающий на то, что discuss.leetcode.com был посещен 9001 раз. Дан массив доменов с парными счетчиками cpdomains, верните массив доменов с парными счетчиками для каждого поддомена во входных данных. Вы можете вернуть ответ в любом порядке. Пример: Input: cpdomains = ["9001 discuss.leetcode.com"] Output: ["9001 leetcode.com","9001 discuss.leetcode.com","9001 com"] Explanation: We only have one website domain: "discuss.leetcode.com". As discussed above, the subdomain "leetcode.com" and "com" will also be visited. So they will all be visited 9001 times. 👨💻 Алгоритм: 1⃣Следуем указаниям из условия задачи. 2⃣Для адреса вида a.b.c, подсчитываем a.b.c, b.c и c. Для адреса вида x.y, подсчитываем x.y и y. 3⃣Для подсчета этих строк используем хеш-таблицу. Для разделения строк на требуемые части используем библиотечные функции split. 😎 Решение: using System; using System.Collections.Generic; public class Solution { public IList SubdomainVisits(string[] cpdomains) { var ans = new Dictionary(); foreach (var domain in cpdomains) { var parts = domain.Split(' '); var count = int.Parse(parts[0]); var frags = parts[1].Split('.'); for (int i = 0; i < frags.Length; i++) { var subdomain = string.Join(".", frags, i, frags.Length - i); if (ans.ContainsKey(subdomain)) { ans[subdomain] += count; } else { ans[subdomain] = count; } } } var res = new List(); foreach (var entry in ans) { res.Add($"{entry.Value} {entry.Key}"); } return res; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 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 = k || count[hi] == 0) { hi--; } else { if (count[lo] > (lo < hi ? 0 : 1)) { answer = Math.Max(answer, lo + hi); } lo++; } } return answer; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 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

Задача: 338. Counting Bits Сложность: easy Дано целое число n, верните массив ans длиной n + 1, такой что для каждого i (0 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