На easyoffer 2.0 появится:
Тренажер "Реальное собеседование"

🟠 Сценарии вопросов из реального собеседования
🟠Возможность подготовиться к собеседованию в конкретную компанию
🟠Итоговая статистика (прошёл/не прошёл)

Сценарий вопросов взят из реального собеседования. То есть вы тренируетесь на тех вопросах, которые действительно задавались в компании X.

Уже в начале следующей недели стартует краудфандинг кампания, чтобы ускорить разработку easyoffer 2.0. Все кто, поддержал проект на этом этапе смогу получить 1 год доступа к сайту по цене месячной подписки. Первые 150 донатеров получать особо-выгодную цену и бонус. Следите за стартом 👉 в этом телеграм канале, в нем информация о старте будет опубликована за 6 часов до официального начала.

Задача: 897. Increasing Order Search Tree
Сложность: easy

Задав корень дерева двоичного поиска, перестройте дерево по порядку так, чтобы самый левый узел дерева теперь был корнем дерева, а каждый узел не имел левого и только одного правого дочернего узла.

Пример:

Input: root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

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

1⃣Выполнить обход дерева в порядке in-order, чтобы получить список узлов.

2⃣Перестроить дерево, устанавливая каждый узел из списка как правый дочерний элемент предыдущего узла и устанавливая левые дочерние элементы в null.

3⃣Вернуть новый корень дерева (первый элемент списка).

😎 Решение:

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

