#hard
Задача: 727. Minimum Window Subsequence

Если в строках s1 и s2 нет такого окна, которое покрывало бы все символы в s2, верните пустую строку "". Если таких окон минимальной длины несколько, возвращается окно с самым левым начальным индексом.

Пример:

Input: s1 = "abcdebdde", s2 = "bde"
Output: "bcde"

👨‍💻 Алгоритм:

1⃣Используйте два указателя для определения текущего окна.

2⃣Поддерживайте счетчики для символов в текущем окне и требуемых символов из s2.

3⃣Перемещайте правый указатель, чтобы найти подходящее окно, и левый указатель, чтобы минимизировать его.

😎 Решение:

fun minWindow(s1: String, s2: String): String {
    if (s1.isEmpty() || s2.isEmpty()) {
        return ""
    }

    val dictT = mutableMapOf<Char, Int>()
    for (char in s2) {
        dictT[char] = dictT.getOrDefault(char, 0) + 1
    }

    val required = dictT.size
    var l = 0
    var r = 0
    var formed = 0
    val windowCounts = mutableMapOf<Char, Int>()
    var ans = Int.MAX_VALUE to 0 to 0

    while (r < s1.length) {
        val char = s1[r]
        windowCounts[char] = windowCounts.getOrDefault(char, 0) + 1

        if (dictT.containsKey(char) && windowCounts[char] == dictT[char]) {
            formed++
        }

        while (l <= r && formed == required) {
            val char = s1[l]

            if (r - l + 1 < ans.first) {
                ans = (r - l + 1) to l to r
            }

            windowCounts[char] = windowCounts[char]!! - 1
            if (dictT.containsKey(char) && windowCounts[char]!! < dictT[char]!!) {
                formed--
            }

            l++
        }

        r++
    }

    return if (ans.first == Int.MAX_VALUE) "" else s1.substring(ans.second.first, ans.second.second + 1)
}

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

#hard
Задача: 728. Self Dividing Numbers

Например, 128 является саморазделяющимся числом, потому что 128 % 1 == 0, 128 % 2 == 0 и 128 % 8 == 0. Саморазделяющееся число не может содержать цифру ноль. Если даны два целых числа left и right, верните список всех саморазделяющихся чисел в диапазоне [left, right].

Пример:

Input: left = 1, right = 22
Output: [1,2,3,4,5,6,7,8,9,11,12,15,22]

👨‍💻 Алгоритм:

1⃣Переберите все числа в диапазоне от left до right.

2⃣Для каждого числа проверьте, является ли оно саморазделяющимся: Разделите число на его цифры. Убедитесь, что ни одна цифра не равна нулю и число делится на каждую из своих цифр без остатка.

3⃣Добавьте саморазделяющиеся числа в результативный список и верните его.

😎 Решение:

fun selfDividingNumbers(left: Int, right: Int): List<Int> {
    fun isSelfDividing(num: Int): Boolean {
        var n = num
        while (n > 0) {
            val digit = n % 10
            if (digit == 0 || num % digit != 0) {
                return false
            }
            n /= 10
        }
        return true
    }
    
    val result = mutableListOf<Int>()
    for (num in left..right) {
        if (isSelfDividing(num)) {
            result.add(num)
        }
    }
    return result
}

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

#hard
Задача: 730. Count Different Palindromic Subsequences

Поскольку ответ может быть очень большим, верните его по модулю 109 + 7. Подпоследовательность строки получается путем удаления из нее нуля или более символов. Последовательность является палиндромной, если она равна последовательности, обращенной назад. Две последовательности a1, a2, ... и b1, b2, ... различны, если существует некоторое i, для которого ai != bi.

Пример:

Input: s = "bccb"
Output: 6

👨‍💻 Алгоритм:

1⃣Используйте динамическое программирование для подсчета количества палиндромных подпоследовательностей.

2⃣Введите двумерный массив dp, где dp[i][j] представляет количество палиндромных подпоследовательностей в подстроке от i до j.

