Kotlin | LeetCode

Задача: 996. Number of Squareful Arrays Сложность: hard Массив является квадратным, если сумма каждой пары соседних элементов является совершенным квадратом. Если задан целочисленный массив nums, верните количество перестановок nums, которые являются квадратными. Две перестановки perm1 и perm2 различны, если существует некоторый индекс i такой, что perm1[i] != perm2[i]. Пример:

    
        Input: nums = [1,17,8]
Output: 2{}
    

👨‍💻 Алгоритм: 1⃣Генерация перестановок: Сгенерируйте все возможные перестановки массива nums. Для каждой перестановки проверьте, является ли она квадратной. 2⃣Проверка квадратности: Для каждой перестановки проверьте, является ли сумма каждой пары соседних элементов совершенным квадратом. Для этого используйте функцию для проверки, является ли число совершенным квадратом. 3⃣Подсчет квадратных перестановок: Подсчитайте количество перестановок, которые являются квадратными, и верните это значение. 😎 Решение:

    
        class Solution {
    fun numSquarefulPerms(nums: IntArray): Int {
        nums.sort()
        val used = BooleanArray(nums.size)
        val result = mutableSetOf<List<Int>>()
        val path = mutableListOf<Int>()
        backtrack(nums, used, path, result)
        return result.size
    }
    
    private fun backtrack(nums: IntArray, used: BooleanArray, path: MutableList<Int>, result: MutableSet<List<Int>>) {
        if (path.size == nums.size) {
            if (isSquareful(path)) {
                result.add(path.toList())
            }
            return
        }
        
        for (i in nums.indices) {
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) continue
            path.add(nums[i])
            used[i] = true
            backtrack(nums, used, path, result)
            path.removeAt(path.size - 1)
            used[i] = false
        }
    }
    
    private fun isSquareful(perm: List<Int>): Boolean {
        for (i in 0 until perm.size - 1) {
            val sum = perm[i] + perm[i + 1]
            val root = kotlin.math.sqrt(sum.toDouble()).toInt()
            if (root * root != sum) return false
        }
        return true
    }
}{}
    

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

Задача: 1051. Height Checker Сложность: easy Школа пытается сделать ежегодную фотографию всех учеников. Учеников просят встать в одну шеренгу в неубывающем порядке по росту. Пусть этот порядок представлен целочисленным массивом expected, где expected[i] - ожидаемый рост i-го студента в очереди. Вам дан целочисленный массив heights, представляющий текущий порядок, в котором стоят студенты. Каждый heights[i] - это высота i-го студента в очереди (с индексом 0). Верните количество индексов, в которых heights[i] != expected[i]. Пример:

    
        Input: heights = [1,1,4,2,1,3]
Output: 3{}
    

👨‍💻 Алгоритм: 1⃣Создай отсортированную копию массива heights, чтобы получить ожидаемый порядок высот. 2⃣Пройди по обоим массивам и сравни элементы. 3⃣Подсчитай количество индексов, где элементы двух массивов не равны 😎 Решение:

    
        fun heightChecker(heights: IntArray): Int {
    val expected = heights.sortedArray()
    var count = 0
    for (i in heights.indices) {
        if (heights[i] != expected[i]) {
            count++
        }
    }
    return count
}{}
    

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

Задача: 420. Strong Password Checker Сложность: hard Пароль считается надежным, если выполняются следующие условия: в нем не менее 6 и не более 20 символов. он содержит не менее одной строчной буквы, не менее одной заглавной буквы и не менее одной цифры. он не содержит трех повторяющихся символов подряд (например, "Baaabb0" - слабый, а "Baaba0" - сильный). Учитывая строку пароля, верните минимальное количество шагов, необходимых для того, чтобы сделать пароль сильным. Если пароль уже сильный, верните 0. За один шаг можно: вставить один символ в пароль, удалить один символ из пароля или заменить один символ пароля другим символом. Пример:

    
        Input: password = "a"
Output: 5{}
    