fun increasingBST(root: TreeNode?): TreeNode? {
    val nodes = mutableListOf<TreeNode>()
    
    fun inorder(node: TreeNode?) {
        if (node == null) return
        inorder(node.left)
        nodes.add(node)
        inorder(node.right)
    }
    
    inorder(root)
    
    for (i in 0 until nodes.size - 1) {
        nodes[i].left = null
        nodes[i].right = nodes[i + 1]
    }
    
    nodes.last().left = null
    nodes.last().right = null
    return nodes.first()

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

Задача: 918. Maximum Sum Circular Subarray
Сложность: medium

Если задан круговой целочисленный массив nums длины n, верните максимально возможную сумму непустого подмассива nums. Круговой массив означает, что конец массива соединяется с его началом. Формально, следующий элемент nums[i] равен nums[(i + 1) % n], а предыдущий элемент nums[i] равен nums[(i - 1 + n) % n]. Подмассив может включать каждый элемент фиксированного буфера nums не более одного раза. Формально, для подмассива nums[i], nums[i + 1], ..., nums[j] не существует i <= k1, k2 <= j, при этом k1 % n == k2 % n.

Пример:

Input: nums = [1,-2,3,-2]
Output: 3

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

1⃣Найти стандартную максимальную сумму подмассива с помощью алгоритма Кадане.

2⃣Найти минимальную сумму подмассива с помощью алгоритма Кадане и вычесть ее из общей суммы массива.

3⃣Вернуть максимум между стандартной максимальной суммой подмассива и общей суммой массива минус минимальную сумму подмассива, если результат не равен 0 (чтобы учесть случай, когда все числа отрицательные).

😎 Решение:

class Solution {
    fun maxSubarraySumCircular(nums: IntArray): Int {
        fun kadane(arr: IntArray): Int {
            var currentSum = arr[0]
            var maxSum = arr[0]
            for (i in 1 until arr.size) {
                currentSum = maxOf(arr[i], currentSum + arr[i])
                maxSum = maxOf(maxSum, currentSum)
            }
            return maxSum
        }

        val maxKadane = kadane(nums)
        val totalSum = nums.sum()
        val minKadane = kadane(nums.map { -it }.toIntArray())

        return maxOf(maxKadane, if (totalSum + minKadane == 0) maxKadane else totalSum + minKadane)
    }
}

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

Задача: 1012. Numbers With Repeated Digits
Сложность: hard

Задав целое число n, верните количество положительных целых чисел в диапазоне [1, n], у которых хотя бы одна цифра повторяется.

Пример:

Input: n = 20
Output: 1

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

1⃣Вычисление всех чисел с уникальными цифрами:
Найдите количество чисел в диапазоне [1, n], у которых все цифры уникальны. Для этого используйте перебор всех чисел и проверку уникальности цифр.

2⃣Вычисление всех чисел в диапазоне [1, n]:
Это значение равно n, поскольку это количество всех чисел от 1 до n включительно.

3⃣Вычисление результата:
Вычтите количество чисел с уникальными цифрами из общего количества чисел, чтобы получить количество чисел с повторяющимися цифрами.

😎 Решение:

class Solution {
    fun numDupDigitsAtMostN(n: Int): Int {
        fun countUniqueDigitNumbers(x: Int): Int {
            val s = x.toString()
            val n = s.length
            var res = (1 until n).sumBy { 9 * permutation(9, it - 1) }
            val used = mutableSetOf<Int>()
            for (i in s.indices) {
                for (j in (if (i == 0) 1 else 0) until (s[i] - '0')) {
                    if (!used.contains(j)) {
                        res += permutation(9 - i, n - i - 1)
                    }
                }
                if (used.contains(s[i] - '0' - '0')) {
                    break
                }
                used.add(s[i] - '0' - '0')
            }
            if (used.size == n) res += 1
            return res
        }

        fun permutation(m: Int, n: Int): Int {
            return if (n == 0) 1 else permutation(m, n - 1) * (m - n + 1)
        }

        return n - countUniqueDigitNumbers(n)
    }
}

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

Задача: 422. Valid Word Square
Сложность: easy

Дан массив строк words, верните true, если он образует правильный квадрат слов.

Последовательность строк образует правильный квадрат слов, если k-я строка и k-й столбец читаются одинаково, где 0 <= k < max(numRows, numColumns).

Пример:

Input: words = ["abcd","bnrt","crmy","dtye"]
Output: true
Explanation:
The 1st row and 1st column both read "abcd".
The 2nd row and 2nd column both read "bnrt".
The 3rd row and 3rd column both read "crmy".
The 4th row and 4th column both read "dtye".
Therefore, it is a valid word square.

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

1⃣Инициализируйте переменные: cols для максимальной длины слов в массиве, rows для количества строк в массиве words, и пустой массив newWords для хранения новых слов, представленных каждым столбцом.

2⃣Итерация по массиву words, определение максимальной длины слова для cols, проверка, что количество строк равно количеству столбцов. Если условие не выполняется, возвращаем false.

3⃣Для каждого столбца col от 0 до cols - 1, формируем строку newWord из символов на позиции (row, col) для каждой строки. Сохраняем newWord в массиве newWords. В конце, если newWords и words равны, возвращаем true, иначе false.

😎 Решение:

class Solution {
    fun validWordSquare(words: List<String>): Boolean {
        var cols = 0
        val rows = words.size
        val newWords = mutableListOf<String>()
        
        for (word in words) {
            cols = maxOf(cols, word.length)
        }

        if (cols != words[0].length || rows != cols) {
            return false
        }

        for (col in 0 until cols) {
            var newWord = ""
            for (row in 0 until rows) {
                if (col < words[row].length) {
                    newWord += words[row][col]
                }
            }
            newWords.add(newWord)
        }

        return words == newWords
    }
}

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

На easyoffer 2.0 появится:
База тестовых заданий

🟠Тестовые задания для разных грейдов
🟠Фильтрация тестовых заданий по технологиям и компаниям

Когда я только начинал учиться на программиста, я постоянно выдумывал себе задачи для практики и тратил на это много времени. Но только в момент поиска работы я столкнулся с тестовыми заданиями, и понял насколько круто они прокачивают навыки. Нужно было еще на этапе обучения пробовать их делать. Все компании стараются составить тестовое задание "под себя", это дает большой выбор в тематике задач и технологий. На easyoffer 2.0 вы сможете отфильтровать тестовые задания по навыкам/грейдам и найти те, что подходят лично вам для практики.

В течение 1-2 дней я объявлю о краудфандинг кампании, чтобы ускорить разработку easyoffer 2.0. Все кто, поддержал проект на этом этапе смогу получить 1 год доступа к сайту по цене месячной подписки и смогут попасть на закрытое бета-тестирование. А первые 150 донатеров получать особо-выгодную цену и бонус.

🚀 Следите за стартом 👉 в этом телеграм канале, в нем информация о старте будет опубликована за 6 часов до официального начала.

Задача: 856. Score of Parentheses
Сложность: medium

Дана строка s, состоящая из сбалансированных скобок, верните счёт строки.

Счёт сбалансированной строки скобок основывается на следующих правилах:

"()" имеет счёт 1.
AB имеет счёт A + B, где A и B — сбалансированные строки скобок.
(A) имеет счёт 2 * A, где A — сбалансированная строка скобок.

Пример:

Input: s = "()"
Output: 1

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

1⃣Назовём сбалансированную строку примитивной, если её нельзя разделить на две непустые сбалансированные строки.

2⃣Отслеживая баланс (количество открывающих скобок минус количество закрывающих скобок), мы можем разделить строку S на примитивные подстроки S = P_1 + P_2 + ... + P_n. Тогда, по определению, score(S) = score(P_1) + score(P_2) + ... + score(P_n).

3⃣Для каждой примитивной подстроки (S[i], S[i+1], ..., S[k]), если длина строки равна 2, то её счёт равен 1. В противном случае, счёт равен удвоенному счёту подстроки (S[i+1], S[i+2], ..., S[k-1]).

😎 Решение:

class Solution {
    fun scoreOfParentheses(S: String): Int {
        return F(S, 0, S.length)
    }

    private fun F(S: String, i: Int, j: Int): Int {
        var ans = 0
        var bal = 0

        for (k in i until j) {
            bal += if (S[k] == '(') 1 else -1
            if (bal == 0) {
                ans += if (k - i == 1) 1 else 2 * F(S, i + 1, k)
                i = k + 1
            }
        }

        return ans
    }
}

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

Задача: 1100. Find K-Length Substrings With No Repeated Characters
Сложность: medium

Дана строка s и целое число k. Верните количество подстрок в s длиной k, которые не содержат повторяющихся символов.

Пример:

Input: s = "havefunonleetcode", k = 5
Output: 6
Explanation: There are 6 substrings they are: 'havef','avefu','vefun','efuno','etcod','tcode'.

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

1⃣Если k > 26, верните 0, так как не может быть строки длиной более 26 символов с уникальными символами. Для остальных случаев, где k <= 26, проверьте каждую подстроку длиной k на наличие повторяющихся символов.

2⃣Итерация по строке s от индекса 0 до n - k (включительно), где n - длина строки s:
Для каждого индекса i:
Инициализируйте флаг isUnique как true и массив частот размером 26 для подсчета частот каждого символа.
Итерируйте следующие k символов и увеличивайте частоту каждого встреченного символа в массиве частот.
Если частота любого символа становится больше 1, установите isUnique в false и прекратите итерацию.
Если после итерации по k символам флаг isUnique все еще равен true, увеличьте счетчик ответов на 1.

3⃣Верните количество подстрок без повторяющихся символов после итерации по всем индексам от 0 до n - k.

😎 Решение:

class Solution {
    fun numKLenSubstrNoRepeats(s: String, k: Int): Int {
        if (k > 26) return 0
        
        val n = s.length
        var answer = 0
        
        for (i in 0..n - k) {
            val freq = IntArray(26)
            var isUnique = true
            
            for (j in i until i + k) {
                freq[s[j] - 'a']++
                
                if (freq[s[j] - 'a'] > 1) {
                    isUnique = false
                    break
                }
            }
            
            if (isUnique) answer++
        }
        
        return answer
    }
}

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

Задача: 814. Binary Tree Pruning
Сложность: medium

Дан корень бинарного дерева. Верните то же дерево, в котором удалены все поддеревья (данного дерева), не содержащие 1.

Поддерево узла node - это сам узел node и все узлы, являющиеся потомками node.

Пример:

Input: root = [1,null,0,0,1]
Output: [1,null,0,null,1]
Explanation: 
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.

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

1⃣Используем функцию containsOne(node), которая сообщает, содержит ли поддерево в данном узле единицу, и обрезает все поддеревья, не содержащие единицу.

2⃣Например, если поддерево node.left не содержит единицу, то мы должны обрезать его через node.left = null.

3⃣Также нужно проверить родительский узел. Например, если дерево состоит из одного узла 0, то ответом будет пустое дерево.

😎 Решение:

class Solution {
    fun pruneTree(root: TreeNode?): TreeNode? {
        return if (containsOne(root)) root else null
    }

    private fun containsOne(node: TreeNode?): Boolean {
        if (node == null) return false

        val leftContainsOne = containsOne(node.left)
        val rightContainsOne = containsOne(node.right)

        if (!leftContainsOne) node.left = null
        if (!rightContainsOne) node.right = null

        return node.`val` == 1 || leftContainsOne || rightContainsOne
    }
}

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

Задача: 1055. Shortest Way to Form String
Сложность: medium

Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (например, "ace" является подпоследовательностью "abcde", а "aec" - нет). Если даны две строки source и target, верните минимальное количество подпоследовательностей source, чтобы их объединение равнялось target. Если задача невыполнима, верните -1.

Пример:

Input: source = "abc", target = "abcbc"
Output: 2

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

1⃣Используй два указателя для отслеживания текущих позиций в строках source и target.

2⃣Перебирай символы строки source, пока не найдешь совпадающий символ в target.
Если ты прошел всю строку source и не нашел все символы target, увеличь счетчик количества подпоследовательностей и начни снова с начала source.

3⃣Повтори шаги 2 и 3 до тех пор, пока не пройдешь всю строку target.

😎 Решение:

fun minSubsequences(source: String, target: String): Int {
    var subsequencesCount = 0
    var targetIndex = 0

    while (targetIndex < target.length) {
        var sourceIndex = 0
        subsequencesCount++
        val startIndex = targetIndex

        while (sourceIndex < source.length && targetIndex < target.length) {
            if (source[sourceIndex] == target[targetIndex]) {
                targetIndex++
            }
            sourceIndex++
        }

        if (targetIndex == startIndex) {
            return -1
        }
    }

    return subsequencesCount
}

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

Задача: 1255. Maximum Score Words Formed by Letters
Сложность: hard

Даны список слов, список отдельных букв (могут повторяться) и оценка каждого символа. Верните максимальную оценку любого правильного набора слов, образованного с помощью заданных букв (words[i] не может быть использовано два или более раз). Не обязательно использовать все символы в буквах, каждая буква может быть использована только один раз. Оценка букв 'a', 'b', 'c', ... , 'z' задаются значениями score[0], score[1], ... , score[25] соответственно.

Пример:

Input: words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
Output: 23

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

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

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

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

😎 Решение:

class Solution {
    fun maxScoreWords(words: Array<String>, letters: CharArray, score: IntArray): Int {
        val letterCount = mutableMapOf<Char, Int>()
        letters.forEach { letterCount[it] = letterCount.getOrDefault(it, 0) + 1 }

        fun wordScore(word: String): Int {
            var total = 0
            for (ch in word) {
                total += score[ch - 'a']
            }
            return total
        }

        fun canFormWord(word: String, letterCount: Map<Char, Int>): Boolean {
            val count = mutableMapOf<Char, Int>()
            for (ch in word) {
                count[ch] = count.getOrDefault(ch, 0) + 1
                if (count[ch]!! > letterCount.getOrDefault(ch, 0)) {
                    return false
                }
            }
            return true
        }

        var maxScore = 0
        val n = words.size
        for (i in 1 until (1 shl n)) {
            var currScore = 0
            val usedLetters = mutableMapOf<Char, Int>()
            var valid = true
            for (j in 0 until n) {
                if (i and (1 shl j) != 0) {
                    val word = words[j]
                    if (canFormWord(word, letterCount)) {
                        currScore += wordScore(word)
                        for (ch in word) {
                            usedLetters[ch] = usedLetters.getOrDefault(ch, 0) + 1
                        }
                    } else {
                        valid = false
                        break
                    }
                }
            }
            if (valid) {
                maxScore = maxOf(maxScore, currScore)
            }
        }

        return maxScore
    }
}

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

Задача: 846. Hand of Straights
Сложность: medium

У Алисы есть некоторое количество карт, и она хочет переставить карты в группы так, чтобы каждая группа была размером groupSize и состояла из groupSize последовательных карт.

Дан целочисленный массив hand, где hand[i] — это значение, написанное на i-й карте, и целое число groupSize. Верните true, если она может переставить карты, или false в противном случае.

Пример:

Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output: true
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]

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

