Последние посты
C# | LeetCode
22 сент., 16:11
Задача: 948. Bag of Tokens Сложность: mediumВы начинаете с начальной силой, равной power, начальным счетом 0 и мешком жетонов, представленным в виде целочисленного массива tokens, где каждый tokens[i] обозначает значение tokeni. Ваша цель - максимизировать общее количество очков, стратегически разыгрывая эти жетоны. За один ход вы можете разыграть неразыгранный жетон одним из двух способов (но не обоими для одного и того же жетона): лицом вверх: Если ваша текущая сила не меньше жетонов[i], вы можете сыграть токени, потеряв силу жетонов[i] и получив 1 очко. Лицом вниз: Если ваш текущий счет не меньше 1, вы можете сыграть токени, получив силу токенов[i] и потеряв 1 счет. Верните максимально возможный счет, который вы можете получить, сыграв любое количество токенов.Пример: Input: tokens = [100], power = 50Output: 0👨💻 Алгоритм:1⃣Отсортировать массив tokens. Использовать дваC# | LeetCode
22 сент., 09:06
Задача: 1056. Confusing Number Сложность: easyЗапутанное число - это число, которое при повороте на 180 градусов становится другим числом, каждая цифра которого действительна. Мы можем повернуть цифры числа на 180 градусов, чтобы получить новые цифры. Когда 0, 1, 6, 8 и 9 поворачиваются на 180 градусов, они становятся 0, 1, 9, 8 и 6 соответственно. При повороте на 180 градусов 2, 3, 4, 5 и 7 становятся недействительными. Обратите внимание, что после поворота числа мы можем игнорировать ведущие нули. Например, после поворота 8000 мы получим 0008, которое считается просто 8. Если задано целое число n, верните true, если это запутанное число, или false в противном случае.Пример: Input: n = 6 Output: true👨💻 Алгоритм:1⃣Преобразуй число в строку для удобства работы с его цифрами. Используй словарь для хранения соответствий цифр при повороте на 180 градусов.2⃣Пройди по цифрамC# | LeetCode
21 сент., 09:06
Задача: 1101. The Earliest Moment When Everyone Become Friends Сложность: mediumВ социальной группе есть n человек, пронумерованных от 0 до n - 1. Вам дан массив logs, где logs[i] = [timestampi, xi, yi] указывает, что xi и yi станут друзьями в момент времени timestampi.Дружба является симметричной. Это означает, что если a является другом b, то b является другом a. Также человек a знаком с человеком b, если a является другом b или a является другом кого-то, кто знаком с b.Верните самое раннее время, когда каждый человек стал знаком с каждым другим человеком. Если такого времени не существует, верните -1.Пример: Input: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4 Output: 3 Explanation: At timestamp = 3, all the persons (i.e., 0, 1, 2, and 3) become friends.👨💻 Алгоритм:1⃣Отсортируйте логи по времени в хронологическом порядке, так как в задаче не указано,C# | LeetCode
19 сент., 09:06
Задача: 242. Valid Anagram Сложность: easyДаны две строки s и t, верните true, если t является анаграммой s, и false в противном случае.Анаграмма — это слово или фраза, сформированная путём перестановки букв другого слова или фразы, обычно используя все исходные буквы ровно один раз.Пример: Input: s = "anagram", t = "nagaram" Output: true👨💻 Алгоритм:1⃣Создайте массив размером 26 для подсчета частот каждой буквы (поскольку s и t содержат только буквы от 'a' до 'z').2⃣Пройдитесь по строке s, увеличивая счетчик соответствующей буквы. Затем пройдитесь по строке t, уменьшая счетчик для каждой буквы.3⃣Проверьте, не опустился ли счетчик ниже нуля во время обхода строки t. Если это произошло, значит в t есть лишняя буква, которой нет в s, и следует вернуть false. Если после проверки всех букв все счетчики равны нулю, возвращайте true, указывая на то, что t является анаграммой s.C# | LeetCode
14 сент., 16:11
Задача: 850. Rectangle Area II Сложность: hardВам дан двумерный массив прямоугольников, выровненных по осям. Каждый прямоугольник[i] = [xi1, yi1, xi2, yi2] обозначает i-й прямоугольник, где (xi1, yi1) — координаты нижнего левого угла, а (xi2, yi2) — координаты верхнего правого угла.Вычислите общую площадь, покрытую всеми прямоугольниками на плоскости. Любая площадь, покрытая двумя или более прямоугольниками, должна учитываться только один раз.Верните общую площадь. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.Пример: Input: rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]] Output: 6 Explanation: A total area of 6 is covered by all three rectangles, as illustrated in the picture. From (1,1) to (2,2), the green and red rectangles overlap. From (1,0) to (2,3), all three rectangles overlap.👨💻 Алгоритм:1⃣Переназначьте каждую x координату на 0, 1, 2,C# | LeetCode
11 сент., 16:12
Задача: 491. Non-decreasing Subsequences Сложность: mediumДан массив целых чисел nums. Верните все возможные различные неубывающие подпоследовательности данного массива, содержащие как минимум два элемента. Вы можете вернуть ответ в любом порядке.Пример: Input: nums = [4,6,7,7] Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]👨💻 Алгоритм:1⃣Инициализация и запуск функции обратного отслеживания Создайте множество для хранения результатов. Создайте список для хранения текущей последовательности. Запустите рекурсивную функцию обратного отслеживания с начальным индексом 0.2⃣Функция обратного отслеживания Если текущий индекс равен длине массива, проверьте длину текущей последовательности и добавьте её в результат, если она содержит не менее двух элементов. Если текущая последовательность остаётся неубывающей после добавления текущего элемента массива, добавьтеC# | LeetCode
10 сент., 16:11
Задача: 136. Single Number Сложность: easyДан непустой массив целых чисел nums, в котором каждый элемент встречается дважды, кроме одного. Найдите этот единственный элемент.Вы должны реализовать решение с линейной сложностью выполнения и использовать только постоянное дополнительное пространство.Пример: Input: nums = [2,2,1] Output: 1👨💻 Алгоритм:1⃣Переберите все элементы в массиве nums.2⃣Если какое-то число в nums новое для массива, добавьте его.3⃣Если какое-то число уже есть в массиве, удалите его.😎 Решение:C# | LeetCode
9 сент., 09:06
Задача: 1026. Maximum Difference Between Node and Ancestor Сложность: mediumУчитывая корень бинарного дерева, найдите максимальное значение v, для которого существуют различные вершины a и b, где v = |a.val - b.val| и a является предком b. Вершина a является предком b, если: любой ребенок a равен b или любой ребенок a является предком b.Пример: Input: root = [8,3,10,1,6,null,14,null,null,4,7,13] Output: 7👨💻 Алгоритм:1⃣Рекурсивный обход дерева: Используйте рекурсивную функцию для обхода дерева. Передавайте минимальное и максимальное значения, встреченные на пути от корня к текущему узлу.2⃣Обновление максимальной разницы: При посещении каждого узла обновляйте минимальное и максимальное значения. Вычисляйте разницу между текущим значением узла и минимальным и максимальным значениями на пути. Обновляйте максимальную разницу, если текущая разница больше.3⃣Рекурсивный вызов дляC# | LeetCode
8 сент., 16:11
Задача: №16. 3Sum Closest Сложность: mediumУчитывая целочисленный массив nums длины n и целочисленную цель, найдите три целых числа в nums, сумма которых наиболее близка к цели. Возвращает сумму трех целых чисел. Вы можете предположить, что каждый вход будет иметь ровно одно решение.Пример: Input: nums = [-1,2,1,-4], target = 1 Output: 2👨💻 Алгоритм:1⃣Отсортировать массив и инициализировать переменные для отслеживания минимальной разницы.2⃣Использовать два указателя (left и right) для поиска суммы трех чисел, обновляя их в зависимости от текущей суммы.3⃣Возвращать сумму, которая наиболее близка к target.😎 Решение: public class Solution { public int ThreeSumClosest(int[] nums, int target) {C# | LeetCode
1 сент., 16:10
Задача: 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) {C# | LeetCode
31 авг., 16:10
Задача: 665. Non-decreasing Array Сложность: mediumДан массив nums из n целых чисел. Ваша задача - проверить, можно ли сделать его неубывающим, изменив не более одного элемента.Мы определяем массив как неубывающий, если для каждого i (индексация с 0), такого что 0 <= i <= n - 2, выполняется условие nums[i] <= nums[i + 1].Пример: Input: nums = [4,2,3] Output: true Explanation: You could modify the first 4 to 1 to get a non-decreasing array.👨💻 Алгоритм:1⃣Инициализация переменных: Завести переменную count для подсчета числа изменений. Проверить последовательность чисел в массиве nums.2⃣Проверка условий: Если nums[i] > nums[i + 1], то увеличиваем count.C# | LeetCode
31 авг., 09:05
Задача: 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, пока количество нулей не станетC# | LeetCode
30 авг., 16:10
Задача: 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 треугольникC# | LeetCode
30 авг., 09:05
Задача: 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, которая содержит элементыC# | LeetCode
29 авг., 16:10
Задача: 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:C# | LeetCode
29 авг., 09:05
Задача: 1242. Web Crawler Multithreaded Сложность: mediumУчитывая URL startUrl и интерфейс HtmlParser, реализуйте многопоточный веб-краулер, который будет просматривать все ссылки, находящиеся под тем же именем хоста, что и startUrl. Верните все URL, полученные вашим веб-краулером, в любом порядке.Ваш краулер должен: Начинать со страницы: startUrl Вызывать HtmlParser.getUrls(url), чтобы получить все URL с веб-страницы данного URL. Не просматривать одну и ту же ссылку дважды. Исследовать только те ссылки, которые находятся под тем же именем хоста, что и startUrl.Пример: Input: urls = [ "http://news.yahoo.com", "http://news.yahoo.com/news", "http://news.yahoo.com/news/topics/", "http://news.google.com", "http://news.yahoo.com/us" ] edges = [[2,0],[2,1],[3,2],[3,1],[0,4]] startUrl = "http://news.yahoo.com/news/topics/" Output: [ "http://news.yahoo.com",C# | LeetCode
27 авг., 16:10
Задача: 347. Top K Frequent Elements Сложность: mediumДан массив целых чисел nums и целое число k. Верните k самых частых элементов. Вы можете вернуть ответ в любом порядке.Пример: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]👨💻 Алгоритм:1⃣Подсчет частоты: Используйте хеш-таблицу или словарь для подсчета количества вхождений каждого элемента в массиве nums.2⃣Создание кучи: Создайте кучу, чтобы отсортировать элементы по их частоте и выбрать k самых частых элементов.3⃣Возврат результата: Верните k самых частых элементов.C# | LeetCode
27 авг., 09:06
Задача: 1485. Clone Binary Tree With Random Pointer Сложность: mediumДано бинарное дерево, такое что каждый узел содержит дополнительный случайный указатель, который может указывать на любой узел в дереве или быть null. Верните глубокую копию дерева.Дерево представлено в том же формате ввода/вывода, что и обычные бинарные деревья, где каждый узел представлен в виде пары [val, random_index], где: - val: целое число, представляющее Node.val - random_index: индекс узла (во входных данных), на который указывает случайный указатель, или null, если он не указывает ни на один узел.Вам будет дано дерево в классе Node, и вы должны вернуть клонированное дерево в классе NodeCopy. Класс NodeCopy является клоном класса Node с такими же атрибутами и конструкторами.Пример: Input: root = [[1,null],null,[4,3],[7,0]] Output: [[1,null],null,[4,3],[7,0]] Explanation: The original binary tree isC# | LeetCode
26 авг., 16:10
Задача: 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⃣Создание узлов: Создайте новые узлы на основе уровня и значения из строки.C# | LeetCode
26 авг., 09:06
Задача: 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.👨💻 Алгоритм:1⃣Проверьте, является ли k-й отсутствующий номер меньше первого элемента массива. Если это так, верните k. Уменьшите k на количество положительных чисел, отсутствующих до начала массива: k -= arr[0] - 1.2⃣Итерируйтесь по элементам массива. На каждом шаге вычисляйте количество отсутствующих положительных чисел между i+1-м и i-м элементами: currMissing = arr[i + 1] - arr[i] - 1. Сравните k с currMissing. Если k <= currMissing, то число для возврата находится