👨‍💻 Алгоритм: 1⃣Определите количество недостающих символов до минимума и превышающих символов для ограничения длины пароля. Также определите наличие строчных, заглавных букв и цифр. 2⃣Вычислите количество необходимых замен для устранения трех повторяющихся символов подряд. 3⃣Определите минимальное количество шагов для приведения пароля к требуемым условиям, используя вычисленные значения недостающих символов, превышающих символов и замен. 😎 Решение:

    
        fun strongPasswordChecker(s: String): Int {
    val n = s.length
    var hasLower = false
    var hasUpper = false
    var hasDigit = false
    var repeatCount = 0
    var i = 0
    
    while (i < n) {
        if (s[i].isLowerCase()) hasLower = true
        if (s[i].isUpperCase()) hasUpper = true
        if (s[i].isDigit()) hasDigit = true
        
        val start = i
        while (i < n && s[i] == s[start]) {
            i++
        }
        
        repeatCount += (i - start) / 3
    }
    
    val missingTypes = (if (hasLower) 0 else 1) + (if (hasUpper) 0 else 1) + (if (hasDigit) 0 else 1)
    
    return when {
        n < 6 -> maxOf(missingTypes, 6 - n)
        n <= 20 -> maxOf(missingTypes, repeatCount)
        else -> {
            val excessChars = n - 20
            var overLenReduction = 0
            i = 2
            while (i < n && excessChars > 0) {
                if (i % 3 == 2 && s[i] == s[i - 1] && s[i] == s[i - 2]) {
                    overLenReduction++
                    excessChars--
                }
                i++
            }
            repeatCount -= overLenReduction
            (n - 20) + maxOf(missingTypes, repeatCount)
        }
    }
}{}
    

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