1⃣Проверьте, делится ли длина массива hand на groupSize. Если нет, верните false.

2⃣Создайте карту cardCount для хранения количества каждой карты в массиве hand.

3⃣Итерируйте по массиву hand и обновляйте карту cardCount. Затем итерируйте снова для создания групп:
Найдите начальную карту startCard для потенциальной последовательности, уменьшая startCard, пока не найдёте карту, которая отсутствует в карте cardCount.
Попробуйте сформировать последовательность из groupSize карт, начиная с startCard. Если какая-либо карта в потенциальной последовательности отсутствует в карте cardCount, верните false.
Если последовательность можно сформировать, уменьшите количество каждой карты в последовательности в карте cardCount.

😎 Решение:

class Solution {
    fun isNStraightHand(hand: IntArray, groupSize: Int): Boolean {
        if (hand.size % groupSize != 0) {
            return false
        }

        val cardCount = hand.groupingBy { it }.eachCount().toMutableMap()
        val sortedHand = hand.sorted()

        for (card in sortedHand) {
            if (cardCount[card] == 0) continue

            for (nextCard in card until card + groupSize) {
                if (cardCount[nextCard] ?: 0 == 0) return false
                cardCount[nextCard] = cardCount[nextCard]!! - 1
            }
        }

        return true
    }
}

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

