Kotlin | LeetCode

Задача: 767. Reorganize String Сложность: medium Дана строка s, переставьте символы строки s так, чтобы любые два соседних символа не были одинаковыми. Верните любую возможную перестановку строки s или верните "", если это невозможно. Пример:

    
        Input: s = "aab"
Output: "aba"{}
    

👨‍💻 Алгоритм: 1⃣Инициализируйте пустой список ans для хранения переставленных символов. Создайте приоритетную очередь pq, используя структуру данных кучи. Каждый элемент в pq — это кортеж, содержащий количество символов и сам символ. Приоритетная очередь упорядочена так, что элементы с большим количеством имеют более высокий приоритет. 2⃣Извлеките элемент с наивысшим приоритетом из pq. Присвойте его количество и символ переменным count_first и char_first соответственно. Если ans пуст или текущий символ char_first отличается от последнего символа в ans, добавьте char_first в ans. Если количество char_first не равно нулю, уменьшите его на один. Если обновленное количество больше нуля, поместите его обратно в pq. Перейдите к следующей итерации. 3⃣В противном случае, если char_first совпадает с последним символом в ans, нужно выбрать другой символ. Если pq пуста, верните пустую строку, так как переставить символы невозможно. Извлеките следующий элемент из pq, присвоив его количество и символ переменным count_second и char_second соответственно. Добавьте char_second в ans. Если количество char_second не равно нулю, уменьшите его на один. Если обновленное количество больше нуля, поместите его обратно в pq. Наконец, поместите оригинальный char_first обратно в pq. Верните переставленные символы как строку, объединив элементы в ans. 😎 Решение:

    
        import java.util.PriorityQueue

class Solution {
    fun reorganizeString(s: String): String {
        val charCounts = IntArray(26)
        for (c in s) {
            charCounts[c - 'a']++
        }
        
        val pq = PriorityQueue(compareByDescending<Pair<Int, Char>> { it.first })
        for (i in 0 until 26) {
            if (charCounts[i] > 0) {
                pq.add(Pair(charCounts[i], 'a' + i))
            }
        }
        
        val result = StringBuilder()
        while (pq.isNotEmpty()) {
            val first = pq.poll()
            if (result.isEmpty() || first.second != result.last()) {
                result.append(first.second)
                if (first.first > 1) {
                    pq.add(Pair(first.first - 1, first.second))
                }
            } else {
                if (pq.isEmpty()) {
                    return ""
                }
                val second = pq.poll()
                result.append(second.second)
                if (second.first > 1) {
                    pq.add(Pair(second.first - 1, second.second))
                }
                pq.add(first)
            }
        }
        
        return result.toString()
    }
}{}
    

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

Задача: 97. Interleaving String Сложность: medium Даны строки s1, s2 и s3. Необходимо определить, может ли строка s3 быть сформирована путем чередования строк s1 и s2. Чередование двух строк s и t — это конфигурация, при которой s и t делятся на n и m подстрок соответственно так, что: s = s1 + s2 + ... + sn t = t1 + t2 + ... + tm |n - m| ≤ 1 Чередование может быть таким: s1 + t1 + s2 + t2 + s3 + t3 + ... или t1 + s1 + t2 + s2 + t3 + s3 + ... Примечание: a + b означает конкатенацию строк a и b. Пример:

    
        Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Explanation: One way to obtain s3 is:
Split s1 into s1 = "aa" + "bc" + "c", and s2 into s2 = "dbbc" + "a".
Interleaving the two splits, we get "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac".{}
    

