Latest posts
Kotlin | LeetCode
22 Sept, 16:11
Задача: 859. Buddy Strings Сложность: easyДаны две строки s и goal. Верните true, если вы можете поменять местами две буквы в s так, чтобы результат был равен goal, в противном случае верните false.Обмен буквами определяется как взятие двух индексов i и j (нумерация с 0), таких что i != j, и обмен символов в s[i] и s[j].Например, обмен символов на индексах 0 и 2 в строке "abcd" приводит к "cbad".Пример: Input: s = "ab", goal = "ba" Output: true Explanation: You can swap s[0] = 'a' and s[1] = 'b' to get "ba", which is equal to goal.👨💻 Алгоритм:1⃣Если количество символов в строках s и goal разное, возвращаем false. Если s == goal, используем хеш-таблицу или массив из 26 элементов для хранения частоты каждого символа в строке s. Если какой-либо символ встречается более одного раза, можно поменять местами две одинаковые буквы, возвращаем true. Иначе возвращаем false.2⃣Иначе,Kotlin | LeetCode
22 Sept, 09:06
Задача: 1214. Two Sum BSTs Сложность: mediumДаны корни двух бинарных деревьев поиска, root1 и root2, верните true, если и только если существует узел в первом дереве и узел во втором дереве, значения которых в сумме равны заданному целому числу target.Пример: Input: root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18 Output: false👨💻 Алгоритм:1⃣Создайте два пустых множества node_set1 и node_set2. Выполните обход дерева root1, добавляя значения каждого узла в node_set1, и выполните обход дерева root2, добавляя значения каждого узла в node_set2.2⃣Итерация по элементам в node_set1: для каждого элемента value1 проверяйте, находится ли target - value1 в node_set2.3⃣Если target - value1 находится в node_set2, верните true. Если после завершения итерации не найдено ни одной подходящей пары, верните false.😎 Решение: class TreeNode(var val: Int) { var left: TreeNode? = nullKotlin | LeetCode
21 Sept, 09:06
Задача: 1155. Number of Dice Rolls With Target Sum Сложность: mediumУ вас есть n кубиков, и на каждом кубике k граней, пронумерованных от 1 до k.Даны три целых числа n, k и target. Необходимо вернуть количество возможных способов (из общего количества kn способов) выбросить кубики так, чтобы сумма выпавших чисел равнялась target. Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7.Пример: Input: n = 1, k = 6, target = 3 Output: 1 Explanation: You throw one die with 6 faces. There is only one way to get a sum of 3.👨💻 Алгоритм:1⃣Начните с:Индекс кубика diceIndex равен 0; это индекс кубика, который мы рассматриваем в данный момент. Сумма чисел на предыдущих кубиках currSum равна 0. Инициализируйте переменную ways значением 0. Итерируйтесь по значениям от 1 до k для каждого значения i. Если текущий кубик может иметь значение i, т.е. currSum послеKotlin | LeetCode
20 Sept, 09:06
Задача: 1033. Moving Stones Until Consecutive Сложность: mediumНа оси X расположены три камня в разных позициях. Вам даны три целых числа a, b и c - позиции камней. За одно движение вы берете камень в конечной точке (т. е. либо в самой низкой, либо в самой высокой позиции камня) и перемещаете его в незанятую позицию между этими конечными точками. Формально, допустим, камни в данный момент находятся в позициях x, y и z, причем x < y < z. Вы берете камень в позиции x или z и перемещаете его в целочисленную позицию k, причем x < k < z и k != y. Игра заканчивается, когда вы больше не можете сделать ни одного хода (то есть камни находятся в трех последовательных позициях). Возвращается целочисленный массив answer длины 2, где: answer[0] - минимальное количество ходов, которое вы можете сыграть, а answer[1] - максимальное количество ходов, которое вы можете сыграть.Пример: Input: a = 3, bKotlin | LeetCode
19 Sept, 09:06
Задача: 820. Short Encoding of Words Сложность: mediumДопустимым кодированием массива слов является любая опорная строка s и массив индексов indices, такие что:words.length == indices.length Опорная строка s заканчивается символом '#'. Для каждого индекса indices[i], подстрока строки s, начинающаяся с indices[i] и заканчивающаяся (но не включительно) следующим символом '#', равна words[i]. Дан массив слов, верните длину самой короткой возможной опорной строки s для любого допустимого кодирования слов.Пример: Input: words = ["time", "me", "bell"] Output: 10 Explanation: A valid encoding would be s = "time#bell#" and indices = [0, 2, 5]. words[0] = "time", the substring of s starting from indices[0] = 0 to the next '#' is underlined in "time#bell#" words[1] = "me", the substring of s starting from indices[1] = 2 to the next '#' is underlined in "time#bell#" words[2] = "bell", theKotlin | LeetCode
16 Sept, 09:06
Задача: 189. Rotate Array Сложность: mediumДля целочисленного массива nums, поверните массив вправо на k шагов, где k — неотрицательное число.Пример: Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4]👨💻 Алгоритм:1⃣Создаем дополнительный массив, в который будем помещать каждый элемент исходного массива на его новую позицию. Элемент на позиции i в исходном массиве будет размещен на индексе (i+k) % длина массива.2⃣Копируем элементы из нового массива в исходный массив, сохраняя новый порядок элементов.3⃣Заменяем исходный массив полученным результатом, завершая процесс поворота массива.Kotlin | LeetCode
15 Sept, 16:11
Задача: 210. Course Schedule II Сложность: mediumВсего есть numCourses курсов, которые вы должны пройти, пронумерованных от 0 до numCourses - 1. Вам дан массив prerequisites, где prerequisites[i] = [ai, bi] указывает на то, что вы должны сначала пройти курс bi, если хотите взять курс ai. Например, пара [0, 1] указывает на то, что для прохождения курса 0 сначала нужно пройти курс 1. Верните порядок курсов, которые вы должны пройти, чтобы завершить все курсы. Если существует несколько правильных ответов, верните любой из них. Если невозможно завершить все курсы, верните пустой массив.Пример: Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] Output: [0,2,1,3] Объяснение: Всего есть 4 курса, которые нужно пройти. Чтобы взять курс 3, вы должны завершить оба курса 1 и 2. Оба курса 1 и 2 должны быть взяты после того, как вы завершите курс 0. Таким образом, один из правильныхKotlin | LeetCode
15 Sept, 09:06
Задача: 1031. Maximum Sum of Two Non-Overlapping Subarrays Сложность: mediumЕсли задан целочисленный массив nums и два целых числа firstLen и secondLen, верните максимальную сумму элементов в двух непересекающихся подмассивах с длинами firstLen и secondLen. Массив с длиной firstLen может находиться до или после массива с длиной secondLen, но они должны быть непересекающимися. Подмассив - это смежная часть массива.Пример: Input: nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2 Output: 20👨💻 Алгоритм:1⃣Предварительные вычисления: Вычислите сумму всех подмассивов длины firstLen и secondLen и сохраните их в списках.2⃣Поиск максимальной суммы: Переберите все возможные позиции для подмассива длины firstLen и для каждого такого подмассива найдите максимальную сумму для подмассива длины secondLen, который не пересекается с текущим подмассивом длины firstLen.3⃣Сравнение двухKotlin | LeetCode
14 Sept, 16:11
Задача: 1361. Validate Binary Tree Nodes Сложность: easyУ вас есть n узлов бинарного дерева, пронумерованных от 0 до n-1, где узел i имеет двух детей: leftChild[i] и rightChild[i]. Верните true, если и только если все заданные узлы образуют ровно одно допустимое бинарное дерево.Если у узла i нет левого ребенка, то leftChild[i] будет равен -1, аналогично для правого ребенка.Обратите внимание, что узлы не имеют значений и мы используем только номера узлов в этой задаче.Пример: Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1] Output: true👨💻 Алгоритм:1⃣Проверка количества родителей для каждого узла: Создайте массив для отслеживания количества родителей для каждого узла. Проходите через leftChild и rightChild, увеличивая счетчик для каждого ребенка. Если какой-либо узел имеет более одного родителя, возвращайте false.2⃣Поиск корневого узла и проверка наKotlin | LeetCode
11 Sept, 16:11
Задача: 710. Random Pick with Blacklist Сложность: hardВам дано целое число n и массив уникальных целых чисел blacklist. Разработайте алгоритм выбора случайного целого числа из диапазона [0, n - 1], не входящего в черный список. Любое целое число, находящееся в указанном диапазоне и не входящее в черный список, должно с равной вероятностью быть возвращено. Оптимизируйте алгоритм так, чтобы он минимизировал количество обращений к встроенной функции random вашего языка. Реализуйте класс Solution: Solution(int n, int[] blacklist) Инициализирует объект целым числом n и целым числом из черного списка blacklist. int pick() Возвращает случайное целое число в диапазоне [0, n - 1] и не входящее в черный список.Пример: Input ["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"] [[7, [2, 3, 5]], [], [], [], [], [], [], []] Output [null, 0, 4, 1, 6, 1, 0, 4]👨💻 Алгоритм:1⃣СоKotlin | LeetCode
10 Sept, 16:11
Задача: 634. Find the Derangement of An Array Сложность: hardВ комбинаторной математике отклонение - это перестановка элементов множества таким образом, что ни один элемент не оказывается на прежнем месте. Вам дано целое число n. Изначально имеется массив, состоящий из n целых чисел от 1 до n в порядке возрастания, верните количество отклонений, которые он может породить. Поскольку ответ может быть огромным, верните его по модулю 109 + 7.Пример: Input: n = 3 Output: 2👨💻 Алгоритм:1⃣Инициализация массива для хранения результатов Создайте массив dp для хранения количества отклонений для каждого значения от 0 до n. Установите начальные значения: dp[0] = 1 и dp[1] = 0.2⃣Вычисление количества отклонений Используйте динамическое программирование для вычисления количества отклонений для каждого значения от 2 до n. Формула для вычисления: dp[i] = (i - 1) (dp[i - 1] + dp[i - 2]) %Kotlin | LeetCode
10 Sept, 09:06
Задача: 340. Longest Substring with At Most K Distinct Characters Сложность: mediumДана строка s и целое число k. Верните длину самой длинной подстроки s, которая содержит не более k различных символов.Пример: Input: n = 27 Output: true Explanation: 27 = 3^3👨💻 Алгоритм:1⃣Инициализация Используйте два указателя (left и right) для отслеживания текущего окна в строке. Создайте словарь для отслеживания количества каждого символа в текущем окне. Инициализируйте переменные для хранения максимальной длины подстроки (max_length).2⃣Раздвижение окна Перемещайте правый указатель (right) по строке и обновляйте словарь. Если количество различных символов в словаре превышает k, перемещайте левый указатель (left) вправо, уменьшая счетчик символов, пока количество различных символов снова не станет меньше или равно k.3⃣Обновление максимальной длины На каждом шаге проверяйте и обновляйтеKotlin | LeetCode
9 Sept, 09:06
Задача: 1512. Number of Good Pairs Сложность: easyДан массив целых чисел nums, верните количество хороших пар.Пара (i, j) называется хорошей, если nums[i] == nums[j] и i < j.Пример: Input: nums = [1,2,3,1,1,3] Output: 4 Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.👨💻 Алгоритм:1⃣Инициализируйте переменную ans значением 0.2⃣Итерируйте i от 0 до nums.length: Итерируйте j от i + 1 до nums.length: Если nums[i] == nums[j], увеличьте ans на 1.Kotlin | LeetCode
8 Sept, 16:11
Задача: 661. Image Smoother Сложность: easyДан целочисленный матрица img размером m x n, представляющая градации серого изображения. Верните изображение после применения сглаживания к каждой его ячейке.Пример: Input: img = [[1,1,1],[1,0,1],[1,1,1]] Output: [[0,0,0],[0,0,0],[0,0,0]] Explanation: For the points (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0 For the points (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0 For the point (1,1): floor(8/9) = floor(0.88888889) = 0👨💻 Алгоритм:1⃣Инициализация: Создайте новую матрицу такого же размера, чтобы сохранить результат сглаживания.2⃣Обработка каждой ячейки: Для каждой ячейки исходной матрицы найдите всех её соседей (включая саму ячейку).Kotlin | LeetCode
6 Sept, 09:06
Задача: 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 самых частых элементов.Kotlin | LeetCode
31 Aug, 09:06
Задача: 1005. Maximize Sum Of Array After K Negations Сложность: easyУчитывая целочисленный массив nums и целое число k, измените массив следующим образом: выберите индекс i и замените nums[i] на -nums[i]. Вы должны применить этот процесс ровно k раз. Вы можете выбрать один и тот же индекс i несколько раз. Верните наибольшую возможную сумму массива после его модификации таким образом.Пример: Input: nums = [4,2,3], k = 1 Output: 5👨💻 Алгоритм:1⃣Сортировка массива: Отсортируйте массив nums по возрастанию, чтобы наибольшее количество раз менять самые маленькие (отрицательные) значения на их противоположные.2⃣Модификация массива: Пройдитесь по отсортированному массиву и замените k наименьших значений на их противоположные (умножьте на -1). Если встретите 0, прекратите дальнейшие изменения, так как изменение 0 на -0 не имеет смысла.3⃣Проверка остатка изменений: Если послеKotlin | LeetCode
30 Aug, 16:11
Задача: 893. Groups of Special-Equivalent Strings Сложность: mediumВам дан массив строк одинаковой длины words. За один ход вы можете поменять местами любые два четных или любые два нечетных символа строки words[i]. Две строки words[i] и words[j] являются специально-эквивалентными, если после любого количества ходов words[i] == words[j].Например, words[i] = "zzxy" и words[j] = "xyzz" являются специально-эквивалентными, потому что мы можем делать ходы "zzxy" -> "xzzy" -> "xyzz". Группа специально-эквивалентных строк из слов - это непустое подмножество слов, такое, что: каждая пара строк в группе специально-эквивалентна, и группа имеет максимально возможный размер (т.е, не существует строки words[i], не входящей в группу, такой, что words[i] является специально-эквивалентной каждой строке в группе). Верните количество групп специально-эквивалентных строк из слов.Пример: Input: wordsKotlin | LeetCode
26 Aug, 09:06
Задача: 1019. Next Greater Node In Linked List Сложность: mediumВам дана голова связного списка с n узлами. Для каждого узла в списке найдите значение следующего большего узла. То есть для каждого узла найдите значение первого узла, который находится рядом с ним и имеет строго большее значение, чем он. Верните целочисленный массив answer, где answer[i] - это значение следующего большего узла ith-узла (с индексацией по 1). Если у узла ith нет следующего большего узла, установите answer[i] = 0.Пример: Input: head = [2,1,5] Output: [5,5,0]👨💻 Алгоритм:1⃣Инициализация переменных: Пройдитесь по всему списку и сохраните значения узлов в массив. Инициализируйте стек для хранения индексов узлов, которые нужно обработать.2⃣Поиск следующего большего элемента: Итерируйте по массиву значений узлов. Для каждого элемента, пока стек не пуст и текущий элемент больше, чем элемент на вершинеKotlin | LeetCode
23 Aug, 16:10
Задача: 1053. Previous Permutation With One Swap Сложность: mediumУчитывая массив целых положительных чисел arr (не обязательно различных), верните лексикографически наибольшую перестановку, которая меньше arr и может быть сделана ровно с одной подстановкой. Если это невозможно, то верните тот же массив. Обратите внимание, что перестановка меняет местами два числа arr[i] и arr[j].Пример: Input: arr = [3,2,1] Output: [3,1,2]👨💻 Алгоритм:1⃣Определи общее количество покупателей, которые удовлетворены в минуты, когда владелец магазина не ворчлив.2⃣Пройди по массиву, используя скользящее окно для учета эффекта от техники.3⃣Найди максимальное количество дополнительных удовлетворенных покупателей, которые можно получить, используя технику на k минут подряд.😎 Решение: fun prevPermOpt1(arr: IntArray): IntArray { val n = arr.sizeKotlin | LeetCode
23 Aug, 09:06
Задача: 1049. Last Stone Weight II Сложность: mediumВам дан массив целых чисел stones, где stones[i] - вес i-го камня. Мы играем в игру с камнями. На каждом ходу мы выбираем два любых камня и разбиваем их вместе. Предположим, что камни имеют веса x и y, причем x <= y. Результат разбивания таков: если x == y, оба камня уничтожаются, а если x != y, камень веса x уничтожается, а камень веса y приобретает новый вес y - x. В конце игры остается не более одного камня. Верните наименьший возможный вес оставшегося камня. Если камней не осталось, верните 0.Пример: Input: stones = [2,7,4,1,8,1] Output: 1👨💻 Алгоритм:1⃣Используй метод динамического программирования, чтобы проверить, можно ли разделить камни на две группы с равной суммой.2⃣Определи, какие веса можно достичь, используя половину суммы всех камней.3⃣Найди наибольшую достижимую сумму, которая меньше или равна половине
Related Channels
Other channels in the same section of the catalogue.