Задача: 1358. Number of Substrings Containing All Three Characters
Сложность: medium

Дана строка s, состоящая только из символов a, b и c.

Верните количество подстрок, содержащих хотя бы одно вхождение всех этих символов a, b и c.

Пример:

Input: s = "abc"
Output: 1

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

1⃣Инициализация указателей и счетчиков:
Создайте три указателя i, j, и count для отслеживания текущего положения в строке и подсчета подстрок. Используйте словарь для подсчета вхождений символов a, b, и c.

2⃣Расширение окна:
Перемещайте правый указатель j по строке и увеличивайте счетчики символов в словаре. Как только все три символа (a, b, и c) присутствуют в текущем окне, начинайте уменьшать левый указатель i.

3⃣Уменьшение окна и подсчет подстрок:
Для каждого сдвига i вправо, проверяйте наличие всех символов в текущем окне. Если все символы присутствуют, добавьте количество подстрок, заканчивающихся в позиции j, к общему счету. Сдвигайте i вправо до тех пор, пока условие выполнения не нарушится.
Верните итоговое количество подстрок.

😎 Решение:

class Solution {
    fun numberOfSubstrings(s: String): Int {
        val charCount = mutableMapOf('a' to 0, 'b' to 0, 'c' to 0)
        var count = 0
        var i = 0
        
        for (j in s.indices) {
            charCount[s[j]] = charCount.getOrDefault(s[j], 0) + 1
            
            while (charCount['a']!! > 0 && charCount['b']!! > 0 && charCount['c']!! > 0) {
                count += s.length - j
                charCount[s[i]] = charCount[s[i]]!! - 1
                i++
            }
        }
        
        return count
    }
}

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

