Kotlin | LeetCode

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

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1049. Last Stone Weight II
Сложность: medium

Вам дан массив целых чисел stones, где stones[i] - вес i-го камня. Мы играем в игру с камнями. На каждом ходу мы выбираем два любых камня и разбиваем их вместе. Предположим, что камни имеют веса x и y, причем x

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

Ставь 👍 и забирай 📚 Базу знаний

Задача: 983. Minimum Cost For Tickets
Сложность: medium

Вы запланировали несколько поездок на поезде за год вперёд. Дни года, в которые вы будете путешествовать, заданы в виде целочисленного массива days. Каждый день — это целое число от 1 до 365.

Билеты на поезд продаются тремя различными способами:

однодневный билет продаётся за costs[0] долларов,
семидневный билет продаётся за costs[1] долларов, и
тридцатидневный билет продаётся за costs[2] долларов.
Билеты позволяют путешествовать указанное количество дней подряд.

Например, если мы покупаем семидневный билет на 2-й день, то мы можем путешествовать в течение 7 дней: 2, 3, 4, 5, 6, 7 и 8.
Верните минимальное количество долларов, которое вам нужно, чтобы путешествовать каждый день, указанный в списке days.

Пример:
Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation: For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
In total, you spent $11 and covered all the days of your travel.

👨‍💻 Алгоритм:

1⃣Создайте массив dp размером на один больше последнего дня, в который нужно путешествовать. Инициализируйте все значения -1, что означает, что ответ для этого дня ещё не был вычислен. Также создайте хэш-набор isTravelNeeded из days.

2⃣Создайте функцию solve, которая принимает аргумент currDay. Если currDay больше последнего дня, когда нужно путешествовать, просто верните 0, так как все дни уже покрыты. Если currDay отсутствует в isTravelNeeded, перейдите к currDay + 1. Если ответ для currDay в массиве dp не равен -1, это означает, что ответ уже был вычислен, поэтому просто верните его.

3⃣Найдите стоимость трёх билетов, которые можно использовать в этот день, добавьте соответствующую стоимость и обновите dp[currDay] соответственно в рекурсивном вызове. Вызовите solve, передав currDay = 1, и верните ответ.

