Kotlin | LeetCode

Задача: 338. Counting Bits Сложность: easy Дано целое число n, верните массив ans длиной n + 1, такой что для каждого i (0 <= i <= n), ans[i] будет равняться количеству единиц в двоичном представлении числа i. Пример:

    
        Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101{}
    

👨‍💻 Алгоритм: 1⃣Инициализация массива: Создайте массив ans длиной n + 1, заполненный нулями. Этот массив будет содержать количество единиц в двоичном представлении каждого числа от 0 до n. 2⃣Итерация и вычисление: Пройдите в цикле по всем числам от 1 до n. Для каждого числа x используйте битовую операцию x & (x - 1), чтобы убрать последнюю установленную биту, и добавьте 1 к значению ans для этого результата. Это количество единиц в двоичном представлении числа x. 3⃣Возврат результата: Верните заполненный массив ans, который содержит количество единиц для каждого числа от 0 до n. 😎 Решение:

    
        class Solution {
    fun countBits(num: Int): IntArray {
        val ans = IntArray(num + 1)
        for (x in 1..num) {
            ans[x] = ans[x and (x - 1)] + 1
        }
        return ans
    }
}{}
    

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

Задача: 1662. Check If Two String Arrays are Equivalent Сложность: easy Даны два массива строк word1 и word2. Верните true, если два массива представляют одну и ту же строку, и false в противном случае. Строка представлена массивом, если элементы массива, соединенные в порядке, образуют строку. Пример:

    
        Input: word1 = ["ab", "c"], word2 = ["a", "bc"]
Output: true
Explanation:
word1 represents string "ab" + "c" -> "abc"
word2 represents string "a" + "bc" -> "abc"
The strings are the same, so return true.{}
    

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

    
        class Solution {
    fun arrayStringsAreEqual(word1: Array<String>, word2: Array<String>): Boolean {
        val list2 = word2.joinToString("")
        var index = 0

        for (word in word1) {
            for (char in word) {
                if (index >= list2.length || char != list2[index]) {
                    return false
                }
                index++
            }
        }

        return index == list2.length
    }
}{}
    

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

Задача: 1207. Unique Number of Occurrences Сложность: easy Дан массив целых чисел arr. Верните true, если количество вхождений каждого значения в массиве уникально, или false в противном случае. Пример:

    
        Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.{}
    

👨‍💻 Алгоритм: 1⃣Сохраните частоты элементов массива arr в хэш-таблице freq. 2⃣Итерируйтесь по хэш-таблице freq и вставьте частоты всех уникальных элементов массива arr в хэш-набор freqSet. 3⃣Верните true, если размер хэш-набора freqSet равен размеру хэш-таблицы freq, иначе верните false. 😎 Решение:

    
        class Solution {
    fun uniqueOccurrences(arr: IntArray): Boolean {
        val freq = mutableMapOf<Int, Int>()
        for (num in arr) {
            freq[num] = freq.getOrDefault(num, 0) + 1
        }
        return freq.values.toSet().size == freq.size
    }
}{}
    

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

Задача: 776. Split BST Сложность: medium Дан корень бинарного дерева поиска (BST) и целое число target, разделите дерево на два поддерева, где первое поддерево содержит узлы, которые меньше или равны значению target, а второе поддерево содержит узлы, которые больше значения target. Не обязательно, чтобы дерево содержало узел со значением target. Кроме того, большая часть структуры исходного дерева должна сохраниться. Формально, для любого потомка c с родителем p в исходном дереве, если они оба находятся в одном поддереве после разделения, то узел c все еще должен иметь родителя p. Верните массив из двух корней двух поддеревьев в порядке. Пример:

    
        Input: root = [4,2,6,1,3,5,7], target = 2
Output: [[2,1],[4,3,6,null,null,5,7]]{}
    

👨‍💻 Алгоритм: 1⃣Базовый случай: Если корень равен null, верните массив, содержащий два указателя null. Это необходимо для обработки случая, когда дерево пустое. 2⃣Проверьте, больше ли значение корня целевого значения. Если да, рекурсивно разделите левое поддерево, вызвав splitBST(root->left, target). Прикрепите правую часть разделенного к левому поддереву корня. Верните массив, содержащий левую часть разделенного и текущий корень. 3⃣Если значение корня меньше или равно целевому значению, рекурсивно разделите правое поддерево, вызвав splitBST(root->right, target). Прикрепите левую часть разделенного к правому поддереву корня. Верните массив, содержащий левую часть разделенного и текущий корень. 😎 Решение:

    
        class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class Solution {
    fun splitBST(root: TreeNode?, target: Int): Array<TreeNode?> {
        if (root == null) {
            return arrayOf(null, null)
        }

        return if (root.`val` > target) {
            val left = splitBST(root.left, target)
            root.left = left[1]
            arrayOf(left[0], root)
        } else {
            val right = splitBST(root.right, target)
            root.right = right[0]
            arrayOf(root, right[1])
        }
    }
}{}
    

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