👨‍💻 Алгоритм: 1⃣В рекурсивном подходе, описанном выше, рассматривается каждая возможная строка, образованная путем чередования двух заданных строк. Однако возникают случаи, когда та же часть s1 и s2 уже была обработана, но в разных порядках (перестановках). Независимо от порядка обработки, если результирующая строка до этого момента совпадает с требуемой строкой (s3), окончательный результат зависит только от оставшихся частей s1 и s2, а не от уже обработанной части. Таким образом, рекурсивный подход приводит к избыточным вычислениям. 2⃣Эту избыточность можно устранить, используя мемоизацию вместе с рекурсией. Для этого мы поддерживаем три указателя i, j, k, которые соответствуют индексу текущего символа s1, s2, s3 соответственно. Также мы поддерживаем двумерный массив memo для отслеживания обработанных до сих пор подстрок. memo[i][j] хранит 1/0 или -1 в зависимости от того, была ли текущая часть строк, то есть до i-го индекса для s1 и до j-го индекса для s2, уже оценена. Мы начинаем с выбора текущего символа s1 (на который указывает i). Если он совпадает с текущим символом s3 (на который указывает k), мы включаем его в обработанную строку и вызываем ту же функцию рекурсивно как: is_Interleave(s1, i+1, s2, j, s3, k+1, memo). 3⃣Таким образом, мы вызвали функцию, увеличив указатели i и k, поскольку часть строк до этих индексов уже была обработана. Аналогично, мы выбираем один символ из второй строки и продолжаем. Рекурсивная функция заканчивается, когда одна из двух строк s1 или s2 полностью обработана. Если, скажем, строка s1 полностью обработана, мы напрямую сравниваем оставшуюся часть s2 с оставшейся частью s3. Когда происходит возврат из рекурсивных вызовов, мы сохраняем значение, возвращенное рекурсивными функциями, в массиве мемоизации memo соответственно, так что когда оно встречается в следующий раз, рекурсивная функция не будет вызвана, но сам массив мемоизации вернет предыдущий сгенерированный результат. 😎 Решение:

    
        class Solution {
    fun isInterleave(s1: String, s2: String, s3: String): Boolean {
        if (s3.length != s1.length + s2.length) return false

        val dp = Array(s1.length + 1) { BooleanArray(s2.length + 1) }
        for (i in 0..s1.length) {
            for (j in 0..s2.length) {
                when {
                    i == 0 && j == 0 -> dp[i][j] = true
                    i == 0 -> dp[i][j] = dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]
                    j == 0 -> dp[i][j] = dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]
                    else -> dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]) || (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1])
                }
            }
        }
        return dp[s1.length][s2.length]
    }
}

// Example usage
fun main() {
    val solution = Solution()
    val s1 = "abc"
    val s2 = "def"
    val s3 = "adbcef"
    println("Can s3 be formed by interleaving s1 and s2? ${solution.isInterleave(s1, s2, s3)}")
}{}
    

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

Задача: 75. Sort Colors Сложность: medium Дан массив nums, содержащий n объектов, окрашенных в красный, белый или синий цвет. Отсортируйте их на месте так, чтобы объекты одного цвета находились рядом, а цвета располагались в порядке красный, белый и синий. Мы будем использовать целые числа 0, 1 и 2 для обозначения красного, белого и синего цветов соответственно. Вы должны решить эту задачу без использования функции сортировки библиотеки. Пример:

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

👨‍💻 Алгоритм: 1⃣Инициализация крайней правой границы нулей: p0 = 0. Во время выполнения алгоритма nums[idx < p0] = 0. 2⃣Инициализация крайней левой границы двоек: p2 = n - 1. Во время выполнения алгоритма nums[idx > p2] = 2. 3⃣Инициализация индекса текущего элемента для рассмотрения: curr = 0. Пока curr <= p2: Если nums[curr] = 0: поменять местами элементы с индексами curr и p0, и сдвинуть оба указателя вправо. Если nums[curr] = 2: поменять местами элементы с индексами curr и p2. Сдвинуть указатель p2 влево. Если nums[curr] = 1: сдвинуть указатель curr вправо. 😎 Решение:

    
        class Solution {
    fun sortColors(nums: IntArray) {
        var p0 = 0
        var curr = 0
        var p2 = nums.size - 1

        while (curr <= p2) {
            when {
                nums[curr] == 0 -> {
                    nums.swap(p0, curr)
                    p0++
                    curr++
                }
                nums[curr] == 2 -> {
                    nums.swap(curr, p2)
                    p2--
                }
                else -> curr++
            }
        }
    }

    private fun IntArray.swap(i: Int, j: Int) {
        val temp = this[i]
        this[i] = this[j]
        this[j] = temp
    }
}{}
    

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

Задача: 912. Sort an Array Сложность: medium Задав массив целых чисел nums, отсортируйте массив по возрастанию и верните его. Вы должны решить задачу без использования встроенных функций за время O(nlog(n)) и с минимально возможной пространственной сложностью. Пример:

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

👨‍💻 Алгоритм: 1⃣Используем алгоритм "Сортировка слиянием" (Merge Sort), который обеспечивает время выполнения O(n log n) и минимально возможную пространственную сложность для стабильного сортировочного алгоритма. 2⃣Разделить массив на две половины. Рекурсивно отсортировать каждую половину. 3⃣Слить две отсортированные половины. 😎 Решение:

    
        fun mergeSort(nums: IntArray) {
    if (nums.size > 1) {
        val mid = nums.size / 2
        val left_half = nums.sliceArray(0 until mid)
        val right_half = nums.sliceArray(mid until nums.size)

        mergeSort(left_half)
        mergeSort(right_half)

        var i = 0
        var j = 0
        var k = 0
        while (i < left_half.size && j < right_half.size) {
            if (left_half[i] < right_half[j]) {
                nums[k++] = left_half[i++]
            } else {
                nums[k++] = right_half[j++]
            }
        }

        while (i < left_half.size) {
            nums[k++] = left_half[i++]
        }

        while (j < right_half.size) {
            nums[k++] = right_half[j++]
        }
    }
}{}
    

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