😎 Решение:
class Solution {
private val isTravelNeeded = mutableSetOf()

private fun solve(dp: IntArray, days: IntArray, costs: IntArray, currDay: Int): Int {
if (currDay > days.last()) {
return 0
}

if (currDay !in isTravelNeeded) {
return solve(dp, days, costs, currDay + 1)
}

if (dp[currDay] != -1) {
return dp[currDay]
}

val oneDay = costs[0] + solve(dp, days, costs, currDay + 1)
val sevenDay = costs[1] + solve(dp, days, costs, currDay + 7)
val thirtyDay = costs[2] + solve(dp, days, costs, currDay + 30)

dp[currDay] = minOf(oneDay, minOf(sevenDay, thirtyDay))
return dp[currDay]
}

fun mincostTickets(days: IntArray, costs: IntArray): Int {
val lastDay = days.last()
val dp = IntArray(lastDay + 1) { -1 }

for (day in days) {
isTravelNeeded.add(day)
}

return solve(dp, days, costs, 1)
}
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 901. Online Stock Span
Сложность: medium

Разработайте алгоритм, который собирает ежедневные котировки цен на некоторые акции и возвращает размах цены этой акции за текущий день. Размах цены акции за один день - это максимальное количество дней подряд (начиная с этого дня и в обратном направлении), в течение которых цена акции была меньше или равна цене этого дня.

Например, если цены акции за последние четыре дня равны [7,2,1,2], а цена акции сегодня равна 2, то размах сегодняшнего дня равен 4, поскольку, начиная с сегодняшнего дня, цена акции была меньше или равна 2 в течение 4 дней подряд.
Также, если цена акции за последние четыре дня равна [7,34,1,2], а цена акции сегодня равна 8, то размах сегодняшнего дня равен 3, так как начиная с сегодняшнего дня цена акции была меньше или равна 8 в течение 3 дней подряд. Реализация класса StockSpanner: StockSpanner() Инициализирует объект класса. int next(int price) Возвращает размах цены акции, учитывая, что сегодняшняя цена равна price.

Пример:
Input
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
Output
[null, 1, 1, 1, 2, 1, 4, 6]

👨‍💻 Алгоритм:

1⃣Инициализировать стек для хранения пар значений (цена, размах) и переменную для текущего индекса.

2⃣Для метода next:
Установить начальный размах текущего дня равным 1.
Пока стек не пуст и верхний элемент стека имеет цену меньше или равную текущей цене:
Добавить размах верхнего элемента стека к текущему размаху.
Удалить верхний элемент стека.

3⃣Добавить текущую цену и размах на вершину стека.
Вернуть текущий размах.

😎 Решение:
class StockSpanner {
private val stack = mutableListOf()

fun next(price: Int): Int {
var span = 1
while (stack.isNotEmpty() && stack.last().first

Задача: 506. Relative Ranks
Сложность: easy

Вам дан целочисленный массив score размером n, где score[i] — это результат i-го спортсмена на соревновании. Все результаты гарантированно уникальны.
Спортсмены размещаются на основе своих результатов: спортсмен, занявший 1-е место, имеет наивысший результат, спортсмен, занявший 2-е место, имеет второй по величине результат и так далее. Размещение каждого спортсмена определяет его ранг:
Ранг спортсмена, занявшего 1-е место, — "Gold Medal".
Ранг спортсмена, занявшего 2-е место, — "Silver Medal".
Ранг спортсмена, занявшего 3-е место, — "Bronze Medal".
Для спортсменов, занявших с 4-го по n-е место, их ранг соответствует их номеру в размещении (т.е. ранг спортсмена, занявшего x-е место, — "x").
Верните массив answer размером n, где answer[i] — это ранг i-го спортсмена.

Пример:
Input: score = [5,4,3,2,1]
Output: ["Gold Medal","Silver Medal","Bronze Medal","4","5"]
Explanation: The placements are [1st, 2nd, 3rd, 4th, 5th].

👨‍💻 Алгоритм:

1⃣Инициализация и нахождение максимального значения
Инициализируйте переменную N длиной массива score. Определите функцию findMax, которая находит максимальный балл в массиве score.

2⃣Создание вспомогательных структур
Инициализируйте массив scoreToIndex размером M + 1, где M — это максимальное значение в массиве score. Заполните scoreToIndex таким образом, чтобы для каждого score[i] его индекс сохранялся в scoreToIndex[score[i]].

3⃣Присваивание рангов и формирование ответа
Создайте массив rank для хранения рангов спортсменов. Используйте цикл для присваивания медалей и рангов в зависимости от значений в scoreToIndex, начиная с наибольшего.

😎 Решение:
class Solution {
fun findRelativeRanks(score: IntArray): Array {
val N = score.size
val maxScore = score.maxOrNull()!!
val scoreToIndex = IntArray(maxScore + 1)

for (i in score.indices) {
scoreToIndex[score[i]] = i + 1
}

val MEDALS = arrayOf("Gold Medal", "Silver Medal", "Bronze Medal")
val rank = Array(N) { "" }
var place = 1

for (i in maxScore downTo 0) {
if (scoreToIndex[i] != 0) {
val originalIndex = scoreToIndex[i] - 1
rank[originalIndex] = if (place < 4) MEDALS[place - 1] else place.toString()
place++
}
}

return rank
}
}

Ставь 👍 и забирай 📚 Базу знаний

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

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1480. Running Sum of 1d Array
Сложность: easy

Дан массив nums. Мы определяем текущую сумму массива как runningSum[i] = сумма(nums[0]…nums[i]).

Верните массив текущих сумм для nums.

Пример:
Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

👨‍💻 Алгоритм:

1⃣Инициализация:
Определите массив result.
Инициализируйте первый элемент массива result первым элементом входного массива nums.

2⃣Вычисление текущих сумм:
На индексе i добавьте сумму элемента nums[i] и предыдущей текущей суммы result[i - 1] в массив result.

3⃣Повторение для всех индексов:
Повторите шаг 2 для всех индексов от 1 до n-1.

😎 Решение:
class Solution {
fun runningSum(nums: IntArray): IntArray {
val result = IntArray(nums.size)
result[0] = nums[0]
for (i in 1 until nums.size) {
result[i] = result[i - 1] + nums[i]
}
return result
}
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 152. Maximum Product Subarray
Сложность: medium

Дан массив целых чисел nums. Найдите подмассив, который имеет наибольший произведение, и верните это произведение.

Тестовые случаи созданы таким образом, что ответ поместится в 32-битное целое число.

Пример:
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
👨‍💻 Алгоритм:

1⃣Если массив nums пуст, возвращаем 0, так как нет элементов для обработки.
Инициализируем переменную result первым элементом массива, чтобы иметь начальную точку сравнения для нахождения максимального произведения.

2⃣Используем вложенные циклы для обработки всех возможных подмассивов:
Внешний цикл i начинается с начала массива и определяет начальную точку каждого подмассива.
Внутренний цикл j начинается с индекса i и идет до конца массива, последовательно умножая элементы и расширяя рассматриваемый подмассив.

3⃣Для каждой итерации внутреннего цикла умножаем текущий элемент nums[j] на аккумулирующую переменную accu и проверяем, не стало ли текущее произведение больше максимального найденного до этого.
Обновляем переменную result, если текущее произведение accu превышает текущее максимальное значение result.

😎 Решение:
class Solution {
fun maxProduct(nums: IntArray): Int {
if (nums.isEmpty()) return 0

var result = nums[0]

for (i in nums.indices) {
var accu = 1
for (j in i until nums.size) {
accu *= nums[j]
result = maxOf(result, accu)
}
}

return result
}
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 305. Number of Islands II
Сложность: hard

Дан пустой двумерный бинарный массив grid размером m x n. Этот массив представляет собой карту, где 0 означает воду, а 1 — сушу. Изначально все ячейки массива — водные (т.е. все ячейки содержат 0).
Вы можете выполнить операцию "добавить землю", которая превращает воду в указанной позиции в сушу. Вам дан массив positions, где positions[i] = [ri, ci] — позиция (ri, ci), в которой следует выполнить i-ю операцию.
Верните массив целых чисел answer, где answer[i] — количество островов после превращения ячейки (ri, ci) в сушу.
Остров окружен водой и образуется путем соединения соседних земель по горизонтали или вертикали. Вы можете считать, что все четыре края сетки окружены водой.

Пример:
Input: m = 1, n = 1, positions = [[0,0]]
Output: [1]

👨‍💻 Алгоритм:

1⃣Инициализация:
Создайте массивы x[] = { -1, 1, 0, 0 } и y[] = { 0, 0, -1, 1 }, которые будут использоваться для нахождения соседей ячейки.
Создайте экземпляр UnionFind, например, dsu(m * n). Инициализируйте всех родителей значением -1. Используйте объединение по рангу, инициализируйте все ранги значением 0. Наконец, инициализируйте count = 0.
Создайте список целых чисел answer, где answer[i] будет хранить количество островов, образованных после превращения ячейки positions[i] в сушу.

2⃣Обработка позиций:
Итерация по массиву positions. Для каждой позиции в positions:
Выполните линейное отображение, чтобы преобразовать двумерную позицию ячейки в landPosition = position[0] * n + position[1].
Используйте операцию addLand(landPosition), чтобы добавить landPosition как узел в граф. Эта функция также увеличит count.
Итерация по каждому соседу позиции. Соседа можно определить с помощью neighborX = position[0] + x[i] и neighborY = position[1] + y[i], где neighborX — координата X, а neighborY — координата Y соседней ячейки. Выполните линейное отображение соседней ячейки с помощью neighborPosition = neighborX * n + neighborY. Теперь, если на neighborPosition есть суша, т.е. isLand(neighborPosition) возвращает true, выполните объединение neighborPosition и landPosition. В объединении уменьшите count на 1.

3⃣Определение количества островов:
Выполните операцию numberOfIslands, которая возвращает количество островов, образованных после превращения позиции в сушу. Добавьте это значение в answer.
Верните answer.

😎 Решение
class UnionFind(size: Int) {
private val parent = IntArray(size) { -1 }
private val rank = IntArray(size)
var count = 0
fun addLand(x: Int) { if (parent[x] < 0) { parent[x] = x; count++ } }
fun isLand(x: Int) = parent[x] >= 0
fun numberOfIslands() = count
fun find(x: Int): Int { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x] }
fun unionSet(x: Int, y: Int) { val xset = find(x); val yset = find(y)
if (xset == yset) return; if (rank[xset] < rank[yset]) parent[xset] = yset
else { parent[yset] = xset; if (rank[xset] == rank[yset]) rank[xset]++ }; count-- }
}

class Solution {
fun numIslands2(m: Int, n: Int, positions: Array): List {
val dsu = UnionFind(m * n), dirs = listOf(-1, 1, 0, 0), dirc = listOf(0, 0, -1, 1)
val answer = mutableListOf()
for (pos in positions) {
val land = pos[0] * n + pos[1]
dsu.addLand(land)
for (i in 0..3) {
val x = pos[0] + dirs[i], y = pos[1] + dirc[i], neighbor = x * n + y
if (x in 0 until m && y in 0 until n && dsu.isLand(neighbor)) { dsu.unionSet(land, neighbor) }
}
answer.add(dsu.numberOfIslands())
}
return answer
}
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 651. 4 Keys Keyboard
Сложность: medium

Представьте, что у вас есть специальная клавиатура со следующими клавишами: A: Напечатать одну букву "A" на экране. Ctrl-A: Выделить весь экран. Ctrl-C: Скопировать выделение в буфер. Ctrl-V: Печать буфера на экране с добавлением его после того, что уже было напечатано. Учитывая целое число n, верните максимальное количество букв 'A', которые можно напечатать на экране при нажатии не более n клавиш.

Пример:
Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]

👨‍💻 Алгоритм:

1⃣Используйте динамическое программирование для отслеживания максимального количества букв 'A' на экране после каждого числа нажатий клавиш.

2⃣Итерируйтесь от 1 до n, вычисляя максимальное количество 'A' для каждой позиции, учитывая возможность вставки скопированного текста.

3⃣Возвращайте значение из таблицы динамического программирования для n нажатий клавиш.

😎 Решение:
fun maxA(n: Int): Int {
val dp = IntArray(n + 1)
for (i in 1..n) {
dp[i] = dp[i - 1] + 1
for (j in 2 until i) {
dp[i] = maxOf(dp[i], dp[j - 2] * (i - j + 1))
}
}
return dp[n]
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 336. Palindrome Pairs
Сложность: hard

Вам дан массив уникальных строк words, индексируемый с 0.

Пара палиндромов — это пара целых чисел (i, j), таких что:
0

Задача: 1503. Last Moment Before All Ants Fall Out of a Plank
Сложность: medium

У нас есть деревянная доска длиной n единиц. Некоторые муравьи ходят по доске, каждый муравей движется со скоростью 1 единица в секунду. Некоторые муравьи движутся влево, другие движутся вправо.

Когда два муравья, движущиеся в разных направлениях, встречаются в какой-то точке, они меняют свои направления и продолжают двигаться дальше. Предполагается, что изменение направлений не занимает дополнительного времени.

Когда муравей достигает одного из концов доски в момент времени t, он сразу же падает с доски.

Дано целое число n и два целых массива left и right, обозначающие позиции муравьев, движущихся влево и вправо соответственно. Верните момент, когда последний(е) муравей(и) падает(ют) с доски.

Пример:
Input: n = 4, left = [4,3], right = [0,1]
Output: 4
Explanation: In the image above:
-The ant at index 0 is named A and going to the right.
-The ant at index 1 is named B and going to the right.
-The ant at index 3 is named C and going to the left.
-The ant at index 4 is named D and going to the left.
The last moment when an ant was on the plank is t = 4 seconds. After that, it falls immediately out of the plank. (i.e., We can say that at t = 4.0000000001, there are no ants on the plank).

👨‍💻 Алгоритм:

1⃣Инициализируйте переменную ans значением 0.

2⃣Итерация по массиву left и обновление ans значением num, если оно больше текущего значения ans.

3⃣Итерация по массиву right и обновление ans значением n - num, если оно больше текущего значения ans. Верните значение ans.

😎 Решение:
class Solution {
fun getLastMoment(n: Int, left: IntArray, right: IntArray): Int {
var ans = 0
for (num in left) {
ans = maxOf(ans, num)
}
for (num in right) {
ans = maxOf(ans, n - num)
}
return ans
}
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 711. Number of Distinct Islands II
Сложность: hard

Вам дана двоичная матричная сетка m x n. Остров - это группа 1 (представляющая сушу), соединенных в четырех направлениях (горизонтальном или вертикальном). Можно предположить, что все четыре края сетки окружены водой. Остров считается одинаковым с другим, если они имеют одинаковую форму, или имеют одинаковую форму после поворота (только на 90, 180 или 270 градусов) или отражения (влево/вправо или вверх/вниз). Верните количество разных островов.

Пример:
Input: grid = [[1,1,0,0,0],[1,0,0,0,0],[0,0,0,0,1],[0,0,0,1,1]]
Output: 1

👨‍💻 Алгоритм:

1⃣Пройдите по каждому элементу матрицы, если найдена земля (1), выполните DFS для обнаружения всех связанных с этим островом земель и сохраните форму острова.

2⃣Нормализуйте форму острова, применив все возможные повороты и отражения, чтобы найти каноническую форму.

3⃣Используйте множество для хранения всех уникальных канонических форм и верните размер этого множества.

😎 Решение:
class Solution {
fun numDistinctIslands2(grid: Array): Int {
val uniqueIslands = mutableSetOf()

for (i in grid.indices) {
for (j in grid[0].indices) {
if (grid[i][j] == 1) {
val shape = mutableListOf()
dfs(grid, i, j, i, j, shape)
uniqueIslands.add(normalize(shape))
}
}
}

return uniqueIslands.size
}

private fun dfs(grid: Array, i: Int, j: Int, baseI: Int, baseJ: Int, shape: MutableList) {
if (i < 0 || i >= grid.size || j < 0 || j >= grid[0].size || grid[i][j] == 0) {
return
}
grid[i][j] = 0
shape.add(Pair(i - baseI, j - baseJ))
dfs(grid, i + 1, j, baseI, baseJ, shape)
dfs(grid, i - 1, j, baseI, baseJ, shape)
dfs(grid, i, j + 1, baseI, baseJ, shape)
dfs(grid, i, j - 1, baseI, baseJ, shape)
}

private fun normalize(shape: List): String {
val shapes = List(8) { mutableListOf() }
for ((x, y) in shape) {
shapes[0].add(Pair(x, y))
shapes[1].add(Pair(x, -y))
shapes[2].add(Pair(-x, y))
shapes[3].add(Pair(-x, -y))
shapes[4].add(Pair(y, x))
shapes[5].add(Pair(y, -x))
shapes[6].add(Pair(-y, x))
shapes[7].add(Pair(-y, -x))
}
for (s in shapes) {
s.sortWith(compareBy({ it.first }, { it.second }))
}
val minShape = shapes.minByOrNull { it.toString() }!!
return minShape.joinToString(";") { "${it.first},${it.second}" }
}
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 667. Beautiful Arrangement II
Сложность: medium

Даны два целых числа n и k, составьте список answer, содержащий n различных положительных чисел в диапазоне от 1 до n, который соответствует следующему требованию:

Предположим, что этот список answer = [a1, a2, a3, ... , an], тогда список [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] имеет ровно k различных чисел. Верните список answer. Если существует несколько допустимых ответов, верните любой из них.

Пример:
Input: n = 3, k = 1
Output: [1,2,3]
Explanation: The [1,2,3] has three different positive integers ranging from 1 to 3, and the [1,1] has exactly 1 distinct integer: 1

👨‍💻 Алгоритм:

1⃣Инициализация списка:
Начните с создания списка от 1 до n: [1, 2, 3, ..., n].

2⃣Конструирование шаблона с k различиями:
Для обеспечения k различных значений разностей используйте следующий подход:
Включайте числа попеременно с конца и начала списка, начиная с n и 1, чтобы создать как можно больше уникальных разностей.
Если требуется меньше k, оставшиеся числа просто добавляйте в порядке возрастания, чтобы не увеличивать количество уникальных разностей.

3⃣Заполнение списка:
Заполните оставшуюся часть списка последовательными числами, чтобы сохранить уникальные числа в диапазоне от 1 до n.

😎 Решение:
fun constructArray(n: Int, k: Int): IntArray {
val answer = mutableListOf()
var left = 1
var right = n

for (i in 0..k) {
if (i % 2 == 0) {
answer.add(left)
left++
} else {
answer.add(right)
right--
}
}

if (k % 2 == 0) {
for (i in left..right) answer.add(i)
} else {
for (i in right downTo left) answer.add(i)
}

return answer.toIntArray()
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 892. Surface Area of 3D Shapes
Сложность: easy

Вам дана сетка n x n, на которой вы разместили несколько кубиков 1 x 1 x 1. Каждое значение v = grid[i][j] представляет собой башню из v кубиков, размещенных на вершине ячейки (i, j). После размещения кубиков вы решили склеить все непосредственно прилегающие кубики друг с другом, образовав несколько неправильных 3D-фигур. Верните общую площадь поверхности получившихся фигур. Примечание: нижняя грань каждой фигуры учитывается в площади ее поверхности.

Пример:
Input: grid = [[1,2],[3,4]]
Output: 34

👨‍💻 Алгоритм:

1⃣Пройти по всей сетке и для каждой башни (ячейки) посчитать начальную площадь поверхности: добавить площадь верхней и нижней граней, а также четыре боковые грани.

2⃣Для каждой башни уменьшить площадь боковых граней, которые прилегают к соседним башням, с учетом высоты соседних башен.

3⃣Просуммировать все значения площадей для получения итоговой площади поверхности.

😎 Решение:
fun surfaceArea(grid: Array): Int {
val n = grid.size
var area = 0
for (i in 0 until n) {
for (j in 0 until n) {
if (grid[i][j] > 0) {
area += (grid[i][j] * 4) + 2
}
if (i > 0) {
area -= minOf(grid[i][j], grid[i-1][j]) * 2
}
if (j > 0) {
area -= minOf(grid[i][j], grid[i][j-1]) * 2
}
}
}
return area

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1208. Get Equal Substrings Within Budget
Сложность: medium

Вам даны две строки s и t одинаковой длины и целое число maxCost.
Вы хотите преобразовать s в t. Изменение i-го символа строки s на i-й символ строки t стоит |s[i] - t[i]| (т.е. абсолютная разница между значениями ASCII символов).

Верните максимальную длину подстроки s, которую можно изменить, чтобы она соответствовала соответствующей подстроке t с затратами, не превышающими maxCost. Если нет подстроки из s, которую можно изменить на соответствующую подстроку из t, верните 0.

Пример:
Input: s = "abcd", t = "bcdf", maxCost = 3
Output: 3
Explanation: "abc" of s can change to "bcd".
That costs 3, so the maximum length is 3.

👨‍💻 Алгоритм:

1⃣Инициализация переменных:
maxLen для хранения максимальной длины подстроки с затратами, не превышающими maxCost.
start для хранения начального индекса текущей подстроки.
currCost для хранения текущих затрат на преобразование подстроки s в t.

2⃣Итерация по индексам от 0 до N-1:
Добавить текущие затраты на преобразование символа s[i] в t[i] к currCost.
Удалять элементы с левого конца, уменьшая затраты до тех пор, пока currCost не станет меньше или равным maxCost.
Обновить maxLen длиной текущей подстроки.

3⃣Возврат maxLen как результата.

😎 Решение:
class Solution {
fun equalSubstring(s: String, t: String, maxCost: Int): Int {
val N = s.length

var maxLen = 0
var start = 0
var currCost = 0

for (i in 0 until N) {
currCost += kotlin.math.abs(s[i] - t[i])

while (currCost > maxCost) {
currCost -= kotlin.math.abs(s[start] - t[start])
start++
}

maxLen = maxOf(maxLen, i - start + 1)
}

return maxLen
}
}

Ставь 👍 и забирай 📚 Базу знаний