Задача: 734. Sentence Similarity Сложность: easy Мы можем представить предложение в виде массива слов, например, предложение "I am happy with leetcode" можно представить как arr = ["I", "am",happy", "with", "leetcode"]. Даны два предложения sentence1 и sentence2, каждое из которых представлено в виде массива строк, и массив пар строк similarPairs, где similarPairs[i] = [xi, yi] указывает, что два слова xi и yi похожи. Возвращается true, если предложения sentence1 и sentence2 похожи, или false, если они не похожи. Два предложения похожи, если: у них одинаковая длина (т.е, Заметьте, что слово всегда похоже само на себя, также обратите внимание, что отношение сходства не является транзитивным. Например, если слова a и b похожи, а слова b и c похожи, то a и c не обязательно похожи. Пример:

    
        Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","fine"],["drama","acting"],["skills","talent"]]
Output: true{}
    

👨‍💻 Алгоритм: 1⃣Проверьте, равны ли длины предложений sentence1 и sentence2. Если нет, верните false. 2⃣Создайте словарь для хранения всех пар похожих слов. 3⃣Проверьте каждую пару слов из предложений sentence1 и sentence2 на схожесть, используя словарь и правило, что слово всегда похоже на само себя. 😎 Решение:

    
        fun areSentencesSimilar(sentence1: Array<String>, sentence2: Array<String>, similarPairs: List<List<String>>): Boolean {
    if (sentence1.size != sentence2.size) {
        return false
    }
    
    val similar = mutableMapOf<String, MutableSet<String>>()
    for (pair in similarPairs) {
        val (x, y) = pair
        similar.computeIfAbsent(x) { mutableSetOf() }.add(y)
        similar.computeIfAbsent(y) { mutableSetOf() }.add(x)
    }
    
    for (i in sentence1.indices) {
        val w1 = sentence1[i]
        val w2 = sentence2[i]
        if (w1 != w2 && (similar[w1]?.contains(w2) != true)) {
            return false
        }
    }
    
    return true
}{}
    

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

Задача: 1023. Camelcase Matching Сложность: medium Учитывая массив строк queries и строку pattern, верните булевский массив answer, где answer[i] - true, если queries[i] соответствует pattern, и false в противном случае. Слово запроса queries[i] соответствует pattern, если вы можете вставить строчные английские буквы pattern так, чтобы они были равны запросу. Вы можете вставить каждый символ в любую позицию и не можете вставить ни одного символа. Пример:

    
        Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB"
Output: [true,false,true,true,false]{}
    

👨‍💻 Алгоритм: 1⃣Инициализация переменных: Создайте массив answer для хранения результатов соответствия каждого запроса шаблону. 2⃣Проверка каждого запроса: Для каждого запроса из queries, проверьте, можно ли вставить строчные буквы в pattern, чтобы они соответствовали запросу. Используйте два указателя, один для query и один для pattern. Перемещайте оба указателя, пока они не достигнут конца строк. Если текущие символы совпадают, переместите оба указателя. Если символы не совпадают и текущий символ в запросе является строчной буквой, переместите только указатель запроса. 3⃣Возврат результата: Если указатель шаблона достиг конца строки, добавьте true в answer, иначе добавьте false. Верните массив answer. 😎 Решение:

    
        class Solution {
    fun camelMatch(queries: Array<String>, pattern: String): BooleanArray {
        fun matches(query: String, pattern: String): Boolean {
            var i = 0
            var j = 0
            
            while (i < query.length) {
                if (j < pattern.length && query[i] == pattern[j]) {
                    j++
                } else if (query[i].isUpperCase()) {
                    return false
                }
                i++
            }
            return j == pattern.length
        }
        
        return queries.map { matches(it, pattern) }.toBooleanArray()
    }
}{}
    

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

Задача: 752. Open the Lock Сложность: medium Перед вами замок с 4 круглыми колесами. Каждое колесо имеет 10 слотов: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. Колеса могут свободно вращаться и оборачиваться: например, мы можем повернуть "9" так, чтобы получился "0", или "0" так, чтобы получился "9". Каждый ход состоит из поворота одного колеса на один слот. Изначально замок начинается с '0000', строки, представляющей состояние 4 колес. Вам дан список тупиков, то есть если замок отобразит любой из этих кодов, колеса замка перестанут вращаться, и вы не сможете его открыть. Учитывая цель, представляющую значение колес, которое позволит отпереть замок, верните минимальное общее количество оборотов, необходимое для открытия замка, или -1, если это невозможно. Пример:

    
        Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6{}
    

👨‍💻 Алгоритм: 1⃣Используйте алгоритм BFS для поиска кратчайшего пути от начального состояния '0000' до целевого состояния, избегая тупиков. Инициализируйте очередь с начальным состоянием '0000' и начальным шагом 0. Используйте множество для отслеживания посещенных состояний, чтобы избежать повторного посещения одного и того же состояния. 2⃣Для каждого состояния в очереди: Проверьте все возможные переходы на следующий шаг, вращая каждое колесо на +1 и -1. Если найденное состояние является целевым, верните количество шагов. Если найденное состояние не является тупиком и не было посещено ранее, добавьте его в очередь и отметьте как посещенное. 3⃣Если очередь пуста и целевое состояние не найдено, верните -1. 😎 Решение:

    
        fun openLock(deadends: Array<String>, target: String): Int {
    fun neighbors(node: String): List<String> {
        val res = mutableListOf<String>()
        val nodeArray = node.toCharArray()
        for (i in 0 until 4) {
            val x = nodeArray[i].toString().toInt()
            for (d in listOf(-1, 1)) {
                val y = (x + d + 10) % 10
                nodeArray[i] = y.toString().toCharArray()[0]
                res.add(String(nodeArray))
            }
            nodeArray[i] = x.toString().toCharArray()[0]
        }
        return res
    }

    val dead = deadends.toSet()
    val queue = ArrayDeque<Pair<String, Int>>()
    queue.add("0000" to 0)
    val visited = mutableSetOf("0000")

    while (queue.isNotEmpty()) {
        val (node, steps) = queue.removeFirst()
        if (node == target) return steps
        if (node in dead) continue
        for (neighbor in neighbors(node)) {
            if (neighbor !in visited) {
                visited.add(neighbor)
                queue.add(neighbor to steps + 1)
            }
        }
    }

    return -1
}{}
    

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

Задача: 921. Minimum Add to Make Parentheses Valid Сложность: medium Строка со скобками допустима тогда и только тогда, когда: это пустая строка, ее можно записать как AB (A, совмещенное с B), где A и B - допустимые строки, или ее можно записать как (A), где A - допустимая строка. Вам дана строка s со скобками. За один ход вы можете вставить скобку в любую позицию строки. Например, если s = "()))", вы можете вставить открывающую скобку в виде "(()))" или закрывающую скобку в виде "())))". Верните минимальное количество ходов, необходимое для того, чтобы сделать s допустимой. Пример:

    
        Input: n = 3, goal = 3, k = 1
Output: 6{}
    

👨‍💻 Алгоритм: 1⃣Инициализировать два счетчика open_needed и close_needed. 2⃣Пройти по строке s символ за символом: Если текущий символ - открывающая скобка (, увеличьте open_needed. Если текущий символ - закрывающая скобка ), проверьте: Если open_needed больше 0, уменьшите open_needed. Иначе увеличьте close_needed. 3⃣Суммируйте значения open_needed и close_needed, чтобы получить минимальное количество вставок. 😎 Решение:

    
        class Solution {
    fun minAddToMakeValid(s: String): Int {
        var openNeeded = 0
        var closeNeeded = 0
        
        for (char in s) {
            if (char == '(') {
                openNeeded++
            } else if (char == ')') {
                if (openNeeded > 0) {
                    openNeeded--
                } else {
                    closeNeeded++
                }
            }
        }
        
        return openNeeded + closeNeeded
    }
}{}
    

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

Задача: 1335. Minimum Difficulty of a Job Schedule Сложность: hard Вы хотите составить расписание списка заданий на d дней. Задания зависят друг от друга (т.е. чтобы выполнить задание i, вы должны закончить все задания j, где 0 <= j < i). Вы должны выполнять как минимум одно задание каждый день. Сложность расписания заданий — это сумма сложностей каждого дня из d дней. Сложность дня — это максимальная сложность задания, выполненного в этот день. Вам дан массив целых чисел jobDifficulty и целое число d. Сложность i-го задания равна jobDifficulty[i]. Верните минимальную сложность расписания заданий. Если вы не можете найти расписание для заданий, верните -1. Пример:

    
        Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7
Explanation: First day you can finish the first 5 jobs, total difficulty = 6.
Second day you can finish the last job, total difficulty = 1.
The difficulty of the schedule = 6 + 1 = 7 {}
    

👨‍💻 Алгоритм: 1⃣Определение состояния: Индекс i (индекс первой задачи на сегодняшний день в массиве jobDifficulty) и день d (количество оставшихся дней) будут определять состояние динамического программирования. min_diff(i, d) обозначает минимальную сложность при начале с i-й задачи с оставшимися d днями. min_diff(0, d) будет окончательным ответом, так как он представляет начало с начала массива задач и завершение всех задач за ровно d дней. 2⃣Функция перехода состояния: Задача с индексом j будет первой задачей на следующий день, следовательно, задачи, которые должны быть завершены сегодня, это все задачи с индексами между i и j, то есть jobDifficulty[i ]. Поскольку сложность дня — это максимальная сложность выполненной в этот день задачи, к сумме сложностей задач будет добавляться максимум из jobDifficulty[i ]. Формулируем функцию перехода состояния следующим образом: min_diff(i, d) = min_diff(j, d - 1) + max(jobDifficulty[i ]) для всех j > i. 3⃣Базовый случай: Когда остается только 1 день, необходимо завершить все незавершенные задачи в этот день и увеличить сложность расписания задач на максимальную сложность этих задач. 😎 Решение:

    
        class Solution {
    fun minDifficulty(jobDifficulty: IntArray, d: Int): Int {
        val n = jobDifficulty.size
        if (n < d) return -1
        
        val mem = Array(n) { IntArray(d + 1) { -1 } }
        
        fun minDiff(i: Int, daysRemaining: Int): Int {
            if (mem[i][daysRemaining] != -1) {
                return mem[i][daysRemaining]
            }
            
            if (daysRemaining == 1) {
                return jobDifficulty.sliceArray(i until n).maxOrNull()!!
            }
            
            var res = Int.MAX_VALUE
            var dailyMaxJobDiff = 0
            
            for (j in i until n - daysRemaining + 1) {
                dailyMaxJobDiff = maxOf(dailyMaxJobDiff, jobDifficulty[j])
                res = minOf(res, dailyMaxJobDiff + minDiff(j + 1, daysRemaining - 1))
            }
            
            mem[i][daysRemaining] = res
            return res
        }
        
        return minDiff(0, d)
    }
}{}
    

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

Задача: 1230. Toss Strange Coins Сложность: medium У вас есть несколько монет. Вероятность выпадения орла для i-й монеты равна prob[i]. Верните вероятность того, что количество монет, на которых выпал орел, равно target, если вы подбросите каждую монету ровно один раз. Пример:

    
        Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0
Output: 0.03125{}
    

👨‍💻 Алгоритм: 1⃣Инициализация: Создайте переменную n и инициализируйте её размером массива prob. Создайте 2D массив dp размером n + 1 строк и target + 1 столбцов, где dp[i][j] хранит вероятность получить j орлов, используя первые i монет. Установите базовый случай dp[0][0] = 1. 2⃣Итерация: Используйте два вложенных цикла для заполнения массива dp. Внешний цикл итерируется от i = 1 до n. Для каждого i установите dp[i][0], что обозначает вероятность получить 0 орлов при использовании i монет: dp[i][0] = dp[i - 1][0] * (1 - prob[i - 1]). Внутренний цикл итерируется от j = 1 до target. Для каждого j вычислите dp[i][j] по формуле: dp[i][j] = dp[i - 1][j - 1] * prob[i - 1] + dp[i - 1][j] * (1 - prob[i - 1]). 3⃣Возврат результата: Верните значение dp[n][target], которое содержит искомую вероятность. 😎 Решение:

    
        class Solution {
    fun probabilityOfHeads(prob: DoubleArray, target: Int): Double {
        val n = prob.size
        val dp = Array(n + 1) { DoubleArray(target + 1) }
        dp[0][0] = 1.0

        for (i in 1..n) {
            dp[i][0] = dp[i - 1][0] * (1 - prob[i - 1])
            for (j in 1..target) {
                if (j <= i) {
                    dp[i][j] = dp[i - 1][j - 1] * prob[i - 1] + dp[i - 1][j] * (1 - prob[i - 1])
                }
            }
        }

        return dp[n][target]
    }
}{}
    

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

Задача: 939. Minimum Area Rectangle Сложность: medium Дан массив точек в плоскости X-Y points, где points[i] = [xi, yi]. Верните минимальную площадь прямоугольника, образованного из этих точек, со сторонами, параллельными осям X и Y. Если такого прямоугольника не существует, верните 0. Пример:

    
        Input: points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output: 4{}
    

👨‍💻 Алгоритм: 1⃣Создать множество для хранения всех точек. Инициализировать переменную для хранения минимальной площади прямоугольника с бесконечным значением. 2⃣Пройти через все пары точек: Если две точки могут образовать диагональ прямоугольника, то проверить, существуют ли оставшиеся две точки для замкнутого прямоугольника. Если да, вычислить площадь прямоугольника и обновить минимальную площадь. 3⃣Если минимальная площадь остается бесконечной, вернуть 0. Иначе вернуть минимальную площадь. 😎 Решение:

    
        class Solution {
    fun minAreaRect(points: Array<IntArray>): Int {
        val pointSet = mutableSetOf<String>()
        for (point in points) {
            pointSet.add("${point[0]},${point[1]}")
        }
        
        var minArea = Int.MAX_VALUE
        for (i in points.indices) {
            for (j in i + 1 until points.size) {
                val (x1, y1) = points[i]
                val (x2, y2) = points[j]
                if (x1 != x2 && y1 != y2 && "${x1},${y2}" in pointSet && "${x2},${y1}" in pointSet) {
                    minArea = minArea.coerceAtMost(Math.abs(x2 - x1) * Math.abs(y2 - y1))
                }
            }
        }
        
        return if (minArea == Int.MAX_VALUE) 0 else minArea
    }
}{}
    

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