Kotlin | LeetCode

Задача: 1342. Number of Steps to Reduce a Number to Zero Сложность: easy Дано целое число num, вернуть количество шагов, необходимых для его сокращения до нуля. На каждом шаге, если текущее число четное, его нужно разделить на 2, в противном случае, вы должны вычесть из него 1. Пример:

Input: num = 14
Output: 6
Explanation: 
Step 1) 14 is even; divide by 2 and obtain 7. 
Step 2) 7 is odd; subtract 1 and obtain 6.
Step 3) 6 is even; divide by 2 and obtain 3. 
Step 4) 3 is odd; subtract 1 and obtain 2. 
Step 5) 2 is even; divide by 2 and obtain 1. 
Step 6) 1 is odd; subtract 1 and obtain 0.

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

fun numberOfSteps(num: Int): Int {
    var num = num
    var steps = 0
    while (num != 0) {
        if (num % 2 == 0) {
            num /= 2
        } else {
            num -= 1
        }
        steps++
    }
    return steps
}

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

Задача: 383. Ransom Note Сложность: easy Даны две строки ransomNote и magazine, верните true, если ransomNote можно составить, используя буквы из magazine, и false в противном случае. Каждая буква из magazine может быть использована в ransomNote только один раз. Пример:

Input: ransomNote = "a", magazine = "b"
Output: false

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

fun canConstruct(ransomNote: String, magazine: String): Boolean {
    var magazine = magazine.toMutableList()
    
    for (char in ransomNote) {
        val index = magazine.indexOf(char)
        if (index == -1) {
            return false
        }
        magazine.removeAt(index)
    }
    return true
}

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

Задача: 1315. Sum of Nodes with Even-Valued Grandparent Сложность: medium Given the root of a binary tree, return the sum of values of nodes with an even-valued grandparent. If there are no nodes with an even-valued grandparent, return 0. A grandparent of a node is the parent of its parent if it exists. Пример:

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.

👨‍💻 Алгоритм: 1⃣Определите метод solve(), который принимает TreeNode root, значение родителя parent и значение бабушки или дедушки gParent. Этот метод возвращает сумму значений узлов с четным значением бабушки и дедушки в поддереве узла root. Если root равен null, верните 0 как сумму. 2⃣Рекурсивно пройдите по левому и правому дочерним узлам, передавая в качестве значения parent root, а в качестве значения gParent parent. Если значение gParent четное, добавьте значение root к ответу. 3⃣Вызовите рекурсивную функцию solve() с корневым узлом и значениями -1 для parent и gParent. Верните сумму для левого и правого дочерних узлов и значение для текущего узла. 😎 Решение:

class Solution {
    private fun solve(root: TreeNode?, parent: Int, gParent: Int): Int {
        if (root == null) {
            return 0
        }
        return solve(root.left, root.`val`, parent) + solve(root.right, root.`val`, parent) + if (gParent % 2 == 0) root.`val` else 0
    }

    fun sumEvenGrandparent(root: TreeNode?): Int {
        return solve(root, -1, -1)
    }
}

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

Задача: 1338. Reduce Array Size to The Half Сложность: medium Дан массив целых чисел arr. Вы можете выбрать набор чисел и удалить все вхождения этих чисел из массива. Верните минимальный размер набора, чтобы было удалено не менее половины целых чисел из массива. Пример:

Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2
Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
Possible sets of size 2 are {3,5},{3,2},{5,2}.
Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has a size greater than half of the size of the old array.

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

class Solution {
    fun minSetSize(arr: IntArray): Int {
        arr.sort()
        
        val counts = mutableListOf<Int>()
        var currentRun = 1
        for (i in 1 until arr.size) {
            if (arr[i] == arr[i - 1]) {
                currentRun += 1
                continue
            }
            counts.add(currentRun)
            currentRun = 1
        }
        counts.add(currentRun)
        
        counts.sortDescending()
        
        var numbersRemovedFromArr = 0
        var setSize = 0
        for (count in counts) {
            numbersRemovedFromArr += count
            setSize += 1   
            if (numbersRemovedFromArr >= arr.size / 2) {
                break
            }
        }
        
        return setSize
    }
}

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