Задача: 318. Maximum Product of Word Lengths Сложность: medium Дан массив строк words, верните максимальное значение произведения длины word[i] на длину word[j], где два слова не имеют общих букв. Если таких двух слов не существует, верните 0. Пример:

    
        Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".{}
    

👨‍💻 Алгоритм: 1⃣Предварительная обработка масок и длин Вычислите битовые маски для всех слов и сохраните их в массиве masks. Сохраните длины всех слов в массиве lens. 2⃣Сравнение слов и проверка общих букв Сравните каждое слово с каждым последующим словом. Если два слова не имеют общих букв (проверка с использованием масок: (masks[i] & masks[j]) == 0), обновите максимальное произведение maxProd. 3⃣Возврат результата Верните максимальное значение произведения maxProd. 😎 Решение:

    
        class Solution {
    fun maxProduct(words: Array<String>): Int {
        val n = words.size
        val masks = IntArray(n)
        val lens = IntArray(n)
        
        for (i in 0 until n) {
            var bitmask = 0
            for (ch in words[i]) {
                bitmask = bitmask or (1 shl (ch - 'a'))
            }
            masks[i] = bitmask
            lens[i] = words[i].length
        }
        
        var maxVal = 0
        for (i in 0 until n) {
            for (j in i + 1 until n) {
                if (masks[i] and masks[j] == 0) {
                    maxVal = maxOf(maxVal, lens[i] * lens[j])
                }
            }
        }
        return maxVal
    }
}{}
    

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

Задача: 239. Sliding Window Maximum Сложность: hard Вам дан массив целых чисел nums. Существует скользящее окно размера k, которое перемещается с самого левого конца массива до самого правого. Вы можете видеть только k чисел в окне. Каждый раз скользящее окно перемещается вправо на одну позицию. Верните максимальные значения скользящего окна. Пример:

    
        Input: nums = [1], k = 1
Output: [1]{}
    

👨‍💻 Алгоритм: 1⃣Инициализация и заполнение первой части окна: Создайте двустороннюю очередь dq для хранения индексов элементов и список res для хранения результатов. Пройдите по первым k элементам массива nums (от i = 0 до k - 1). Для каждого элемента: Удалите из dq все элементы, которые меньше или равны текущему элементу nums[i]. Добавьте текущий индекс i в конец dq. Добавьте в res максимальный элемент первого окна, который находится в nums[dq[0]]. 2⃣Сканирование оставшейся части массива: Пройдите по оставшимся элементам массива nums (от i = k до n - 1). Для каждого элемента: Если индекс элемента на передней части dq равен i - k, удалите этот элемент из dq, так как он выходит за пределы текущего окна. Удалите из dq все элементы, которые меньше или равны текущему элементу nums[i]. Добавьте текущий индекс i в конец dq. Добавьте в res максимальный элемент текущего окна, который находится в nums[dq[0]]. 3⃣Возвращение результата: Верните список res, содержащий максимальные элементы для каждого скользящего окна. 😎 Решение:

    
        class Solution {
    fun maxSlidingWindow(nums: IntArray, k: Int): IntArray {
        val dq = ArrayDeque<Int>()
        val res = mutableListOf<Int>()
        
        for (i in 0 until k) {
            while (dq.isNotEmpty() && nums[i] >= nums[dq.last()]) {
                dq.removeLast()
            }
            dq.addLast(i)
        }
        res.add(nums[dq.first()])

        for (i in k until nums.size) {
            if (dq.first() == i - k) {
                dq.removeFirst()
            }
            while (dq.isNotEmpty() && nums[i] >= nums[dq.last()]) {
                dq.removeLast()
            }
            dq.addLast(i)
            res.add(nums[dq.first()])
        }
        
        return res.toIntArray()
    }
}{}
    

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

Задача: 1277. Count Square Submatrices with All Ones Сложность: medium Если задана матрица m * n из единиц и нулей, верните, сколько квадратных подматриц имеют все единицы. Пример:

    
        Input: matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
Output: 15{}
    

👨‍💻 Алгоритм: 1⃣Создайте вспомогательную матрицу dp таких же размеров, что и исходная матрица, для хранения размеров максимальных квадратов. 2⃣Пройдите по каждому элементу матрицы и обновите dp следующим образом: если элемент равен 1, то dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1. 3⃣Суммируйте все значения в dp, чтобы получить количество квадратных подматриц, состоящих из всех единиц. 😎 Решение:

    
        class Solution {
    fun countSquares(matrix: Array<IntArray>): Int {
        val m = matrix.size
        val n = matrix[0].size
        val dp = Array(m) { IntArray(n) }
        var count = 0

        for (i in 0 until m) {
            for (j in 0 until n) {
                if (matrix[i][j] == 1) {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1
                    } else {
                        dp[i][j] = minOf(dp[i-1][j], minOf(dp[i][j-1], dp[i-1][j-1])) + 1
                    }
                    count += dp[i][j]
                }
            }
        }

        return count
    }
}{}
    

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

