Kotlin | LeetCode

Задача: 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⃣Проверка остатка изменений: Если после первого прохода остались изменения (k нечетное), то найдите минимальное значение в измененном массиве и еще раз поменяйте его знак. Это обеспечит максимальную сумму. 😎 Решение: class Solution { fun largestSumAfterKNegations(nums: IntArray, k: Int): Int { nums.sort() var k = k for (i in nums.indices) { if (k > 0 && nums[i] < 0) { nums[i] = -nums[i] k-- } } if (k % 2 == 1) { nums.sort() nums[0] = -nums[0] } return nums.sum() } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 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: words = ["abcd","cdab","cbad","xyzz","zzxy","zzyx"] Output: 3 👨💻 Алгоритм: 1⃣Для каждой строки в массиве words создать два новых списка: один из символов на четных позициях, другой из символов на нечетных позициях. Отсортировать оба списка и объединить их в одну строку, которая будет представлять каноническую форму строки. 2⃣Использовать множество, чтобы хранить все уникальные канонические формы строк. 3⃣Размер множества будет равен количеству групп специально-эквивалентных строк. 😎 Решение: fun numSpecialEquivGroups(words: Array): Int { val uniqueForms = mutableSetOf() for (word in words) { val evenChars = word.filterIndexed { index, _ -> index % 2 == 0 }.toCharArray().sorted() val oddChars = word.filterIndexed { index, _ -> index % 2 != 0 }.toCharArray().sorted() val canonicalForm = evenChars.joinToString("") + oddChars.joinToString("") uniqueForms.add(canonicalForm) } return uniqueForms.size Ставь 👍 и забирай 📚 Базу знаний

Задача: 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⃣Поиск следующего большего элемента: Итерируйте по массиву значений узлов. Для каждого элемента, пока стек не пуст и текущий элемент больше, чем элемент на вершине стека, обновите массив ответов значением текущего элемента и удалите элемент из стека. Добавьте текущий индекс в стек. 3⃣Заполнение оставшихся значений: Для всех индексов, оставшихся в стеке, установите значение ответа равным 0, так как для них не найдено большего элемента. 😎 Решение: class ListNode(var `val`: Int) { var next: ListNode? = null } class Solution { fun nextLargerNodes(head: ListNode?): IntArray { val values = mutableListOf() var current = head while (current != null) { values.add(current.`val`) current = current.next } val answer = IntArray(values.size) val stack = mutableListOf() for (i in values.indices) { while (stack.isNotEmpty() && values[stack.last()] < values[i]) { answer[stack.removeAt(stack.size - 1)] = values[i] } stack.add(i) } return answer } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 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.size var i = n - 2 while (i >= 0 && arr[i] = arr[i] || (j < n - 1 && arr[j] == arr[j + 1])) { j-- } val temp = arr[i] arr[i] = arr[j] arr[j] = temp return arr } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1197. Minimum Knight Moves Сложность: medium На бесконечной шахматной доске с координатами от -бесконечности до +бесконечности у вас есть конь на клетке [0, 0]. У коня есть 8 возможных ходов. Каждый ход представляет собой два квадрата в кардинальном направлении, затем один квадрат в ортогональном направлении. Верните минимальное количество шагов, необходимых для перемещения коня на клетку [x, y]. Гарантируется, что ответ существует. Пример: Input: x = 5, y = 5 Output: 4 Explanation: [0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5] 👨💻 Алгоритм: 1⃣Инициализация структур данных: Инициализируйте две очереди для хранения координат и расстояний: одну для движения от начальной точки, другую — от конечной точки. Инициализируйте две карты для хранения посещенных координат и расстояний: одну для движения от начальной точки, другую — от конечной точки. 2⃣Реализация двунаправленного поиска в ширину (BFS): Выполняйте шаги из очередей, расширяя круги поиска как от начальной, так и от конечной точки. Если круги пересекаются, возвращайте сумму расстояний до точки пересечения. 3⃣Расширение кругов поиска: Для каждой текущей точки из очередей расширяйте круг поиска по всем возможным ходам коня. Обновляйте расстояния и добавляйте новые точки в очереди, если они еще не были посещены. Увеличивайте units на значение, извлеченное из кучи. 😎 Решение: class Solution { fun minKnightMoves(x: Int, y: Int): Int { val offsets = arrayOf( intArrayOf(1, 2), intArrayOf(2, 1), intArrayOf(2, -1), intArrayOf(1, -2), intArrayOf(-1, -2), intArrayOf(-2, -1), intArrayOf(-2, 1), intArrayOf(-1, 2) ) val originQueue: Deque = LinkedList() originQueue.add(intArrayOf(0, 0, 0)) val originDistance = mutableMapOf("0,0" to 0) val targetQueue: Deque = LinkedList() targetQueue.add(intArrayOf(x, y, 0)) val targetDistance = mutableMapOf("$x,$y" to 0) while (true) { val origin = originQueue.removeFirst() val originKey = "${origin[0]},${origin[1]}" if (targetDistance.containsKey(originKey)) { return origin[2] + targetDistance[originKey]!! } val target = targetQueue.removeFirst() val targetKey = "${target[0]},${target[1]}" if (originDistance.containsKey(targetKey)) { return target[2] + originDistance[targetKey]!! } for (offset in offsets) { val nextOrigin = intArrayOf(origin[0] + offset[0], origin[1] + offset[1], origin[2] + 1) val nextOriginKey = "${nextOrigin[0]},${nextOrigin[1]}" if (!originDistance.containsKey(nextOriginKey)) { originQueue.add(nextOrigin) originDistance[nextOriginKey] = nextOrigin[2] } val nextTarget = intArrayOf(target[0] + offset[0], target[1] + offset[1], target[2] + 1) val nextTargetKey = "${nextTarget[0]},${nextTarget[1]}" if (!targetDistance.containsKey(nextTargetKey)) { targetQueue.add(nextTarget) targetDistance[nextTargetKey] = nextTarget[2] } } } } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit Сложность: medium Дан массив целых чисел nums и целое число limit. Вернуть размер самой длинной непустой подстроки, такая что абсолютная разница между любыми двумя элементами этой подстроки меньше или равна limit. Пример: Input: nums = [8,2,4,7], limit = 4 Output: 2 Explanation: All subarrays are: [8] with maximum absolute diff |8-8| = 0 4. [8,2,4] with maximum absolute diff |8-2| = 6 > 4. [8,2,4,7] with maximum absolute diff |8-2| = 6 > 4. [2] with maximum absolute diff |2-2| = 0

Задача: 644. Maximum Average Subarray II Сложность: hard Вам дан целочисленный массив nums, состоящий из n элементов, и целое число k. Найдите смежный подмассив, длина которого больше или равна k и который имеет максимальное среднее значение, и верните это значение. Принимается любой ответ с погрешностью вычислений менее 10-5. Пример: Input: nums = [1,12,-5,-6,50,3], k = 4 Output: 12.75000 👨💻 Алгоритм: 1⃣Используйте скользящее окно длины k для нахождения начального среднего значения. 2⃣Перемещайте окно по массиву, добавляя следующий элемент и убирая предыдущий, обновляя текущее среднее значение. 3⃣Следите за максимальным средним значением и верните его после проверки всех возможных окон. 😎 Решение: fun findMaxAverage(nums: IntArray, k: Int): Double { var currSum = nums.take(k).sum() var maxSum = currSum for (i in k until nums.size) { currSum += nums[i] - nums[i - k] if (currSum > maxSum) { maxSum = currSum } } return maxSum.toDouble() / k } Ставь 👍 и забирай 📚 Базу знаний

Задача: 897. Increasing Order Search Tree Сложность: easy Задав корень дерева двоичного поиска, перестройте дерево по порядку так, чтобы самый левый узел дерева теперь был корнем дерева, а каждый узел не имел левого и только одного правого дочернего узла. Пример: Input: root = [5,3,6,2,4,null,8,1,null,null,null,7,9] Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9] 👨💻 Алгоритм: 1⃣Выполнить обход дерева в порядке in-order, чтобы получить список узлов. 2⃣Перестроить дерево, устанавливая каждый узел из списка как правый дочерний элемент предыдущего узла и устанавливая левые дочерние элементы в null. 3⃣Вернуть новый корень дерева (первый элемент списка). 😎 Решение: class TreeNode(var `val`: Int = 0) { var left: TreeNode? = null var right: TreeNode? = null } fun increasingBST(root: TreeNode?): TreeNode? { val nodes = mutableListOf() fun inorder(node: TreeNode?) { if (node == null) return inorder(node.left) nodes.add(node) inorder(node.right) } inorder(root) for (i in 0 until nodes.size - 1) { nodes[i].left = null nodes[i].right = nodes[i + 1] } nodes.last().left = null nodes.last().right = null return nodes.first() Ставь 👍 и забирай 📚 Базу знаний

Задача: 1253. Reconstruct a 2-Row Binary Matrix Сложность: medium Даны следующие сведения о матрице с n столбцами и 2 строками: Матрица является двоичной, то есть каждый элемент матрицы может быть 0 или 1. Сумма элементов 0-й (верхней) строки задана как upper. Сумма элементов 1-й (нижней) строки задана как lower. Сумма элементов i-го столбца (индексированного 0) - colsum[i], где colsum - целочисленный массив длины n. Ваша задача - восстановить матрицу с upper, lower и colsum. Вернуть ее в виде двумерного целочисленного массива. Если существует более одного правильного решения, будет принято любое из них. Если правильного решения не существует, верните пустой двумерный массив. Пример: Input: upper = 2, lower = 1, colsum = [1,1,1] Output: [[1,1,0],[0,0,1]] 👨💻 Алгоритм: 1⃣Инициализируйте две строки матрицы длины n с нулями. 2⃣Пройдите по массиву colsum и распределите значения 2 по обеим строкам, уменьшая upper и lower. Пройдите по массиву colsum и распределите значения 1 по строкам, уменьшая соответствующие upper или lower. 3⃣Проверьте, что остатки upper и lower равны нулю. Если все шаги выполнены успешно, верните восстановленную матрицу, иначе верните пустую матрицу. 😎 Решение: class Solution { fun reconstructMatrix(upper: Int, lower: Int, colsum: IntArray): List • > { var upper = upper var lower = lower val n = colsum.size val top = IntArray(n) val bottom = IntArray(n) for (i in colsum.indices) { if (colsum[i] == 2) { if (upper > 0 && lower > 0) { top[i] = 1 bottom[i] = 1 upper-- lower-- } else { return emptyList() } } } for (i in colsum.indices) { if (colsum[i] == 1) { if (upper > lower) { if (upper > 0) { top[i] = 1 upper-- } else { return emptyList() } } else { if (lower > 0) { bottom[i] = 1 lower-- } else { return emptyList() } } } } if (upper == 0 && lower == 0) { return listOf(top.toList(), bottom.toList()) } else { return emptyList() } } } Ставь 👍 и забирай 📚 Базу знаний