3⃣Итерируйте по длине подстрок от 1 до длины строки и обновляйте значения в dp на основе состояния предыдущих подстрок.

😎 Решение:

class Solution {
    fun countPalindromicSubsequences(s: String): Int {
        val MOD = 1_000_000_007
        val n = s.length
        val dp = Array(n) { IntArray(n) }
        
        for (i in 0 until n) {
            dp[i][i] = 1
        }
        
        for (length in 2..n) {
            for (i in 0..(n - length)) {
                val j = i + length - 1
                if (s[i] == s[j]) {
                    var l = i + 1
                    var r = j - 1
                    while (l <= r && s[l] != s[i]) l++
                    while (l <= r && s[r] != s[j]) r--
                    dp[i][j] = if (l > r) {
                        dp[i + 1][j - 1] * 2 + 2
                    } else if (l == r) {
                        dp[i + 1][j - 1] * 2 + 1
                    } else {
                        dp[i + 1][j - 1] * 2 - dp[l + 1][r - 1]
                    }
                } else {
                    dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]
                }
                dp[i][j] = (dp[i][j] + MOD) % MOD
            }
        }
        
        return dp[0][n - 1]
    }
}

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

#hard
Задача: 732. My Calendar III

k-бронирование происходит, когда k событий имеют некоторое непустое пересечение (т.е, дано некоторое время, общее для всех k событий). Даны некоторые события [startTime, endTime), после каждого данного события верните целое число k, представляющее максимальное k-бронирование между всеми предыдущими событиями. Реализация класса MyCalendarThree: MyCalendarThree() Инициализирует объект. int book(int startTime, int endTime) Возвращает целое число k, представляющее наибольшее целое число, при котором в календаре существует k-бронирование.

Пример:

Input
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, 1, 1, 2, 3, 3, 3]

👨‍💻 Алгоритм:

1⃣Создайте два словаря для хранения изменений времени бронирования: один для начала событий, другой для конца событий.

2⃣Для каждого нового события обновите словари начала и конца событий.

3⃣Поддерживайте текущее количество активных бронирований и обновляйте максимальное количество активных бронирований по мере добавления новых событий.

😎 Решение:

class MyCalendarThree {
    private val events = mutableMapOf<Int, Int>()
    
    fun book(startTime: Int, endTime: Int): Int {
        events[startTime] = events.getOrDefault(startTime, 0) + 1
        events[endTime] = events.getOrDefault(endTime, 0) - 1
        
        var active = 0
        var maxActive = 0
        for (time in events.keys.sorted()) {
            active += events[time]!!
            maxActive = maxOf(maxActive, active)
        }
        
        return maxActive
    }
}

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

#hard
Задача: 736. Parse Lisp Expression

Нам дан массив asteroids, состоящий из целых чисел, представляющих астероиды в ряд. Для каждого астероида абсолютное значение обозначает его размер, а знак - направление движения (положительное - вправо, отрицательное - влево). Каждый астероид движется с одинаковой скоростью. Определите состояние астероидов после всех столкновений. Если два астероида столкнутся, меньший из них взорвется. Если оба одинакового размера, то взорвутся оба. Два астероида, движущиеся в одном направлении, никогда не встретятся.

Пример:

Input: expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"
Output: 14

👨‍💻 Алгоритм:

1⃣Определите функцию для оценки выражений.

2⃣Используйте рекурсивный подход для обработки различных типов выражений (let, add, mult, и переменных).

3⃣Используйте словарь для отслеживания значений переменных с учетом области видимости.

😎 Решение:

class Solution {
    fun evaluate(expression: String): Int {
        return evaluate(expression, mutableMapOf())
    }
    
