Kotlin | LeetCode

Задача: 979. Distribute Coins in Binary Tree Сложность: medium Вам дан корень бинарного дерева с n узлами, где каждый узел в дереве содержит node.val монет. Всего по всему дереву распределено n монет. За один ход мы можем выбрать два смежных узла и переместить одну монету из одного узла в другой. Ход может быть как от родителя к ребенку, так и от ребенка к родителю. Верните минимальное количество ходов, необходимых для того, чтобы каждый узел имел ровно одну монету. Пример:

    
        Input: root = [3,0,0]
Output: 2
Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.{}
    

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

    
        class Solution {
    private var moves = 0

    fun distributeCoins(root: TreeNode?): Int {
        dfs(root)
        return moves
    }

    private fun dfs(current: TreeNode?): Int {
        if (current == null) return 0
        val leftCoins = dfs(current.left)
        val rightCoins = dfs(current.right)
        moves += Math.abs(leftCoins) + Math.abs(rightCoins)
        return current.`val` - 1 + leftCoins + rightCoins
    }
}{}
    

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

Задача: 260. Single Number III Сложность: medium Дан целочисленный массив nums, в котором ровно два элемента встречаются только один раз, а все остальные элементы встречаются ровно дважды. Найдите два элемента, которые встречаются только один раз. Вы можете вернуть ответ в любом порядке. Вы должны написать алгоритм, который работает за линейное время и использует только постоянное дополнительное пространство.. Пример:

    
        Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation:  [5, 3] is also a valid answer.{}
    

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

    
        class Solution {
    fun singleNumber(nums: IntArray): IntArray {
        val xor = nums.reduce { acc, num -> acc xor num }
        val diff = xor and -xor
        val res = intArrayOf(0, 0)
        for (num in nums) {
            if (num and diff == 0) {
                res[0] = res[0] xor num
            } else {
                res[1] = res[1] xor num
            }
        }
        return res
    }
}{}
    

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

Задача: 965. Univalued Binary Tree Сложность: easy Бинарное дерево является одноценным, если каждый узел в дереве имеет одинаковое значение. Дан корень бинарного дерева, верните true, если данное дерево является одноценным, или false в противном случае. Пример:

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

👨‍💻 Алгоритм: 1⃣Выполните обход дерева в глубину (DFS), чтобы собрать все значения узлов в список. 2⃣Проверьте, что все значения в списке одинаковы. 3⃣Если все значения одинаковы, верните true, иначе верните false. 😎 Решение:

    
        class Solution {
    private val vals = mutableListOf<Int>()
    
    fun isUnivalTree(root: TreeNode?): Boolean {
        dfs(root)
        return vals.all { it == vals[0] }
    }

    private fun dfs(node: TreeNode?) {
        if (node != null) {
            vals.add(node.`val`)
            dfs(node.left)
            dfs(node.right)
        }
    }
}{}
    

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

Задача: 832. Flipping an Image Сложность: easy Дано бинарное изображение размером n x n, необходимо перевернуть изображение по горизонтали, затем инвертировать его и вернуть результат. Перевернуть изображение по горизонтали означает, что каждая строка изображения будет развернута. Например, переворот строки [1,1,0] по горизонтали дает [0,1,1]. Инвертировать изображение означает, что каждый 0 заменяется на 1, а каждый 1 заменяется на 0. Например, инверсия строки [0,1,1] дает [1,0,0]. Пример:

    
        Input: image = [[1,1,0],[1,0,1],[0,0,0]]