📺 База 1000+ реальных собеседований На программиста, тестировщика, аналитика, проджекта и другие IT профы. Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д. 🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!

Задача: 376. Wiggle Subsequence Сложность: easy Колеблющаяся последовательность — это последовательность, в которой разности между последовательными числами строго чередуются между положительными и отрицательными. Первая разность (если она существует) может быть как положительной, так и отрицательной. Последовательность с одним элементом и последовательность с двумя неравными элементами тривиально являются колеблющимися последовательностями. Например, [1, 7, 4, 9, 2, 5] — это колеблющаяся последовательность, потому что разности (6, -3, 5, -7, 3) чередуются между положительными и отрицательными. В отличие от нее, [1, 4, 7, 2, 5] и [1, 7, 4, 5, 5] не являются колеблющимися последовательностями. Первая не является, потому что первые две разности положительные, а вторая не является, потому что последняя разность равна нулю. Подпоследовательность получается путем удаления некоторых элементов (возможно, нуля) из исходной последовательности с сохранением оставшихся элементов в их первоначальном порядке. Дан целочисленный массив nums, верните длину самой длинной колеблющейся подпоследовательности из nums. Пример:

    
        Input: nums = [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).{}
    

👨‍💻 Алгоритм: 1⃣Для понимания этого подхода создайте два массива для динамического программирования, названных up и down. Эти массивы будут хранить длины наибольших колеблющихся подпоследовательностей, заканчивающихся соответственно восходящим или нисходящим колебанием. 2⃣up[i] относится к длине самой длинной колеблющейся подпоследовательности на данный момент, если рассматривать i-й элемент как последний элемент последовательности, заканчивающейся восходящим колебанием. Аналогично, down[i] относится к длине самой длинной колеблющейся подпоследовательности, если рассматривать i-й элемент как последний элемент последовательности, заканчивающейся нисходящим колебанием. 3⃣up[i] обновляется каждый раз, когда мы находим восходящее колебание, заканчивающееся на i-м элементе. Чтобы найти up[i], необходимо учесть максимальное значение всех предыдущих подпоследовательностей, заканчивающихся нисходящим колебанием, т.е. down[j], для каждого j<i и nums[i]>nums[j]. Аналогично, down[i] обновляется при нахождении нисходящего колебания. 😎 Решение:

    
        class Solution {
    fun islandPerimeter(grid: Array<IntArray>): Int {
        val rows = grid.size
        val cols = grid[0].size
        
        var result = 0
        
        for (r in 0 until rows) {
            for (c in 0 until cols) {
                if (grid[r][c] == 1) {
                    val up = if (r == 0) 0 else grid[r-1][c]
                    val left = if (c == 0) 0 else grid[r][c-1]
                    val down = if (r == rows-1) 0 else grid[r+1][c]
                    val right = if (c == cols-1) 0 else grid[r][c+1]
                    
                    result += 4 - (up + left + right + down)
                }
            }
        }
        
        return result
    }
}{}
    

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

Задача №19. Remove Nth Node From End of List Сложность: medium Учитывая заголовок связанного списка, удалите n-й узел из конца списка и верните его заголовок. Пример:

    
        Input: head = [1,2,3,4,5], n = 2  
Output: [1,2,3,5]  {}
    

👨‍💻 Алгоритм: 1⃣ Создать фиктивный узел (dummyHead), который указывает на head, чтобы упростить удаление узлов, включая первый. 2⃣ Использовать два указателя (slow и fast), перемещая fast на n шагов вперед. 3⃣ Одновременно двигать slow и fast, пока fast не достигнет конца списка, затем удалить n-й узел. 😎 Решение:

    
        class Solution {
    fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
        val dummyHead = ListNode(0).apply { next = head }
        var slow = dummyHead
        var fast = head

        repeat(n) { fast = fast?.next }

        while (fast != null) {
            fast = fast.next
            slow = slow.next!!
        }

        slow.next = slow.next?.next
        return dummyHead.next
    }
}{}
    

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

Задача: 635. Design Log Storage System Сложность: medium Вам дается несколько журналов, где каждый журнал содержит уникальный идентификатор и временную метку. Временная метка - это строка, имеющая следующий формат: Год:Месяц:День:Час:Минута:Секунда, например, 2017:01:01:23:59:59. Все домены - десятичные числа с нулевым добавлением. Реализация класса LogSystem: LogSystem() Инициализирует объект LogSystem. void put(int id, string timestamp) Сохраняет заданный журнал (id, timestamp) в вашей системе хранения. int[] retrieve(string start, string end, string granularity) Возвращает идентификаторы журналов, временные метки которых находятся в диапазоне от start до end включительно. start и end имеют тот же формат, что и timestamp, а granularity означает, насколько точным должен быть диапазон (т. е. с точностью до дня, минуты и т. д.). Например, start = "2017:01:01:23:59:59", end = "2017:01:02:23:59:59", а granularity = "Day" означает, что нам нужно найти журналы в диапазоне от 1 января 2017 года до 2 января 2017 года включительно, а час, минуту и секунду для каждой записи журнала можно игнорировать. Пример:

    
        Input