    private fun evaluate(expression: String, env: MutableMap<String, Int>): Int {
        if (expression[0] != '(') {
            return expression.toIntOrNull() ?: env[expression]!!
        }
        
        val tokens = tokenize(expression)
        return when (tokens[0]) {
            "let" -> {
                for (i in 1 until tokens.size - 2 step 2) {
                    env[tokens[i]] = evaluate(tokens[i + 1], env)
                }
                evaluate(tokens.last(), env)
            }
            "add" -> evaluate(tokens[1], env) + evaluate(tokens[2], env)
            "mult" -> evaluate(tokens[1], env) * evaluate(tokens[2], env)
            else -> 0
        }
    }
    
    private fun tokenize(expression: String): List<String> {
        val tokens = mutableListOf<String>()
        var token = StringBuilder()
        var parens = 0
        for (char in expression) {
            when (char) {
                '(' -> {
                    parens++
                    if (parens == 1) continue
                }
                ')' -> {
                    parens--
                    if (parens == 0) {
                        tokens.addAll(tokenize(token.toString()))
                        token = StringBuilder()
                        continue
                    }
                }
                ' ' -> {
                    if (parens == 1) {
                        if (token.isNotEmpty()) {
                            tokens.add(token.toString())
                            token = StringBuilder()
                        }
                        continue
                    }
                }
            }
            token.append(char)
        }
        if (token.isNotEmpty()) {
            tokens.add(token.toString())
        }
        return tokens
    }
}

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

#hard
Задача: 741. Cherry Pickup

Вам дана сетка n x n, представляющая поле вишен. Каждая клетка - одно из трех возможных целых чисел. 0 означает, что клетка пуста, и вы можете пройти через нее, 1 означает, что клетка содержит вишню, которую вы можете сорвать и пройти через нее, или -1 означает, что клетка содержит шип, который преграждает вам путь. Верните максимальное количество вишен, которое вы можете собрать, следуя следующим правилам: Начиная с позиции (0, 0) и достигая (n - 1, n - 1) путем перемещения вправо или вниз через допустимые клетки пути (клетки со значением 0 или 1).
После достижения (n - 1, n - 1) вернитесь в (0, 0), двигаясь влево или вверх по клеткам с действительными путями. Проходя через клетку пути, содержащую вишню, вы поднимаете ее, и клетка становится пустой клеткой 0. Если между (0, 0) и (n - 1, n - 1) нет действительного пути, то вишни собрать нельзя.

Пример:

Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5

👨‍💻 Алгоритм:

1⃣Используйте динамическое программирование для подсчета максимального количества вишен, которые можно собрать при движении от (0, 0) до (n - 1, n - 1).

2⃣Примените еще один проход с использованием динамического программирования для движения обратно от (n - 1, n - 1) до (0, 0), чтобы учитывать вишни, собранные на обратном пути.

3⃣Объедините результаты двух проходов, чтобы найти максимальное количество вишен, которые можно собрать.

😎 Решение:

fun cherryPickup(grid: Array<IntArray>): Int {
    val n = grid.size
    val dp = Array(n) { Array(n) { IntArray(2 * n - 1) { Int.MIN_VALUE } } }
    dp[0][0][0] = grid[0][0]

    for (k in 1 until 2 * n - 1) {
        for (i1 in maxOf(0, k - n + 1)..minOf(n - 1, k)) {
            for (i2 in maxOf(0, k - n + 1)..minOf(n - 1, k)) {
                val j1 = k - i1
                val j2 = k - i2
                if (j1 < n && j2 < n && grid[i1][j1] != -1 && grid[i2][j2] != -1) {
                    var maxCherries = Int.MIN_VALUE
                    if (i1 > 0 && i2 > 0) maxCherries = maxOf(maxCherries, dp[i1 - 1][i2 - 1][k - 1])
                    if (i1 > 0) maxCherries = maxOf(maxCherries, dp[i1 - 1][i2][k - 1])
                    if (i2 > 0) maxCherries = maxOf(maxCherries, dp[i1][i2 - 1][k - 1])
                    maxCherries = maxOf(maxCherries, dp[i1][i2][k - 1])
                    if (maxCherries != Int.MIN_VALUE) {
                        dp[i1][i2][k] = maxCherries + grid[i1][j1]
                        if (i1 != i2) dp[i1][i2][k] += grid[i2][j2]
                    }
                }
            }
        }
    }

    return maxOf(0, dp[n - 1][n - 1][2 * n - 1])
}

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

