Kotlin | LeetCode

Задача: 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⃣Иначе, если s != goal, инициализируем firstIndex и secondIndex значениями -1 для хранения индексов символов в строке s, которые отличаются от символов в строке goal на тех же индексах. Итерируем по каждому индексу i в строке s: если символы s[i] и goal[i] разные, сохраняем текущий индекс. Если firstIndex == -1, обновляем firstIndex = i. Если firstIndex != -1, но secondIndex == -1, обновляем secondIndex = i. Если оба индекса уже обновлены, возвращаем false.

3⃣Если обновлен только firstIndex, возвращаем false. Иначе, все символы обеих строк одинаковы, кроме двух индексов. Поэтому s[firstIndex] должен быть равен goal[secondIndex], и s[secondIndex] должен быть равен goal[firstIndex], чтобы строки стали равны после обмена.

😎 Решение:

class Solution {
    fun buddyStrings(s: String, goal: String): Boolean {
        if (s.length != goal.length) return false
        if (s == goal) {
            val freq = IntArray(26)
            for (ch in s) {
                if (++freq[ch - 'a'] > 1) return true
            }
            return false
        }

        var firstIndex = -1
        var secondIndex = -1
        for (i in s.indices) {
            if (s[i] != goal[i]) {
                if (firstIndex == -1) firstIndex = i
                else if (secondIndex == -1) secondIndex = i
                else return false
            }
        }

        return secondIndex != -1 &&
               s[firstIndex] == goal[secondIndex] &&
               s[secondIndex] == goal[firstIndex]
    }
}

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

Задача: 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? = null
    var right: TreeNode? = null
}

class Solution {
    private fun dfs(node: TreeNode?, nodeSet: MutableSet<Int>) {
        if (node == null) return
        dfs(node.left, nodeSet)
        nodeSet.add(node.`val`)
        dfs(node.right, nodeSet)
    }

    fun twoSumBSTs(root1: TreeNode?, root2: TreeNode?, target: Int): Boolean {
        val nodeSet1 = mutableSetOf<Int>()
        val nodeSet2 = mutableSetOf<Int>()
        dfs(root1, nodeSet1)
        dfs(root2, nodeSet2)
        
        for (value1 in nodeSet1) {
            if (nodeSet2.contains(target - value1)) {
                return true
            }
        }
        
        return false
    }
}

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

Задача: 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 после добавления i не превысит значение target, то обновите значение currSum и рекурсивно перейдите к следующему кубику. Добавьте значение, возвращенное этим рекурсивным вызовом, к ways. Иначе, если это значение невозможно, то выйдите из цикла, так как большие значения также не удовлетворят вышеуказанному условию.

2⃣Базовые случаи:

Если мы перебрали все кубики, т.е. diceIndex = n, то проверьте, равна ли currSum значению target.

3⃣Верните значение ways и также сохраните его в таблице мемоизации memo, соответствующей текущему состоянию, определяемому diceIndex и currSum.

😎 Решение:

class Solution {
    val MOD = 1_000_000_007

    fun waysToTarget(memo: Array<IntArray>, diceIndex: Int, n: Int, currSum: Int, target: Int, k: Int): Int {
        if (diceIndex == n) {
            return if (currSum == target) 1 else 0
        }
        if (memo[diceIndex][currSum] != -1) {
            return memo[diceIndex][currSum]
        }

        var ways = 0
        for (i in 1..minOf(k, target - currSum)) {
            ways = (ways + waysToTarget(memo, diceIndex + 1, n, currSum + i, target, k)) % MOD
        }
        memo[diceIndex][currSum] = ways
        return ways
    }

    fun numRollsToTarget(n: Int, k: Int, target: Int): Int {
        val memo = Array(n + 1) { IntArray(target + 1) { -1 } }
        return waysToTarget(memo, 0, n, 0, target, k)
    }
}

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

Задача: 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, b = 5, c = 1
Output: [1,2]

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

1⃣Сортировка позиций:
Убедитесь, что позиции камней отсортированы в порядке возрастания. Обозначим отсортированные позиции как x, y и z.

2⃣Вычисление минимальных ходов:
Если камни уже находятся в последовательных позициях (то есть y - x == 1 и z - y == 1), минимальное количество ходов равно 0.
Если два камня находятся в соседних позициях, а третий камень на расстоянии более чем одна позиция, минимальное количество ходов равно 1.
В остальных случаях минимальное количество ходов равно 2.