Задача: 73. Set Matrix Zeroes
Сложность: medium

Дана матрица размером m×n, состоящая из целых чисел. Если элемент матрицы равен 0, установите в 0 все элементы его строки и столбца.

Необходимо выполнить это действие на месте, не используя дополнительное пространство для другой матрицы.

Пример:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

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

1⃣Мы перебираем матрицу и отмечаем первую ячейку строки i и первую ячейку столбца j, если условие в приведенном выше псевдокоде выполняется, т.е. если cell[i][j] == 0.

2⃣Первая ячейка строки и столбца для первой строки и первого столбца совпадают, т.е. cell[0][0]. Поэтому мы используем дополнительную переменную, чтобы узнать, был ли отмечен первый столбец, а cell[0][0] используется для того же для первой строки.

3⃣Теперь мы перебираем исходную матрицу, начиная со второй строки и второго столбца, т.е. с matrix[1][1]. Для каждой ячейки мы проверяем, были ли ранее отмечены строка r или столбец c, проверяя соответствующую первую ячейку строки или первую ячейку столбца. Если любая из них была отмечена, мы устанавливаем значение в ячейке на 0. Обратите внимание, что первая строка и первый столбец служат как row_set и column_set, которые мы использовали в первом подходе. Затем мы проверяем, равна ли cell[0][0] нулю, если это так, мы отмечаем первую строку как ноль. И, наконец, если первый столбец был отмечен, мы делаем все записи в нем нулевыми.