#hard
Задача: 745. Prefix and Suffix Search

Создайте специальный словарь, в котором поиск слов осуществляется по префиксу и суффиксу. Реализуйте класс WordFilter: WordFilter(string[] words) Инициализирует объект со словами в словаре. f(string pref, string suff) Возвращает индекс слова в словаре, которое имеет префикс pref и суффикс suff. Если существует более одного допустимого индекса, возвращается наибольший из них. Если в словаре нет такого слова, возвращается -1.

Пример:

Input: letters = ["c","f","j"], target = "a"
Output: "c"

👨‍💻 Алгоритм:

1⃣Сохраните слова и их индексы в словаре.

2⃣Создайте объединенные ключи, состоящие из префиксов и суффиксов для всех возможных комбинаций.

3⃣Реализуйте функцию поиска, которая ищет наибольший индекс слова по префиксу и суффиксу.

😎 Решение:

class WordFilter(words: Array<String>) {
    private val prefixSuffixMap = mutableMapOf<String, Int>()
    
    init {
        for ((index, word) in words.withIndex()) {
            val length = word.length
            for (prefixLength in 1..length) {
                for (suffixLength in 1..length) {
                    val prefix = word.substring(0, prefixLength)
                    val suffix = word.substring(length - suffixLength)
                    val key = "$prefix#$suffix"
                    prefixSuffixMap[key] = index
                }
            }
        }
    }
    
    fun f(pref: String, suff: String): Int {
        val key = "$pref#$suff"
        return prefixSuffixMap[key] ?: -1
    }
}

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

#hard
Задача: 757. Set Intersection Size At Least Two

Вам дан двумерный целочисленный массив intervals, в котором intervals[i] = [starti, endi] представляет все целые числа от starti до endi включительно. Содержащее множество - это массив nums, в котором каждый интервал из intervals содержит не менее двух целых чисел в nums. Например, если intervals = [[1,3], [3,7], [8,9]], то [1,2,4,7,8,9] и [2,3,4,8,9] - содержащие множества. Верните минимально возможный размер содержащего множества.

Пример:

Input: intervals = [[1,3],[3,7],[8,9]]
Output: 5

👨‍💻 Алгоритм:

1⃣Отсортируйте интервалы по их конечным точкам.

2⃣Инициализируйте пустое множество для хранения чисел.

3⃣Пройдите по каждому интервалу, добавляя необходимые числа в множество так, чтобы каждый интервал содержал не менее двух чисел из этого множества.

😎 Решение:

fun minSetSize(intervals: Array<IntArray>): Int {
    intervals.sortBy { it[1] }
    val nums = mutableListOf<Int>()
    for (interval in intervals) {
        val start = interval[0]
        val end = interval[1]
        if (nums.isEmpty() || nums.last() < start) {
            nums.add(end - 1)
            nums.add(end)
        } else if (nums.last() == end - 1) {
            nums.add(end)
        }
    }
    return nums.size
}

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

#hard
Задача: 759. Employee Free Time

Нам дан список schedule of employees, который представляет собой рабочее время каждого сотрудника. У каждого сотрудника есть список непересекающихся интервалов, и эти интервалы расположены в отсортированном порядке. Верните список конечных интервалов, представляющих общее свободное время положительной длины для всех сотрудников, также в отсортированном порядке. (Хотя мы представляем интервалы в форме [x, y], объекты внутри них являются интервалами, а не списками или массивами. Например, schedule[0][0].start = 1, schedule[0][0].end = 2, а schedule[0][0][0] не определено).Также мы не будем включать в наш ответ интервалы типа [5, 5], так как они имеют нулевую длину.