3⃣Вычисление максимальных ходов:
Максимальное количество ходов равно сумме расстояний между соседними камнями минус 2, то есть (y - x - 1) + (z - y - 1).

😎 Решение:

class Solution {
    fun numMovesStones(a: Int, b: Int, c: Int): IntArray {
        val stones = listOf(a, b, c).sorted()
        val x = stones[0]
        val y = stones[1]
        val z = stones[2]
        val minMoves = if (y - x <= 2 || z - y <= 2) if (y - x == 1 && z - y == 1) 0 else 1 else 2
        val maxMoves = (y - x - 1) + (z - y - 1)
        return intArrayOf(minMoves, maxMoves)
    }
}

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

Задача: 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", the substring of s starting from indices[2] = 5 to the next '#' is underlined in "time#bell#"

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

1⃣Поскольку слово имеет не более 6 собственных суффиксов (так как words[i].length <= 7), давайте итерироваться по всем из них. Для каждого собственного суффикса мы попытаемся удалить его из нашего списка слов. Для эффективности сделаем words множеством.

2⃣Затем создадим список оставшихся слов и сформируем опорную строку, объединяя каждое слово с символом '#'.

3⃣В конце вернем длину полученной опорной строки.

😎 Решение:

class Solution {
    fun minimumLengthEncoding(words: Array<String>): Int {
        val good = words.toMutableSet()
        for (word in words) {
            for (k in 1 until word.length) {
                good.remove(word.substring(k))
            }
        }
        return good.sumOf { it.length + 1 }
    }

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

Задача: 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⃣Заменяем исходный массив полученным результатом, завершая процесс поворота массива.

😎 Решение:

class Solution {
    fun rotate(nums: IntArray, k: Int) {
        val n = nums.size
        val a = IntArray(n)
        for (i in nums.indices) {
            a[(i + k) % n] = nums[i]
        }
        for (i in nums.indices) {
            nums[i] = a[i]
        }
    }
}

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

Задача: 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.
Таким образом, один из правильных порядков курсов — [0,1,2,3]. Другой правильный порядок — [0,2,1,3].

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

1⃣Инициализация и построение графа:
Инициализируйте стек S, который будет содержать топологически отсортированный порядок курсов в нашем графе.
Постройте список смежности, используя пары ребер, указанные на входе. Важно отметить, что пара вида [a, b] указывает на то, что курс b должен быть пройден, чтобы взять курс a. Это подразумевает ребро вида b ➔ a. Учтите это при реализации алгоритма.

2⃣Запуск поиска в глубину (DFS):
Для каждого узла в нашем графе выполните поиск в глубину (DFS), если этот узел еще не был посещен во время DFS другого узла.
Предположим, что мы выполняем поиск в глубину для узла N. Рекурсивно обойдите всех соседей узла N, которые еще не были обработаны.

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

😎 Решение:

class Solution {
    companion object {
        const val WHITE = 1
        const val GRAY = 2
        const val BLACK = 3
    }

    private var isPossible: Boolean = true
    private lateinit var color: MutableMap<Int, Int>
    private val adjList: MutableMap<Int, MutableList<Int>> = HashMap()
    private val topologicalOrder: MutableList<Int> = ArrayList()

    private fun init(numCourses: Int) {
        isPossible = true
        color = HashMap()
        adjList.clear()
        topologicalOrder.clear()
        for (i in 0 until numCourses) {
            color[i] = WHITE
        }
    }

    private fun dfs(node: Int) {
        if (!isPossible) return
        color[node] = GRAY
        for (neighbor in adjList.getOrDefault(node, mutableListOf())) {
            when (color[neighbor]) {
                WHITE -> dfs(neighbor)
                GRAY -> isPossible = false
            }
        }
        color[node] = BLACK
        topologicalOrder.add(node)
    }