😎 Решение:

class Solution {
    fun setZeroes(matrix: Array<IntArray>) {
        var isCol = false
        val R = matrix.size
        val C = matrix[0].size
        
        for (i in 0 until R) {
            if (matrix[i][0] == 0) {
                isCol = true
            }
            for (j in 1 until C) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0
                    matrix[i][0] = 0
                }
            }
        }
        
        for (i in 1 until R) {
            for (j in 1 until C) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0
                }
            }
        }
        
        if (matrix[0][0] == 0) {
            for (j in 0 until C) {
                matrix[0][j] = 0
            }
        }
        
        if (isCol) {
            for (i in 0 until R) {
                matrix[i][0] = 0
            }
        }
    }
}

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

Задача: 658. Find K Closest Elements
Сложность: easy

Дан отсортированный массив целых чисел arr, два целых числа k и x. Верните k ближайших к x целых чисел в массиве. Результат также должен быть отсортирован в порядке возрастания.

Целое число a ближе к x, чем целое число b, если:

|a - x| < |b - x|, или
|a - x| == |b - x| и a < b.

Пример:

Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]

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

1⃣Бинарный поиск:
Найдите положение числа x или ближайшего к нему числа в массиве arr с помощью бинарного поиска.

2⃣Два указателя:
Используйте два указателя, чтобы расширять окно, которое содержит k ближайших к x элементов. Начните с ближайших элементов и расширяйте окно, сравнивая элементы слева и справа от текущего окна.

3⃣Сортировка:
Отсортируйте итоговый список, если это необходимо (в данном случае это не нужно, так как массив уже отсортирован).

😎 Решение:

class Solution {
    fun findClosestElements(arr: List<Int>, k: Int, x: Int): List<Int> {
        var left = 0
        var right = arr.size - k

        while (left < right) {
            val mid = (left + right) / 2
            if (x - arr[mid] > arr[mid + k] - x) {
                left = mid + 1
            } else {
                right = mid
            }
        }

        return arr.subList(left, left + k)
    }
}

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

Задача: 786. K-th Smallest Prime Fraction
Сложность: medium

Вам дан отсортированный массив целых чисел arr, содержащий 1 и простые числа, где все элементы массива arr уникальны. Также дано целое число k.

Для каждого i и j, где 0 <= i < j < arr.length, мы рассматриваем дробь arr[i] / arr[j].

Верните k-ую наименьшую дробь из рассмотренных. Верните ответ в виде массива из двух целых чисел размера 2, где answer[0] == arr[i] и answer[1] == arr[j].

Пример:

Input: arr = [1,2,3,5], k = 3
Output: [2,5]
Explanation: The fractions to be considered in sorted order are:
1/5, 1/3, 2/5, 1/2, 3/5, and 2/3.
The third fraction is 2/5.

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

1⃣Инициализируйте пустую приоритетную очередь pq для хранения пар дробей и соответствующих им индексов. Итеративно пройдите по входному массиву arr, используя переменную цикла i. Для каждого элемента arr[i] вычислите дробь, образованную делением его на наибольший элемент в массиве (arr[arr.size() - 1]). Поместите пару, состоящую из отрицательного значения дроби (-1.0 * arr[i] / arr[arr.size() - 1]) и соответствующих индексов (i для числителя и arr.size() - 1 для знаменателя), в приоритетную очередь pq. Приоритетная очередь pq теперь содержит все дроби, образованные делением каждого элемента на наибольший элемент в массиве, отсортированные в порядке возрастания значений дробей.

2⃣Повторите следующие шаги k - 1 раз: удалите верхний элемент (наименьшую дробь) из приоритетной очереди pq и сохраните его индексы в переменной cur. Уменьшите индекс знаменателя (cur[1]--). Вычислите новую дробь, образованную делением числителя в cur[0] на уменьшенный знаменатель (arr[cur[1]]). Поместите новое значение дроби (-1.0 * arr[cur[0]] / arr[cur[1]]) и соответствующие индексы (cur[0] для числителя и cur[1] для знаменателя) в приоритетную очередь pq. После k - 1 итераций верхний элемент приоритетной очереди pq будет k-й наименьшей дробью.

3⃣Извлеките индексы числителя и знаменателя из верхнего элемента приоритетной очереди и сохраните их в result. Верните массив, содержащий значения числителя (arr[result[0]]) и знаменателя (arr[result[1]]), соответствующие k-й наименьшей дроби.

😎 Решение:

import java.util.PriorityQueue

class Solution {
    fun kthSmallestPrimeFraction(arr: IntArray, k: Int): IntArray {
        val pq = PriorityQueue(compareBy<Pair<Double, IntArray>> { it.first })

        for (i in 0 until arr.size - 1) {
            pq.add(Pair(arr[i].toDouble() / arr[arr.size - 1], intArrayOf(i, arr.size - 1)))
        }

        repeat(k - 1) {
            val (_, indices) = pq.poll()
            val (numeratorIndex, denominatorIndex) = indices
            val newDenominatorIndex = denominatorIndex - 1
            if (newDenominatorIndex > numeratorIndex) {
                pq.add(Pair(arr[numeratorIndex].toDouble() / arr[newDenominatorIndex], intArrayOf(numeratorIndex, newDenominatorIndex)))
            }
        }

        val (_, result) = pq.poll()
        return intArrayOf(arr[result[0]], arr[result[1]])
    }
}

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

Задача: 1203. Sort Items by Groups Respecting Dependencies
Сложность: hard

Есть n предметов, каждый из которых принадлежит нулевой или одной из m групп, где group[i] — это группа, к которой принадлежит i-й предмет, и равно -1, если i-й предмет не принадлежит никакой группе. Предметы и группы имеют индексацию с нуля. Группа может не иметь ни одного предмета.

Верните отсортированный список предметов таким образом:
Предметы, принадлежащие одной группе, расположены рядом друг с другом в отсортированном списке.
Существуют некоторые отношения между этими предметами, где beforeItems[i] — это список, содержащий все предметы, которые должны быть перед i-м предметом в отсортированном массиве (слева от i-го предмета).
Верните любое решение, если существует более одного решения, и верните пустой список, если решения не существует.

Пример:

Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
Output: [6,3,4,1,5,2,0,7]

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

1⃣Инициализация и создание графов:
Присвоить уникальные идентификаторы группам для элементов без группы.
Создать два графа: item_graph для элементов и group_graph для групп. Также создать два массива для учета входящих рёбер для элементов и групп.