Пример:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]

👨‍💻 Алгоритм:

1⃣Объедините все интервалы всех сотрудников в один список и отсортируйте его по начальным временам.

2⃣Объедините пересекающиеся интервалы в один.

3⃣Найдите промежутки между объединенными интервалами, представляющие свободное время.

😎 Решение:

class Interval(var start: Int, var end: Int)

fun employeeFreeTime(schedule: List<List<Interval>>): List<Interval> {
    val intervals = mutableListOf<Interval>()
    for (employee in schedule) {
        intervals.addAll(employee)
    }
    
    intervals.sortBy { it.start }
    
    val merged = mutableListOf<Interval>()
    for (interval in intervals) {
        if (merged.isEmpty() || merged.last().end < interval.start) {
            merged.add(interval)
        } else {
            merged.last().end = maxOf(merged.last().end, interval.end)
        }
    }
    
    val freeTime = mutableListOf<Interval>()
    for (i in 1 until merged.size) {
        if (merged[i].start > merged[i - 1].end) {
            freeTime.add(Interval(merged[i - 1].end, merged[i].start))
        }
    }
    
    return freeTime
}

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

#hard
Задача: 761. Special Binary String

Специальные двоичные строки - это двоичные строки, обладающие следующими двумя свойствами: количество 0 равно количеству 1. Каждый префикс двоичной строки имеет не меньше 1, чем 0. Вам дана специальная двоичная строка s. Ход состоит в выборе двух последовательных, непустых специальных подстрок s и их обмене. Две строки являются последовательными, если последний символ первой строки находится ровно на один индекс раньше первого символа второй строки. Верните лексикографически наибольшую результирующую строку, возможную после применения указанных операций над строкой.

Пример:

Input: s = "11011000"
Output: "11100100"

👨‍💻 Алгоритм:

1⃣Определите, что специальная двоичная строка можно разбить на несколько специальных подстрок.

2⃣Рекурсивно примените к каждой подстроке этот алгоритм, чтобы найти лексикографически наибольшую строку.

3⃣Сортируйте полученные подстроки в лексикографическом порядке по убыванию и объединяйте их.

😎 Решение:

fun makeLargestSpecial(s: String): String {
    var count = 0
    var i = 0
    val substrs = mutableListOf<String>()
    for (j in s.indices) {
        count += if (s[j] == '1') 1 else -1
        if (count == 0) {
            substrs.add("1" + makeLargestSpecial(s.substring(i + 1, j)) + "0")
            i = j + 1
        }
    }
    return substrs.sortedDescending().joinToString("")
}

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

#hard
Задача: 762. Prime Number of Set Bits in Binary Representation

Если даны два целых числа left и right, верните количество чисел в диапазоне [left, right], имеющих простое число битов в двоичном представлении. Напомним, что число битов в двоичном представлении - это количество единиц, присутствующих в числе 1. Например, 21 в двоичном представлении - это 10101, которое имеет 3 бита.

Пример:

Input: left = 10, right = 15
Output: 5

👨‍💻 Алгоритм:

1⃣Создайте функцию для подсчета количества единиц в двоичном представлении числа.

2⃣Создайте функцию для проверки, является ли число простым.

3⃣Пройдите через все числа в диапазоне [left, right] и подсчитайте числа, у которых количество битов в двоичном представлении является простым числом.

😎 Решение:

fun countPrimeSetBits(left: Int, right: Int): Int {
    fun countBits(x: Int): Int {
        return x.toString(2).count { it == '1' }
    }
    
    fun isPrime(x: Int): Boolean {
        if (x < 2) return false
        for (i in 2..Math.sqrt(x.toDouble()).toInt()) {
            if (x % i == 0) return false
        }
        return true
    }
    
    var count = 0
    for (num in left..right) {
        if (isPrime(countBits(num))) {
            count++
        }
    }
    return count
}

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