    fun findOrder(numCourses: Int, prerequisites: Array<IntArray>): IntArray {
        init(numCourses)
        for (prerequisite in prerequisites) {
            val (dest, src) = prerequisite
            adjList.computeIfAbsent(src) { mutableListOf() }.add(dest)
        }
        for (i in 0 until numCourses) {
            if (color[i] == WHITE) {
                dfs(i)
            }
        }
        return if (isPossible) {
            val order = IntArray(numCourses)
            for (i in 0 until numCourses) {
                order[i] = topologicalOrder[numCourses - i - 1]
            }
            order
        } else {
            intArrayOf()
        }
    }
}

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

Задача: 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⃣Сравнение двух случаев:
Рассмотрите оба случая: подмассив длины firstLen до подмассива длины secondLen и подмассив длины secondLen до подмассива длины firstLen. Найдите максимальную сумму для каждого случая.

😎 Решение:

class Solution {
    fun maxSumTwoNoOverlap(nums: IntArray, firstLen: Int, secondLen: Int): Int {
        fun maxSumNonOverlap(nums: IntArray, firstLen: Int, secondLen: Int): Int {
            val n = nums.size
            val prefix = IntArray(n + 1)
            for (i in 0 until n) {
                prefix[i + 1] = prefix[i] + nums[i]
            }
            
            val maxFirst = IntArray(n)
            for (i in firstLen - 1 until n) {
                maxFirst[i] = maxOf(if (i > 0) maxFirst[i - 1] else 0, prefix[i + 1] - prefix[i + 1 - firstLen])
            }
            
            val maxSecond = IntArray(n)
            for (i in secondLen - 1 until n) {
                maxSecond[i] = maxOf(if (i > 0) maxSecond[i - 1] else 0, prefix[i + 1] - prefix[i + 1 - secondLen])
            }
            
            var maxSum = 0
            for (i in firstLen + secondLen - 1 until n) {
                maxSum = maxOf(maxSum, maxFirst[i - secondLen] + (prefix[i + 1] - prefix[i + 1 - secondLen]))
            }
            
            return maxSum
        }
        
        return maxOf(maxSumNonOverlap(nums, firstLen, secondLen), maxSumNonOverlap(nums.reversedArray(), secondLen, firstLen))
    }
}

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

Задача: 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⃣Поиск корневого узла и проверка на единственное дерево:
Найдите корневой узел (узел с нулевым количеством родителей). Если корневых узлов нет или больше одного, верните false. Используйте BFS или DFS, чтобы проверить, что все узлы достижимы от корня и что нет циклов.

3⃣Проверка на достижение всех узлов:
Проверьте, что количество посещенных узлов равно n. Если нет, верните false. В противном случае, верните true.
😎 Решение:

class Solution {
    fun validateBinaryTreeNodes(n: Int, leftChild: IntArray, rightChild: IntArray): Boolean {
        val parents = IntArray(n)
        
        for (i in 0 until n) {
            if (leftChild[i] != -1) {
                parents[leftChild[i]]++
                if (parents[leftChild[i]] > 1) {
                    return false
                }
            }
            if (rightChild[i] != -1) {
                parents[rightChild[i]]++
                if (parents[rightChild[i]] > 1) {
                    return false
                }
            }
        }
        
        var root = -1
        for (i in 0 until n) {
            if (parents[i] == 0) {
                if (root == -1) {
                    root = i
                } else {
                    return false
                }
            }
        }
        
        if (root == -1) {
            return false
        }
        
        val visited = mutableSetOf<Int>()
        val queue = ArrayDeque<Int>()
        queue.add(root)
        
        while (queue.isNotEmpty()) {
            val node = queue.removeFirst()
            if (visited.contains(node)) {
                return false
            }
            visited.add(node)
            if (leftChild[node] != -1) {
                queue.add(leftChild[node])
            }
            if (rightChild[node] != -1) {
                queue.add(rightChild[node])
            }
        }
        
        return visited.size == n
    }
}

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

Задача: 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⃣Создайте маппинг для чисел, входящих в черный список, чтобы сопоставить их с числами из диапазона [n - len(blacklist), n - 1], которые не входят в черный список.

2⃣Создайте массив для хранения возможных чисел для выбора, исключая числа из черного списка.

3⃣При каждом вызове функции pick() используйте встроенную функцию random для выбора случайного индекса из массива возможных чисел и возвращайте соответствующее значение.

😎 Решение:

import kotlin.random.Random

class Solution(n: Int, blacklist: IntArray) {
    private val map = mutableMapOf<Int, Int>()
    private val bound = n - blacklist.size

    init {
        val blackset = blacklist.toSet()
        var whitelist = bound
        for (b in blacklist) {
            if (b < bound) {
                while (blackset.contains(whitelist)) {
                    whitelist++
                }
                map[b] = whitelist
                whitelist++
            }
        }
    }

    fun pick(): Int {
        val r = Random.nextInt(bound)
        return map.getOrDefault(r, r)
    }
}

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

Задача: 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]) % MOD.

3⃣Возвращение результата
Верните значение dp[n], которое будет количеством отклонений для n элементов, по модулю 10^9 + 7.

😎 Решение:

class Solution {
    fun countDerangements(n: Int): Int {
        val MOD = 1_000_000_007
        if (n == 0) return 1
        if (n == 1) return 0
        val dp = IntArray(n + 1)
        dp[0] = 1
        dp[1] = 0
        for (i in 2..n) {
            dp[i] = ((i - 1) * (dp[i - 1] + dp[i - 2].toLong()) % MOD).toInt()
        }
        return dp[n]
    }
}

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

Задача: 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⃣Обновление максимальной длины
На каждом шаге проверяйте и обновляйте максимальную длину подстроки, если текущее окно содержит не более k различных символов. В конце верните максимальную длину подстроки.

😎 Решение:

class Solution {
    fun lengthOfLongestSubstringKDistinct(s: String, k: Int): Int {
        var left = 0
        var right = 0
        val charCount = mutableMapOf<Char, Int>()
        var maxLength = 0
        
        while (right < s.length) {
            charCount[s[right]] = charCount.getOrDefault(s[right], 0) + 1
            while (charCount.size > k) {
                charCount[s[left]] = charCount[s[left]]!! - 1
                if (charCount[s[left]] == 0) {
                    charCount.remove(s[left])
                }
                left++
            }
            maxLength = maxOf(maxLength, right - left + 1)
            right++
        }
        
        return maxLength
    }
}

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

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

3⃣Верните ans.

😎 Решение:

class Solution {
    fun numIdenticalPairs(nums: IntArray): Int {
        var ans = 0
        for (i in nums.indices) {
            for (j in i + 1 until nums.size) {
                if (nums[i] == nums[j]) {
                    ans++
                }
            }
        }
        return ans
    }
}

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

Задача: 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⃣Обработка каждой ячейки:
Для каждой ячейки исходной матрицы найдите всех её соседей (включая саму ячейку).
Вычислите среднее значение этих ячеек и сохраните его в соответствующей ячейке результирующей матрицы.

3⃣Возврат результата:
Верните результирующую матрицу после применения сглаживания ко всем ячейкам.

😎 Решение:

class Solution {
    fun imageSmoother(img: Array<IntArray>): Array<IntArray> {
        val m = img.size
        val n = img[0].size
        val result = Array(m) { IntArray(n) }
        
        for (i in 0 until m) {
            for (j in 0 until n) {
                var count = 0
                var total = 0
                for (ni in maxOf(0, i - 1)..minOf(m - 1, i + 1)) {
                    for (nj in maxOf(0, j - 1)..minOf(n - 1, j + 1)) {
                        total += img[ni][nj]
                        count += 1
                    }
                }
                result[i][j] = total / count
            }
        }
        
        return result
    }
}

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

Задача: 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 самых частых элементов.

😎 Решение:

class Solution {
    fun topKFrequent(nums: IntArray, k: Int): List<Int> {
        val count = nums.groupingBy { it }.eachCount()
        return count.entries.sortedByDescending { it.value }.take(k).map { it.key }
    }
}

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

Задача: 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<String>): Int {
    val uniqueForms = mutableSetOf<String>()
    
    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<Int>()
        var current = head
        while (current != null) {
            values.add(current.`val`)
            current = current.next
        }
        
        val answer = IntArray(values.size)
        val stack = mutableListOf<Int>()
        
        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 + 1]) {
        i--
    }
    if (i == -1) return arr
    
    var j = n - 1
    while (arr[j] >= 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 <= y. Результат разбивания таков: если x == y, оба камня уничтожаются, а если x != y, камень веса x уничтожается, а камень веса y приобретает новый вес y - x. В конце игры остается не более одного камня. Верните наименьший возможный вес оставшегося камня. Если камней не осталось, верните 0.

Пример:

Input: stones = [2,7,4,1,8,1]
Output: 1

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

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

2⃣Определи, какие веса можно достичь, используя половину суммы всех камней.

3⃣Найди наибольшую достижимую сумму, которая меньше или равна половине общей суммы, и верни разницу между общей суммой и удвоенной этой суммой.Верни максимальную длину среди всех цепочек.

😎 Решение:

fun lastStoneWeightII(stones: IntArray): Int {
    val totalSum = stones.sum()
    val halfSum = totalSum / 2
    val dp = IntArray(halfSum + 1)

    for (stone in stones) {
        for (j in halfSum downTo stone) {
            dp[j] = maxOf(dp[j], dp[j - stone] + stone)
        }
    }

    return totalSum - 2 * dp[halfSum]
}

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