["LogSystem", "put", "put", "put", "retrieve", "retrieve"]
[[], [1, "2017:01:01:23:59:59"], [2, "2017:01:01:22:59:59"], [3, "2016:01:01:00:00:00"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Year"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Hour"]]
Output
[null, null, null, null, [3, 2, 1], [2, 1]]{}
    

👨‍💻 Алгоритм: 1⃣Инициализация и хранение журналов Реализуйте метод put, который будет сохранять журнал с заданным id и timestamp в системе хранения. 2⃣Формирование диапазона Реализуйте метод retrieve, который будет формировать диапазон временных меток на основе заданного start, end и granularity. 3⃣Фильтрация и возврат результатов Используйте сформированный диапазон для фильтрации журналов и возврата идентификаторов тех журналов, чьи временные метки попадают в этот диапазон. 😎 Решение:

    
        class LogSystem {
    private val logs = mutableListOf<Pair<Int, String>>()
    private val granularity = mapOf(
        "Year" to 4,
        "Month" to 7,
        "Day" to 10,
        "Hour" to 13,
        "Minute" to 16,
        "Second" to 19
    )

    fun put(id: Int, timestamp: String) {
        logs.add(id to timestamp)
    }

    fun retrieve(start: String, end: String, granularity: String): List<Int> {
        val length = this.granularity[granularity]!!
        val start = start.substring(0, length)
        val end = end.substring(0, length)
        return logs.filter { (id, timestamp) ->
            val ts = timestamp.substring(0, length)
            start <= ts && ts <= end
        }.map { it.first }
    }
}{}
    

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

Задача: 867. Transpose Matrix Сложность: easy Дан двумерный целочисленный массив matrix, верните его транспонированную матрицу. Транспонированная матрица — это матрица, перевернутая относительно своей главной диагонали, при этом строки и столбцы меняются местами. Пример:

    
        Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[1,4,7],[2,5,8],[3,6,9]]{}
    

👨‍💻 Алгоритм: 1⃣Инициализируйте новую матрицу ans с размерами C x R, где C — количество столбцов в исходной матрице, а R — количество строк. 2⃣Скопируйте каждую запись исходной матрицы в новую матрицу так, чтобы ans[c][r] = matrix[r][c]. 3⃣Верните матрицу ans. 😎 Решение:

    
        class Solution {
    fun transpose(A: Array<IntArray>): Array<IntArray> {
        val R = A.size
        val C = A[0].size
        val ans = Array(C) { IntArray(R) }
        for (r in 0 until R) {
            for (c in 0 until C) {
                ans[c][r] = A[r][c]
            }
        }
        return ans
    }
}{}
    

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

Задача: 821. Shortest Distance to a Character Сложность: easy Дана строка s и символ c, который встречается в s. Верните массив целых чисел answer, где answer.length == s.length, и answer[i] - это расстояние от индекса i до ближайшего появления символа c в строке s. Расстояние между двумя индексами i и j равно abs(i - j), где abs - это функция абсолютного значения. Пример:

    
        Input: s = "loveleetcode", c = "e"
Output: [3,2,1,0,1,0,0,1,2,2,1,0]
Explanation: The character 'e' appears at indices 3, 5, 6, and 11 (0-indexed).
The closest occurrence of 'e' for index 0 is at index 3, so the distance is abs(0 - 3) = 3.
The closest occurrence of 'e' for index 1 is at index 3, so the distance is abs(1 - 3) = 2.
For index 4, there is a tie between the 'e' at index 3 and the 'e' at index 5, but the distance is still the same: abs(4 - 3) == abs(4 - 5) = 1.
The closest occurrence of 'e' for index 8 is at index 6, so the distance is abs(8 - 6) = 2.{}
    

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

    
        class Solution {
    fun shortestToChar(S: String, C: Char): IntArray {
        val ans = IntArray(S.length)
        var prev = -S.length

        for (i in S.indices) {
            if (S[i] == C) {
                prev = i
            }
            ans[i] = i - prev
        }

        prev = 2 * S.length
        for (i in S.length - 1 downTo 0) {
            if (S[i] == C) {
                prev = i
            }
            ans[i] = minOf(ans[i], prev - i)
        }

        return ans
    }
}{}
    

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