Output: [[1,0,0],[0,1,0],[1,1,1]]
Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]{}
    

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

    
        class Solution {
    fun flipAndInvertImage(A: Array<IntArray>): Array<IntArray> {
        val C = A[0].size

        for (row in A) {
            for (i in 0 until (C + 1) / 2) {
                val tmp = row[i] xor 1
                row[i] = row[C - 1 - i] xor 1
                row[C - 1 - i] = tmp
            }
        }

        return A
    }{}
    

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

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

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

Задача: 30. Substring with Concatenation of All Words Сложность: hard Вам дана строка s и массив строк words. Все строки в words имеют одинаковую длину. Объединенная строка — это строка, содержащая все строки из words в любой перестановке. Верните массив начальных индексов всех таких подстрок в s. Порядок ответа не имеет значения. Пример:

    
        Input: s = "barfoothefoobarman", words = ["foo","bar"]  
Output: [0,9]  {}
    

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

    
        class Solution {
    fun findSubstring(s: String, words: Array<String>): List<Int> {
        val result = mutableListOf<Int>()
        if (s.isEmpty() || words.isEmpty()) return result

        val wordLength = words[0].length
        val substringLength = wordLength * words.size
        val wordCount = words.groupingBy { it }.eachCount()

        for (i in 0..s.length - substringLength) {
            val seen = s.substring(i, i + substringLength)
                .chunked(wordLength)
                .groupingBy { it }
                .eachCount()

            if (seen == wordCount) result.add(i)
        }

        return result
    }
}{}
    

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

Задача: 668. Kth Smallest Number in Multiplication Table Сложность: hard Почти каждый использовал таблицу умножения. Таблица умножения размером m x n - это целочисленная матрица mat, где mat[i][j] == i * j (индексация начинается с 1). Даны три целых числа m, n и k. Верните k-й наименьший элемент в таблице умножения размером m x n. Пример:

    
        Input: m = 3, n = 3, k = 5
Output: 3
Explanation: The 5th smallest number is 3.{}
    

👨‍💻 Алгоритм: 1⃣Установка границ поиска: Установите нижнюю границу left равной 1 и верхнюю границу right равной m * n. 2⃣Бинарный поиск: Используйте бинарный поиск, чтобы найти k-й наименьший элемент. Для каждого среднего значения mid, посчитайте количество элементов в таблице умножения, которые меньше или равны mid. 3⃣Проверка количества элементов: Если количество элементов меньше k, увеличьте нижнюю границу (left). Если количество элементов больше или равно k, уменьшите верхнюю границу (right). 😎 Решение:

    
        class Solution {
    fun findKthNumber(m: Int, n: Int, k: Int): Int {
        fun countLessEqual(x: Int): Int {
            var count = 0
            for (i in 1..m) {
                count += minOf(x / i, n)
            }
            return count
        }
        
        var left = 1
        var right = m * n
        while (left < right) {
            val mid = (left + right) / 2
            if (countLessEqual(mid) < k) {
                left = mid + 1
            } else {
                right = mid
            }
        }
        return left
    }
}{}
    

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

Задача: 204. Count Primes Сложность: medium Дано целое число n, верните количество простых чисел, которые строго меньше n. Пример:

    
        Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.{}
    

👨‍💻 Алгоритм: 1⃣Создайте список последовательных целых чисел от 2 до n: (2, 3, 4, ..., n). Пусть p будет переменной, используемой во внешнем цикле, проходящем от 2 до n. Изначально p равно 2, самому маленькому простому числу. 2⃣Перечислите кратные числа p, считая с шагом p от pp до n и отметьте их в списке (это будут pp, pp + p, pp + 2*p и т.д.; само число p должно быть простым). Найдите наименьшее число в списке, большее p, которое не отмечено. Если такого числа нет, остановитесь. В противном случае, пусть p теперь равно этому новому числу (следующее простое) и повторите шаг 2. 3⃣Когда алгоритм завершится, все оставшиеся числа, которые не отмечены, являются простыми. 😎 Решение:

    
        class Solution {
    fun countPrimes(n: Int): Int {
        if (n <= 2) {
            return 0
        }

        val numbers = BooleanArray(n) { true }
        for (p in 2..Math.sqrt(n.toDouble()).toInt()) {
            if (numbers[p]) {
                for (j in p * p until n step p) {
                    numbers[j] = false
                }
            }
        }

        var numberOfPrimes = 0
        for (i in 2 until n) {
            if (numbers[i]) {
                numberOfPrimes++
            }
        }

        return numberOfPrimes
    }
}{}
    

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

Задача: 172. Factorial Trailing Zeroes Сложность: medium Дано целое число n, верните количество конечных нулей в n!. Обратите внимание, что n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1. Пример:

    
        Input: n = 3
Output: 0
Explanation: 3! = 6, no trailing zero.{}
    

👨‍💻 Алгоритм: 1⃣Вычислите факториал n: Инициализируйте переменную nFactorial значением 1. Для каждого i от 2 до n включительно умножайте nFactorial на i. 2⃣Подсчитайте количество конечных нулей в nFactorial: Инициализируйте переменную zeroCount значением 0. Пока nFactorial делится на 10 без остатка, делите его на 10 и увеличивайте zeroCount на 1. 3⃣Верните значение zeroCount как количество конечных нулей в n!. 😎 Решение:

    
        class Solution {
    fun trailingZeroes(n: Int): Int {
        var nFactorial = 1L
        for (i in 2..n) {
            nFactorial *= i
        }

        var zeroCount = 0
        while (nFactorial % 10 == 0L) {
            zeroCount += 1
            nFactorial /= 10
        }

        return zeroCount
    }
}{}
    

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

Задача: 905. Sort Array By Parity Сложность: easy Если задан целочисленный массив nums, переместите все четные числа в начало массива, а затем все нечетные. Верните любой массив, удовлетворяющий этому условию. Пример:

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

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

    
        class Solution {
    fun sortArrayByParity(nums: IntArray): IntArray {
        val evens = mutableListOf<Int>()
        val odds = mutableListOf<Int>()
        for (num in nums) {
            if (num % 2 == 0) {
                evens.add(num)
            } else {
                odds.add(num)
            }
        }
        evens.addAll(odds)
        return evens.toIntArray()
    }
}{}
    

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