Задача: 819. Most Common Word Сложность: easy Дана строка paragraph и массив строк banned, представляющий запрещенные слова. Верните наиболее часто встречающееся слово, которое не запрещено. Гарантируется, что существует хотя бы одно слово, которое не запрещено, и что ответ является уникальным. Слова в paragraph нечувствительны к регистру, и ответ должен быть возвращен в нижнем регистре. Пример:

Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"]
Output: "ball"
Explanation: 
"hit" occurs 3 times, but it is a banned word.
"ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. 
Note that words in the paragraph are not case sensitive,
that punctuation is ignored (even if adjacent to words, such as "ball,"), 
and that "hit" isn't the answer even though it occurs more because it is banned.

👨‍💻 Алгоритм: 1⃣Заменяем всю пунктуацию пробелами и одновременно переводим каждую букву в нижний регистр. Это можно сделать и в два этапа, но здесь мы объединяем их в один этап. 2⃣Разбиваем полученный результат на слова, используя пробелы в качестве разделителей. 3⃣Затем итерируемся по словам, чтобы подсчитать количество появлений каждого уникального слова, исключая слова из списка запрещенных. С помощью хеш-таблицы {слово->количество} проходим по всем элементам, чтобы найти слово с наивысшей частотой. 😎 Решение:

class Solution {
    fun mostCommonWord(paragraph: String, banned: List<String>): String {
        val normalizedStr = paragraph.map { if (it.isLetterOrDigit()) it.lowercaseChar() else ' ' }.joinToString("")
        val words = normalizedStr.split("\\s+".toRegex()).filter { it.isNotEmpty() }
        val wordCount = mutableMapOf<String, Int>()
        val bannedWords = banned.toSet()

        for (word in words) {
            if (word !in bannedWords) {
                wordCount[word] = wordCount.getOrDefault(word, 0) + 1
            }
        }

        return wordCount.maxByOrNull { it.value }!!.key
    }

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

Главный навык на ближайшие годы — ВАЙБ-КОДИНГ ИИ уже пишет код, чинит баги, генерирует тесты, документацию и помогает запускать продукты быстрее, чем это делали классические команды разработки. И это уже не "будущее когда-нибудь", а реальность, которая меняет рынок уже сегодня И те, кто научится вайбкодить сейчас, будут увереннее конкурировать на рынке и зарабатывать больше тех, кто по-прежнему делает всё вручную. Стартовать с нуля поможет канал Вайб-кодинг. Там ребята круглосуточно мониторят более 320 российских и зарубежных источников и публикуют только главное: релизы, инструменты, гайды, курсы и практические кейсы. Подписывайтесь, нас уже 30 тысяч: @vibecoding_tg

Задача: 994. Rotting Oranges Сложность: medium Дан m x n сетка, где каждая ячейка может иметь одно из трех значений: 0, представляющее пустую ячейку, 1, представляющее свежий апельсин, 2, представляющее гнилой апельсин. Каждую минуту любой свежий апельсин, который находится в 4-х направленно смежной ячейке с гнилым апельсином, становится гнилым. Верните минимальное количество минут, которые должны пройти, пока в ячейке не останется свежих апельсинов. Если это невозможно, верните -1. Пример:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

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

class Solution {
    fun orangesRotting(grid: Array<IntArray>): Int {
        val queue = ArrayDeque<Pair<Int, Int>>()
        var freshCount = 0
        val directions = arrayOf(Pair(0, 1), Pair(1, 0), Pair(0, -1), Pair(-1, 0))
        
        for (i in grid.indices) {
            for (j in grid[0].indices) {
                when (grid[i][j]) {
                    2 -> queue.add(Pair(i, j))
                    1 -> freshCount++
                }
            }
        }
        
        if (freshCount == 0) return 0
        
        var minutes = 0
        while (queue.isNotEmpty()) {
            repeat(queue.size) {
                val (i, j) = queue.removeFirst()
                for ((di, dj) in directions) {
                    val ni = i + di
                    val nj = j + dj
                    if (ni in grid.indices && nj in grid[0].indices && grid[ni][nj] == 1) {
                        grid[ni][nj] = 2
                        freshCount--
                        queue.add(Pair(ni, nj))
                    }
                }
            }
            if (queue.isNotEmpty()) {
                minutes++
            }
        }
        
        return if (freshCount == 0) minutes else -1
    }
}

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

Задача: 345. Reverse Vowels of a String Сложность: easy Дана строка s, переверните только все гласные в строке и верните её. Гласные: 'a', 'e', 'i', 'o', 'u', а также их верхние регистры. Пример:

Input: s = "hello"
Output: "holle"

👨‍💻 Алгоритм: 1⃣Инициализация указателей и гласных: Создайте набор гласных для быстрой проверки. Установите два указателя: один на начало строки (left), другой на конец строки (right). 2⃣Перестановка гласных: Пока левый указатель меньше правого, перемещайте указатели к центру, пока не найдёте гласные. Обменивайте найденные гласные и продолжайте сдвигать указатели. 3⃣Завершение работы: Когда указатели пересекутся, остановите процесс и верните строку. 😎 Решение:

class Solution {
    fun reverseVowels(s: String): String {
        val vowels = "aeiouAEIOU".toSet()
        val chars = s.toCharArray()
        var left = 0
        var right = s.length - 1
        
        while (left < right) {
            if (chars[left] !in vowels) {
                left++
            } else if (chars[right] !in vowels) {
                right--
            } else {
                val temp = chars[left]
                chars[left] = chars[right]
                chars[right] = temp
                left++
                right--
            }
        }
        
        return String(chars)
    }
}

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

Задача: 484. Find Permutation Сложность: Medium Перестановка perm из n целых чисел всех чисел в диапазоне [1, n] может быть представлена в виде строки s длиной n - 1, где: s[i] == 'I', если perm[i] < perm[i + 1], и s[i] == 'D', если perm[i] > perm[i + 1]. Дана строка s, восстановите лексикографически наименьшую перестановку perm и верните её. Пример:

Input: s = "I"
Output: [1,2]
Explanation: [1,2] is the only legal permutation that can represented by s, where the number 1 and 2 construct an increasing relationship.

👨‍💻 Алгоритм: 1⃣Инициализация Создайте пустой стек stack. Создайте пустой список result для хранения конечной перестановки. 2⃣Для каждого числа i Если текущий символ в строке s равен 'D', добавьте i в стек. Если текущий символ в строке s равен 'I', добавьте i в стек, затем извлеките все элементы из стека и добавьте их в result. 3⃣Завершение Добавьте n в стек и извлеките все элементы из стека, добавив их в result. Верните список result, который представляет лексикографически наименьшую перестановку. 😎 Решение:

class Solution {
    fun findPermutation(s: String): IntArray {
        val res = IntArray(s.length + 1)
        val stack = Stack<Int>()
        var j = 0
        for (i in 1..s.length) {
            if (s[i - 1] == 'I') {
                stack.push(i)
                while (stack.isNotEmpty()) {
                    res[j++] = stack.pop()
                }
            } else {
                stack.push(i)
            }
        }
        stack.push(s.length + 1)
        while (stack.isNotEmpty()) {
            res[j++] = stack.pop()
        }
        return res
    }
}

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

Задача: 421. Maximum XOR of Two Numbers in an Array Сложность: medium Дан целочисленный массив nums, верните максимальный результат nums[i] XOR nums[j], где 0 <= i <= j < n. Пример:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

👨‍💻 Алгоритм: 1⃣Вычислите количество битов L для использования. Это длина максимального числа в двоичном представлении. Инициализируйте max_xor = 0. 2⃣Запустите цикл от i = L−1 до i = 0 (от самого левого бита L−1 до самого правого бита 0): Сдвигайте max_xor влево, чтобы освободить следующий бит. Инициализируйте переменную curr_xor = max_xor | 1, установив 1 в самом правом бите max_xor. Теперь проверьте, можно ли выполнить curr_xor, используя доступные префиксы. 3⃣Вычислите все возможные префиксы длины L−i, итерируя по nums: Поместите в HashSet префиксы префикс текущего числа длиной L−i: num >> i. Итерируйте по всем префиксам и проверьте, можно ли выполнить curr_xor, используя два из них: p1 ^ p2 == curr_xor. Используя свойство самопреобразования XOR p1 ^ p2 ^ p2 = p1, можно переписать это как p1 == curr_xor ^ p2 и просто проверить для каждого p, если curr_xor ^ p есть в префиксах. Если так, установите max_xor равным curr_xor, т.е. установите 1-бит в самом правом бите. В противном случае, пусть max_xor оставит 0-бит в самом правом бите. 😎 Решение:

class Solution {
    fun findMaximumXOR(nums: IntArray): Int {
        var maxNum = nums.maxOrNull() ?: 0
        val L = Integer.toBinaryString(maxNum).length

        var maxXor = 0
        for (i in L - 1 downTo 0) {
            maxXor = maxXor shl 1
            val currXor = maxXor or 1
            val prefixes = mutableSetOf<Int>()
            nums.forEach { prefixes.add(it shr i) }
            for (p in prefixes) {
                if (prefixes.contains(currXor xor p)) {
                    maxXor = currXor
                    break
                }
            }
        }
        return maxXor
    }
}

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

Задача: 827. Making A Large Island Сложность: hard Вам дан n x n бинарный матрица grid. Вам разрешено изменить не более одного 0 на 1. Верните размер самого большого острова в grid после выполнения этой операции. Остров — это группа 1, соединенных в 4 направлениях. Пример:

Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.

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

class Solution {
    private val directions = arrayOf(
        intArrayOf(-1, 0), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(0, 1)
    )
    private lateinit var grid: Array<IntArray>
    private var N = 0