Задача: 144. Binary Tree Preorder Traversal Сложность: easy Дан корень бинарного дерева, верните предварительный обход значений его узлов. Пример:

    
        Input: root = [1,null,2,3]
Output: [1,2,3]{}
    

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

    
        class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class Solution {
    fun preorderTraversal(root: TreeNode?): List<Int> {
        if (root == null) {
            return emptyList()
        }

        val stack = mutableListOf(root)
        val output = mutableListOf<Int>()

        while (stack.isNotEmpty()) {
            val node = stack.removeAt(stack.lastIndex)
            output.add(node.`val`)
            node.right?.let { stack.add(it) }
            node.left?.let { stack.add(it) }
        }

        return output
    }
}{}
    

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

Задача: 1182. Shortest Distance to Target Color Сложность: medium Дан массив colors, содержащий три цвета: 1, 2 и 3. Также даны несколько запросов. Каждый запрос состоит из двух целых чисел i и c. Верните наименьшее расстояние между заданным индексом i и целевым цветом c. Если решения нет, верните -1. Пример:

    
        Input: colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]]
Output: [3,0,3]
Explanation: 
The nearest 3 from index 1 is at index 4 (3 steps away).
The nearest 2 from index 2 is at index 2 itself (0 steps away).
The nearest 1 from index 6 is at index 3 (3 steps away).{}
    

👨‍💻 Алгоритм: 1⃣Инициализируйте хэш-таблицу для отображения каждого цвета в список индексов. Итерируйте по массиву colors и добавляйте каждый индекс в соответствующий список хэш-таблицы. 2⃣Для каждого запроса, содержащего i и c, если c не является одним из ключей в хэш-таблице, то colors не содержит c, поэтому верните -1. Иначе, найдите позицию i в соответствующем списке индексов indexList для поддержания упорядоченного порядка. 3⃣Если i меньше всех элементов в indexList, то i - indexList[0] является кратчайшим расстоянием. Если i больше всех элементов в indexList, то indexList[indexList.size() - 1] - i является кратчайшим расстоянием. Иначе, ближайшее появление c к i либо на индексе вставки, либо перед ним, поэтому рассчитайте расстояние от i до каждого из них и верните наименьшее. 😎 Решение:

    
        class Solution {
    fun shortestDistanceColor(colors: IntArray, queries: Array<IntArray>): List<Int> {
        val queryResults = mutableListOf<Int>()
        val hashmap = mutableMapOf<Int, MutableList<Int>>()

        for (i in colors.indices) {
            hashmap.putIfAbsent(colors[i], mutableListOf())
            hashmap[colors[i]]!!.add(i)
        }

        for (query in queries) {
            val target = query[0]
            val color = query[1]
            val indexList = hashmap[color]

            if (indexList == null) {
                queryResults.add(-1)
                continue
            }

            val insert = indexList.binarySearch(target)

            val insertPos = if (insert < 0) -insert - 1 else insert

            if (insertPos == 0) {
                queryResults.add(indexList[insertPos] - target)
            } else if (insertPos == indexList.size) {
                queryResults.add(target - indexList[insertPos - 1])
            } else {
                val leftNearest = target - indexList[insertPos - 1]
                val rightNearest = indexList[insertPos] - target
                queryResults.add(min(leftNearest, rightNearest))
            }
        }

        return queryResults
    }
}{}
    

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

Задача: 985. Sum of Even Numbers After Queries Сложность: medium Дан целочисленный массив nums и массив queries, где queries[i] = [vali, indexi]. Для каждого запроса i, сначала примените nums[indexi] = nums[indexi] + vali, затем выведите сумму четных значений nums. Верните целочисленный массив answer, где answer[i] - это ответ на i-й запрос. Пример:

    
        Input: nums = [1], queries = [[4,0]]
Output: [0]{}
    

👨‍💻 Алгоритм: 1⃣Инициализация переменных: Завести переменную evenSum для хранения суммы всех четных чисел в массиве nums. Пройти по массиву nums и вычислить начальное значение evenSum, сложив все четные числа в nums. 2⃣Обработка запросов: Создать пустой массив result для хранения ответов на каждый запрос. Для каждого запроса [val, index] из массива queries выполнить следующие действия: Если значение nums[index] четное, вычесть его из evenSum. Обновить nums[index] добавлением val. Если новое значение nums[index] четное, добавить его к evenSum. Добавить текущее значение evenSum в массив result. 3⃣Возврат результата: Вернуть массив result, содержащий ответы на все запросы. 😎 Решение:

    
        fun sumEvenAfterQueries(nums: IntArray, queries: Array<IntArray>): IntArray {
    var evenSum = nums.filter { it % 2 == 0 }.sum()
    val result = IntArray(queries.size)
    
    for (i in queries.indices) {
        val (value, index) = queries[i]
        if (nums[index] % 2 == 0) {
            evenSum -= nums[index]
        }
        nums[index] += value
        if (nums[index] % 2 == 0) {
            evenSum += nums[index]
        }
        result[i] = evenSum
    }
    
    return result
}{}
    

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