2⃣Построение графов:
Пройти по массиву beforeItems и добавить зависимости между элементами в item_graph, увеличивая счётчик входящих рёбер.
Если элементы принадлежат разным группам, добавить зависимость между группами в group_graph, увеличивая счётчик входящих рёбер.

3⃣Топологическая сортировка и создание итогового списка:
Выполнить топологическую сортировку для элементов и групп. Если есть цикл, вернуть пустой список.
Создать итоговый список, добавляя отсортированные элементы каждой группы.

😎 Решение:

class Solution {
    fun sortItems(n: Int, m: Int, group: IntArray, beforeItems: List<List<Int>>): IntArray {
        var groupId = m
        for (i in 0 until n) if (group[i] == -1) group[i] = groupId++

        val itemGraph = mutableMapOf<Int, MutableList<Int>>()
        val groupGraph = mutableMapOf<Int, MutableList<Int>>()
        val itemIndegree = IntArray(n)
        val groupIndegree = IntArray(groupId)
        for (i in 0 until n) itemGraph[i] = mutableListOf()
        for (i in 0 until groupId) groupGraph[i] = mutableListOf()

        for (curr in 0 until n) {
            for (prev in beforeItems[curr]) {
                itemGraph[prev]!!.add(curr)
                itemIndegree[curr]++
                if (group[curr] != group[prev]) {
                    groupGraph[group[prev]]!!.add(group[curr])
                    groupIndegree[group[curr]]++
                }
            }
        }

        val itemOrder = topologicalSort(itemGraph, itemIndegree)
        val groupOrder = topologicalSort(groupGraph, groupIndegree)
        if (itemOrder.isEmpty() || groupOrder.isEmpty()) return intArrayOf()

        val orderedGroups = mutableMapOf<Int, MutableList<Int>>()
        for (item in itemOrder) orderedGroups.computeIfAbsent(group[item]) { mutableListOf() }.add(item)

        val answerList = mutableListOf<Int>()
        for (groupIndex in groupOrder) answerList.addAll(orderedGroups.getOrDefault(groupIndex, mutableListOf()))

        return answerList.toIntArray()
    }

    private fun topologicalSort(graph: Map<Int, List<Int>>, indegree: IntArray): List<Int> {
        val visited = mutableListOf<Int>()
        val stack = ArrayDeque<Int>()
        for (key in graph.keys) if (indegree[key] == 0) stack.add(key)

        while (stack.isNotEmpty()) {
            val curr = stack.removeLast()
            visited.add(curr)
            for (next in graph[curr]!!) if (--indegree[next] == 0) stack.add(next)
        }

        return if (visited.size == graph.size) visited else emptyList()
    }
}

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

Задача: 1235. Maximum Profit in Job Scheduling
Сложность: hard

У нас есть n заданий, где каждое задание планируется выполнить от startTime[i] до endTime[i], получив прибыль profit[i]. Вам даны массивы startTime, endTime и profit, верните максимальную прибыль, которую вы можете получить, так чтобы в подмножестве не было двух заданий с перекрывающимся временным диапазоном. Если вы выберете задание, которое заканчивается в момент времени X, вы сможете начать другое задание, которое начинается в момент времени X.

Пример:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120

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

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

2⃣Использование динамического программирования с двоичным поиском:
Используем массив dp, где dp[i] будет хранить максимальную прибыль, которую можно получить, рассматривая первые i заданий.

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

😎 Решение:

class Solution {
    fun jobScheduling(startTime: IntArray, endTime: IntArray, profit: IntArray): Int {
        val jobs = startTime.indices.map { Triple(endTime[it], startTime[it], profit[it]) }.sortedBy { it.first }

        val dp = mutableListOf(Pair(0, 0))

        for ((e, s, p) in jobs) {
            val i = dp.binarySearch { if (it.first <= s) -1 else 1 }
            val newProfit = dp[if (i < 0) -i - 2 else i].second + p
            if (newProfit > dp.last().second) {
                dp.add(Pair(e, newProfit))
            }
        }

        return dp.last().second
    }
}

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