    fun largestIsland(grid: Array<IntArray>): Int {
        this.grid = grid
        N = grid.size

        var index = 2
        val area = IntArray(N * N + 2)
        for (r in 0 until N) {
            for (c in 0 until N) {
                if (grid[r][c] == 1) {
                    area[index] = dfs(r, c, index)
                    index++
                }
            }
        }

        var ans = area.maxOrNull() ?: 0
        for (r in 0 until N) {
            for (c in 0 until N) {
                if (grid[r][c] == 0) {
                    val seen = mutableSetOf<Int>()
                    for ((nr, nc) in neighbors(r, c)) {
                        if (grid[nr][nc] > 1) {
                            seen.add(grid[nr][nc])
                        }
                    }
                    ans = maxOf(ans, 1 + seen.sumOf { area[it] })
                }
            }
        }
        return ans
    }

    private fun dfs(r: Int, c: Int, index: Int): Int {
        var ans = 1
        grid[r][c] = index
        for ((nr, nc) in neighbors(r, c)) {
            if (grid[nr][nc] == 1) {
                grid[nr][nc] = index
                ans += dfs(nr, nc, index)
            }
        }
        return ans
    }

    private fun neighbors(r: Int, c: Int): List<Pair<Int, Int>> {
        val result = mutableListOf<Pair<Int, Int>>()
        for (dir in directions) {
            val nr = r + dir[0]
            val nc = c + dir[1]
            if (nr in 0 until N && nc in 0 until N) {
                result.add(nr to nc)
            }
        }
        return result
    }

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

Задача: 952. Largest Component Size by Common Factor Сложность: hard Для бинарного дерева T мы можем определить операцию переворота следующим образом: выбираем любой узел и меняем местами левое и правое дочерние поддеревья. Бинарное дерево X эквивалентно бинарному дереву Y тогда и только тогда, когда мы можем сделать X равным Y после некоторого количества операций переворота. Учитывая корни двух бинарных деревьев root1 и root2, верните true, если эти два дерева эквивалентны перевороту, или false в противном случае. Пример:

Input: nums = [4,6,15,35]
Output: 4

👨‍💻 Алгоритм: 1⃣Построить граф, в котором узлы представляют числа из массива, а ребра между узлами существуют, если два числа имеют общий делитель больше 1. 2⃣Использовать алгоритм Union-Find для объединения узлов в связные компоненты. Для каждого числа в массиве nums найти его простые делители и использовать их для объединения узлов. 3⃣Найти размер наибольшей связной компоненты. 😎 Решение:

class Solution {
    fun largestComponentSize(nums: IntArray): Int {
        val parent = mutableMapOf<Int, Int>()
        val rank = mutableMapOf<Int, Int>()
        
        nums.forEach { num ->
            parent[num] = num
            rank[num] = 0
        }
        
        fun find(x: Int): Int {
            if (parent[x] != x) {
                parent[x] = find(parent[x]!!)
            }
            return parent[x]!!
        }
        
        fun union(x: Int, y: Int) {
            val rootX = find(x)
            val rootY = find(y)
            if (rootX != rootY) {
                when {
                    rank[rootX]!! > rank[rootY]!! -> parent[rootY] = rootX
                    rank[rootX]!! < rank[rootY]!! -> parent[rootX] = rootY
                    else -> {
                        parent[rootY] = rootX
                        rank[rootX] = rank[rootX]!! + 1
                    }
                }
            }
        }
        
        fun primeFactors(n: Int): Set<Int> {
            val factors = mutableSetOf<Int>()
            var n = n
            var d = 2
            while (d * d <= n) {
                while (n % d == 0) {
                    factors.add(d)
                    n /= d
                }
                d++
            }
            if (n > 1) {
                factors.add(n)
            }
            return factors
        }
        
        val primeToIndex = mutableMapOf<Int, MutableList<Int>>()
        nums.forEach { num ->
            val primes = primeFactors(num)
            primes.forEach { prime ->
                primeToIndex.computeIfAbsent(prime) { mutableListOf() }.add(num)
            }
        }
        
        primeToIndex.values.forEach { primes ->
            for (i in 1 until primes.size) {
                union(primes[0], primes[i])
            }
        }
        
        val size = mutableMapOf<Int, Int>()
        nums.forEach { num ->
            val root = find(num)
            size[root] = size.getOrDefault(root, 0) + 1
        }
        
        return size.values.maxOrNull()!!
    }
}

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

Задача: 641. Design Circular Deque Сложность: medium Разработайте свою реализацию круговой двусторонней очереди (deque). Реализуйте класс MyCircularDeque: MyCircularDeque(int k) Инициализирует deque с максимальным размером k. boolean insertFront() Добавляет элемент в переднюю часть Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean insertLast() Добавляет элемент в заднюю часть Deque. Возвращает true, если операция выполнена успешно, или false в противном случае. boolean deleteFront() Удаляет элемент из передней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean deleteLast() Удаляет элемент из задней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. int getFront() Возвращает передний элемент из Deque. Возвращает -1, если Deque пуст. int getRear() Возвращает последний элемент из Deque. Возвращает -1, если Deque пуст. boolean isEmpty() Возвращает true, если Deque пуст, или false в противном случае. boolean isFull() Возвращает true, если Deque полон, или false в противном случае. Пример:

Input
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 2, true, true, true, 4]

👨‍💻 Алгоритм: 1⃣Инициализация и проверка состояний: Реализуйте конструктор для инициализации кольцевой двусторонней очереди заданного размера и методы для проверки пустоты и полноты очереди. 2⃣Операции вставки: Реализуйте методы вставки элементов в переднюю и заднюю части очереди с учетом кольцевой структуры. 3⃣Операции удаления: Реализуйте методы удаления элементов из передней и задней частей очереди с учетом кольцевой структуры и методы для получения переднего и заднего элементов очереди. 😎 Решение:

class MyCircularDeque(k: Int) {
    private val deque = IntArray(k)
    private var front = 0
    private var rear = 0
    private var size = 0
    private val capacity = k

    fun insertFront(value: Int): Boolean {
        if (isFull()) return false
        front = (front - 1 + capacity) % capacity
        deque[front] = value
        size++
        return true
    }

    fun insertLast(value: Int): Boolean {
        if (isFull()) return false
        deque[rear] = value
        rear = (rear + 1) % capacity
        size++
        return true
    }

    fun deleteFront(): Boolean {
        if (isEmpty()) return false
        front = (front + 1) % capacity
        size--
        return true
    }

    fun deleteLast(): Boolean {
        if (isEmpty()) return false
        rear = (rear - 1 + capacity) % capacity
        size--
        return true
    }

    fun getFront(): Int {
        return if (isEmpty()) -1 else deque[front]
    }

    fun getRear(): Int {
        return if (isEmpty()) -1 else deque[(rear - 1 + capacity) % capacity]
    }

    fun isEmpty(): Boolean {
        return size == 0
    }

    fun isFull(): Boolean {
        return size == capacity
    }
}

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

Задача: 683. K Empty Slots Сложность: hard У вас есть n лампочек, расположенных в ряд и пронумерованных от 1 до n. Изначально все лампочки выключены. Каждый день мы включаем ровно одну лампочку, и через n дней все лампочки будут включены. Вам дан массив bulbs длины n, где bulbs[i] = x означает, что в (i+1)-й день мы включим лампочку в позиции x, где i индексируется с 0, а x индексируется с 1. Дано целое число k, верните минимальный номер дня, такой что существует две включенные лампочки, между которыми ровно k выключенных лампочек. Если такого дня не существует, верните -1. Пример:

Input: bulbs = [1,3,2], k = 1
Output: 2
Explanation:
On the first day: bulbs[0] = 1, first bulb is turned on: [1,0,0]
On the second day: bulbs[1] = 3, third bulb is turned on: [1,0,1]
On the third day: bulbs[2] = 2, second bulb is turned on: [1,1,1]
We return 2 because on the second day, there were two on bulbs with one off bulb between them.

👨‍💻 Алгоритм: 1⃣Поддерживайте active, отсортированную структуру данных, содержащую каждую лампочку, которая в данный момент включена. Это позволит быстро находить соседей для вновь добавленных лампочек и проверять условия задачи. 2⃣Когда вы добавляете лампочку в active, проверьте ее нижних и верхних соседей. Для этого найдите ближайшие включенные лампочки с обеих сторон и проверьте количество выключенных лампочек между ними. 3⃣Если какой-то сосед удовлетворяет условию (ровно k выключенных лампочек между двумя включенными), значит, условие впервые произошло в этот день, и вы можете вернуть номер этого дня. Если такого дня не существует после включения всех лампочек, верните -1. 😎 Решение:

import java.util.TreeSet

class Solution {
    fun kEmptySlots(flowers: IntArray, k: Int): Int {
        val active = TreeSet<Int>()
        var day = 0
        
        for (flower in flowers) {
            day++
            active.add(flower)
            val lower = active.lower(flower)
            val higher = active.higher(flower)
            
            if ((lower != null && flower - lower - 1 == k) ||
                (higher != null && higher - flower - 1 == k)) {
                return day
            }
        }
        return -1
    }
}

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

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

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