Задача: 1037. Valid Boomerang
Сложность: easy

Если задан массив points, где points[i] = [xi, yi] представляет точку на плоскости X-Y, верните true, если эти точки являются бумерангом. Бумеранг - это набор из трех точек, которые отличаются друг от друга и не являются прямой линией.

Пример:

Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false

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

1⃣Проверка уникальности точек:
Убедитесь, что все три точки уникальны. Если любые две точки совпадают, то это не бумеранг.

2⃣Проверка на коллинеарность:
Используйте определитель (или площадь параллелограмма) для проверки, находятся ли три точки на одной прямой. Если площадь параллелограмма, образованного тремя точками, равна нулю, то точки коллинеарны.

3⃣Результат:
Если точки уникальны и не коллинеарны, верните true. В противном случае, верните false.

😎 Решение:

class Solution {
    fun isBoomerang(points: Array<IntArray>): Boolean {
        val (x1, y1) = points[0]
        val (x2, y2) = points[1]
        val (x3, y3) = points[2]
        return (x1 != x2 || y1 != y2) && (x1 != x3 || y1 != y3) && (x2 != x3 || y2 != y3) && (x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) != 0
    }
}

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

Задача: 436. Find Right Interval
Сложность: medium

Дан массив интервалов, где intervals[i] = [starti, endi] и каждый starti уникален.

Правый интервал для интервала i - это интервал j, такой что startj >= endi и startj минимален. Обратите внимание, что i может быть равен j.

Верните массив индексов правых интервалов для каждого интервала i. Если правого интервала для интервала i не существует, то поставьте -1 в индекс i.

Пример:

Input: intervals = [[1,2]]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.

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

1⃣Интуиция за этим подходом такова: если мы будем поддерживать два массива - intervals, который отсортирован по начальным точкам, и endIntervals, который отсортирован по конечным точкам. Когда мы выбираем первый интервал (или, скажем, i-ый интервал) из массива endIntervals, мы можем определить подходящий интервал, удовлетворяющий критериям правого интервала, просматривая интервалы в массиве intervals слева направо, так как массив intervals отсортирован по начальным точкам. Допустим, индекс выбранного элемента из массива intervals окажется j.

2⃣Теперь, когда мы выбираем следующий интервал (скажем, (i+1)-ый интервал) из массива endIntervals, нам не нужно начинать сканирование массива intervals с первого индекса. Вместо этого мы можем начать прямо с индекса j, где мы остановились в последний раз в массиве intervals. Это потому, что конечная точка, соответствующая endIntervals[i+1], больше, чем та, которая соответствует endIntervals[i], и ни один из интервалов из intervals[k], таких что 0 < k < j, не удовлетворяет критериям правого соседа с endIntervals[i], а значит, и с endIntervals[i+1] тоже.

3⃣Если в какой-то момент мы достигнем конца массива, т.е. j = intervals.length, и ни один элемент, удовлетворяющий критериям правого интервала, не будет доступен в массиве intervals, мы ставим -1 в соответствующую запись res. То же самое касается всех оставшихся элементов массива endIntervals, конечные точки которых даже больше, чем у предыдущего интервала. Также мы используем хеш-таблицу hash изначально, чтобы сохранить индексы, соответствующие интервалам, даже после сортировки.

😎 Решение:

class Solution {
    fun findRightInterval(intervals: Array<IntArray>): IntArray {
        val endIntervals = intervals.copyOf()
        val hash = hashMapOf<IntArray, Int>()
        for (i in intervals.indices) {
            hash[intervals[i]] = i
        }
        intervals.sortBy { it[0] }
        endIntervals.sortBy { it[1] }
        var j = 0
        val res = IntArray(intervals.size)
        for (i in endIntervals.indices) {
            while (j < intervals.size && intervals[j][0] < endIntervals[i][1]) {
                j++
            }
            res[hash[endIntervals[i]]!!] = if (j == intervals.size) -1 else hash[intervals[j]]!!
        }
        return res
    }
}

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

Задача: 101. Symmetric Tree
Сложность: easy

Дан корень бинарного дерева. Проверьте, является ли это дерево зеркальным отражением самого себя (то есть симметричным относительно своего центра).

Пример:

Input: root = [1,2,2,3,4,4,3]
Output: true

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

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

2⃣Два дерева являются зеркалами, если их корни равны, и правое поддерево одного — зеркало левого поддерева другого.

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

😎 Решение:

class TreeNode(var value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

class Solution {
    fun isSymmetric(root: TreeNode?): Boolean {
        return isMirror(root, root)
    }

    private fun isMirror(t1: TreeNode?, t2: TreeNode?): Boolean {
        if (t1 == null && t2 == null) {
            return true
        }
        if (t1 == null || t2 == null) {
            return false
        }
        return t1.value == t2.value && isMirror(t1.right, t2.left) && isMirror(t1.left, t2.right)
    }
}

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

Задача: 686. Repeated String Match
Сложность: medium

Даны две строки a и b. Верните минимальное количество повторений строки a, чтобы строка b стала её подстрокой. Если сделать b подстрокой a невозможно, верните -1.

Обратите внимание: строка "abc", повторенная 0 раз, это "", повторенная 1 раз - "abc", повторенная 2 раза - "abcabc".

Пример:

Input: a = "abcd", b = "cdabcdab"
Output: 3
Explanation: We return 3 because by repeating a three times "abcdabcdabcd", b is a substring of it.

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

1⃣Найти минимальное количество повторений строки A, чтобы её длина стала больше или равна длине B. Это значение q = ceil(len(B) / len(A)).

2⃣Проверить, является ли B подстрокой строки A, повторенной q раз. Если да, вернуть q. Иначе, проверить строку A, повторенную (q+1) раз. Если B является подстрокой этой строки, вернуть q+1.

3⃣Если B не является подстрокой ни в одном из случаев, вернуть -1.

😎 Решение:

class Solution {
    fun repeatedStringMatch(A: String, B: String): Int {
        var q = 1
        var S = StringBuilder(A)
        while (S.length < B.length) {
            S.append(A)
            q++
        }
        if (S.indexOf(B) >= 0) {
            return q
        }
        if (S.append(A).indexOf(B) >= 0) {
            return q + 1
        }
        return -1
    }
}

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

Задача: 930. Binary Subarrays With Sum
Сложность: medium

Если задан двоичный массив nums и целочисленная цель, верните количество непустых подмассивов с целью sum. Подмассив - это смежная часть массива.

Пример:

Input: nums = [1,0,1,0,1], goal = 2
Output: 4

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

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

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

3⃣Вернуть счетчик подмассивов.

😎 Решение:

class Solution {
    fun numSubarraysWithSum(nums: IntArray, goal: Int): Int {
        val prefixSumCount = mutableMapOf(0 to 1)
        var currentSum = 0
        var count = 0
        
        for (num in nums) {
            currentSum += num
            count += prefixSumCount.getOrDefault(currentSum - goal, 0)
            prefixSumCount[currentSum] = prefixSumCount.getOrDefault(currentSum, 0) + 1
        }
        
        return count
    }
}

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

Задача: 1160. Find Words That Can Be Formed by Characters
Сложность: easy

Вам дан массив строк words и строка chars.

Строка считается хорошей, если она может быть составлена из символов chars (каждый символ может быть использован только один раз).

Верните сумму длин всех хороших строк в words.

Пример:

Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.

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

1⃣Создайте хеш-таблицу counts, которая будет записывать частоту каждого символа в chars. Инициализируйте переменную ans = 0.

2⃣Итерируйте по каждому слову в words. Создайте хеш-таблицу wordCount, которая будет записывать частоту каждого символа в слове. Установите good = true. Итерируйте по каждому ключу c в wordCount. Пусть freq = wordCount[c]. Если counts[c] < freq, установите good = false и прервите цикл.

3⃣Если good = true, добавьте длину слова к ans. Верните ans.

😎 Решение:

class Solution {
    fun countCharacters(words: Array<String>, chars: String): Int {
        val counts = mutableMapOf<Char, Int>()
        for (c in chars) {
            counts[c] = counts.getOrDefault(c, 0) + 1
        }
        
        var ans = 0
        for (word in words) {
            val wordCount = mutableMapOf<Char, Int>()
            for (c in word) {
                wordCount[c] = wordCount.getOrDefault(c, 0) + 1
            }
            
            var good = true
            for ((c, freq) in wordCount) {
                if (counts.getOrDefault(c, 0) < freq) {
                    good = false
                    break
                }
            }
            
            if (good) {
                ans += word.length
            }
        }
        
        return ans
    }
}

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

Задача: 1062. Longest Repeating Substring
Сложность: medium

Дана строка s. Вернуть длину самой длинной повторяющейся подстроки. Если повторяющаяся подстрока отсутствует, вернуть 0.

Пример:

Input: s = "abcd"
Output: 0
Explanation: There is no repeating substring.

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

1⃣Перемещайте скользящее окно длиной L по строке длиной N.

2⃣Проверьте, находится ли строка в скользящем окне в хэш-наборе уже виденных строк. Если да, то повторяющаяся подстрока находится здесь. Если нет, сохраните строку из скользящего окна в хэш-наборе.

3⃣Очевидный недостаток этого подхода — большое потребление памяти в случае длинных строк.

😎 Решение:

class Solution {
    fun search(L: Int, n: Int, S: String): Int {
        val seen = HashSet<String>()
        for (start in 0..n - L) {
            val tmp = S.substring(start, start + L)
            if (seen.contains(tmp)) return start
            seen.add(tmp)
        }
        return -1
    }

    fun longestRepeatingSubstring(S: String): Int {
        val n = S.length
        var left = 1
        var right = n
        while (left <= right) {
            val L = left + (right - left) / 2
            if (search(L, n, S) != -1) {
                left = L + 1
            } else {
                right = L - 1
            }
        }
        return left - 1
    }
}

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

Задача: 1038. Binary Search Tree to Greater Sum Tree
Сложность: medium

Получив корень двоичного дерева поиска (BST), преобразуйте его в большее дерево таким образом, чтобы каждый ключ исходного BST был заменен на исходный ключ плюс сумма всех ключей, превышающих исходный ключ в BST. Напомним, что двоичное дерево поиска - это дерево, удовлетворяющее следующим ограничениям: левое поддерево узла содержит только узлы с ключами меньше, чем ключ узла. Правое поддерево узла содержит только узлы с ключами больше, чем ключ узла. И левое, и правое поддеревья должны быть двоичными деревьями поиска.

Пример:

Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

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

1⃣Обратный обход in-order:
Пройдите по дереву в порядке "правый, корень, левый" (обратный in-order обход). Это обеспечит посещение узлов в порядке убывания их значений.

2⃣Накопление суммы:
Во время обхода поддерживайте переменную для хранения накопленной суммы. На каждом узле добавляйте значение узла к накопленной сумме и обновляйте значение узла этой накопленной суммой.

3⃣Преобразование узлов:
Преобразуйте значение каждого узла в накопленную сумму.

😎 Решение:

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

class Solution {
    private var sum = 0
    
    fun bstToGst(root: TreeNode?): TreeNode? {
        reverseInorder(root)
        return root
    }
    
    private fun reverseInorder(node: TreeNode?) {
        if (node == null) return
        reverseInorder(node.right)
        sum += node.`val`
        node.`val` = sum
        reverseInorder(node.left)
    }
}

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

Ура, друзья! Изиоффер переходит в публичное бета-тестирование!

🎉 Что нового:
🟢Анализ IT собеседований на основе 4500+ реальных интервью
🟢Вопросы из собеседований с вероятностью встречи
🟢Видео-примеры ответов на вопросы от Senior, Middle, Junior грейдов
🟢Пример лучшего ответа
🟢Задачи из собеседований
🟢Тестовые задания
🟢Примеры собеседований
🟢Фильтрация всего контента по грейдам, компаниям
🟢Тренажер подготовки к собеседованию на основе интервальных повторений и флеш карточек
🟡Тренажер "Реальное собеседование" с сценарием вопросов из реальных собеседований (скоро)
🟢Автоотклики на HeadHunter
🟢Закрытое сообщество easyoffer


💎 Акция в честь открытия для первых 500 покупателей:
🚀 Скидка 50% на PRO тариф на 1 год (15000₽ → 7500₽)

🔥 Акция уже стартовала! 👉 https://easyoffer.ru/pro

Задача: 433. Minimum Genetic Mutation
Сложность: medium

Генетическая строка может быть представлена строкой длиной 8 символов, содержащей символы 'A', 'C', 'G' и 'T'.

Предположим, нам нужно исследовать мутацию от генетической строки startGene до генетической строки endGene, где одна мутация определяется как изменение одного символа в генетической строке.

Например, "AACCGGTT" --> "AACCGGTA" является одной мутацией.
Также существует генетический банк bank, который содержит все допустимые генетические мутации. Генетическая строка должна быть в банке, чтобы считаться допустимой.

Даны две генетические строки startGene и endGene и генетический банк bank, верните минимальное количество мутаций, необходимых для мутации от startGene до endGene. Если такой мутации не существует, верните -1.

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

Пример:

Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1

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

1⃣Инициализируйте очередь и множество seen. Очередь будет использоваться для выполнения BFS, а множество seen будет использоваться для предотвращения повторного посещения одного и того же узла. Изначально в очередь и множество должен быть помещен startGene.

2⃣Выполняйте BFS. На каждом узле, если node == endGene, верните количество шагов, пройденных до этого момента. В противном случае, итеративно заменяйте каждый символ в строке на один из "A", "C", "G", "T" для нахождения соседей. Для каждого соседа, если он еще не был посещен и находится в bank, добавьте его в очередь и в множество seen.

3⃣Если BFS завершился и endGene не был найден, задача невыполнима. Верните -1.

😎 Решение:

import java.util.*

class Solution {
    fun minMutation(start: String, end: String, bank: Array<String>): Int {
        val queue: Queue<String> = LinkedList()
        val seen: MutableSet<String> = HashSet()
        queue.offer(start)
        seen.add(start)
        
        var steps = 0
        while (queue.isNotEmpty()) {
            val nodesInQueue = queue.size
            
            for (j in 0 until nodesInQueue) {
                val node = queue.poll()
                
                if (node == end) {
                    return steps
                }
                
                for (c in "ACGT") {
                    for (i in node.indices) {
                        val neighbor = StringBuilder(node)
                        neighbor[i] = c
                        val neighborStr = neighbor.toString()
                        if (!seen.contains(neighborStr) && bank.contains(neighborStr)) {
                            queue.offer(neighborStr)
                            seen.add(neighborStr)
                        }
                    }
                }
            }
            
            steps++
        }
        
        return -1
    }
}

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

Задача: 561. Array Partition
Сложность: easy

Дан массив целых чисел nums из 2n элементов. Разделите эти числа на n пар (a1, b1), (a2, b2), ..., (an, bn) так, чтобы сумма min(ai, bi) для всех i была максимальной. Верните максимальную сумму.

Пример:

Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) are:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.

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

1⃣Отсортируйте массив nums в неубывающем порядке.

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

3⃣Суммируйте выбранные элементы и верните эту сумму.

😎 Решение:

class Solution {
    fun arrayPairSum(nums: IntArray): Int {
        nums.sort()
        var sum = 0
        for (i in nums.indices step 2) {
            sum += nums[i]
        }
        return sum
    }
}

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

Задача: 43. Multiply Strings
Сложность: hard

Даны два неотрицательных целых числа num1 и num2, представленные в виде строк. Верните произведение num1 и num2, также представленное в виде строки.

Примечание: Вы не должны использовать встроенную библиотеку BigInteger или прямо преобразовывать входные данные в целые числа.

Пример:

Input: num1 = "2", num2 = "3"
Output: "6"

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

1⃣Переверните оба числа. Инициализируйте массив ans с (N+M) нулями. Для каждой цифры в secondNumber:
Инициализируйте переменную carry, первоначально равную 0.
Инициализируйте массив (currentResult), который начинается с некоторого количества нулей, основываясь на позиции цифры в secondNumber.

2⃣Для каждой цифры в firstNumber:
Умножьте цифру из secondNumber на цифру из firstNumber и добавьте предыдущий carry к умножению.
Возьмите остаток от деления умножения на 10, чтобы получить последнюю цифру.
Добавьте последнюю цифру в массив currentResult.
Разделите умножение на 10, чтобы получить новое значение для carry.

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

😎 Решение:

class Solution {
    fun multiply(num1: String, num2: String): String {
        if (num1 == "0" || num2 == "0") {
            return "0"
        }

        val firstNumber = num1.reversed()
        val secondNumber = num2.reversed()

        val N = firstNumber.length + secondNumber.length
        val answer = IntArray(N) { 0 }

        for ((index, digit) in secondNumber.withIndex()) {
            val result = multiplyOneDigit(firstNumber, digit, index)
            addStrings(result, answer)
        }

        while (answer.last() == 0 && answer.size > 1) {
            answer.dropLast(1)
        }

        answer.reverse()
        return answer.joinToString(separator = "") { it.toString() }
    }

    private fun multiplyOneDigit(firstNumber: String, digit2: Char, numZeros: Int): IntArray {
        val result = IntArray(firstNumber.length + numZeros + 1) { 0 }
        var carry = 0

        for (i in 0 until numZeros) {
            result[i] = 0
        }

        for ((i, digit1) in firstNumber.withIndex()) {
            val multiplication = Character.getNumericValue(digit1) * Character.getNumericValue(digit2) + carry
            result[i + numZeros] = multiplication % 10
            carry = multiplication / 10
        }

        if (carry != 0) {
            result[firstNumber.length + numZeros] = carry
        }
        return result
    }

    private fun addStrings(result: IntArray, answer: IntArray) {
        var carry = 0
        for (i in result.indices) {
            val sum = (if (i < answer.size) answer[i] else 0) + result[i] + carry
            if (i < answer.size) {
                answer[i] = sum % 10
            } else {
                answer[i] = sum
            }
            carry = sum / 10
        }
        var i = result.size
        while (carry != 0) {
            val sum = (if (i < answer.size) answer[i] else 0) + carry
            if (i < answer.size) {
                answer[i] = sum % 10
            } else {
                answer[i] = sum
            }
            carry = sum / 10
            i++
        }
    }
}

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

Задача: 1271. Hexspeak
Сложность: easy

Десятичное число можно преобразовать в его шестнадцатеричное представление, сначала преобразовав его в прописную шестнадцатеричную строку, а затем заменив все вхождения цифры '0' на букву 'O', а цифры '1' - на букву 'I'. Такое представление допустимо тогда и только тогда, когда оно состоит только из букв набора {'A', 'B', 'C', 'D', 'E', 'F', 'I', 'O'}. Получив строку num, представляющую десятичное целое число n, верните шестнадцатеричное представление n, если оно допустимо, иначе верните "ERROR".

Пример:

Input: num = "257"
Output: "IOI"

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

1⃣Преобразуйте десятичное число в шестнадцатеричную строку в верхнем регистре.

2⃣Замените все вхождения цифры '0' на букву 'O', а цифры '1' на букву 'I'

3⃣Проверьте, что преобразованная строка содержит только допустимые символы. Если это так, верните строку, иначе верните "ERROR".

😎 Решение:

class Solution {
    fun toHexString(num: String): String {
        val hexStr = num.toLong().toString(16).uppercase().replace('0', 'O').replace('1', 'I')
        for (char in hexStr) {
            if (!"ABCDEFIO".contains(char)) {
                return "ERROR"
            }
        }
        return hexStr
    }
}

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

Задача: 841. Keys and Rooms
Сложность: medium

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

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

Пример:

Input: rooms = [[1],[2],[3],[]]
Output: true
Explanation: 
We visit room 0 and pick up key 1.
We then visit room 1 and pick up key 2.
We then visit room 2 and pick up key 3.
We then visit room 3.
Since we were able to visit every room, we return true.

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

1⃣Создайте массив seen для отслеживания посещенных комнат и стек stack для ключей, которые нужно использовать.

2⃣Поместите ключ от комнаты 0 в стек и отметьте комнату 0 как посещенную.

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

😎 Решение:

class Solution {
    fun canVisitAllRooms(rooms: List<List<Int>>): Boolean {
        val seen = BooleanArray(rooms.size) { false }
        seen[0] = true
        val stack = Stack<Int>()
        stack.push(0)

        while (stack.isNotEmpty()) {
            val node = stack.pop()
            for (nei in rooms[node]) {
                if (!seen[nei]) {
                    seen[nei] = true
                    stack.push(nei)
                }
            }
        }

        return seen.all { it }
    }
}

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

Задача: 212. Word Search II
Сложность: hard

Дана m на n доска символов и список строк words, верните все слова, находящиеся на доске.

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

Пример:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

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

1⃣Постройте структуру Trie из слов в словаре. Trie будет использоваться для процесса сопоставления позже.

2⃣Начните обход доски с каждой ячейки. Если существует слово в словаре, которое начинается с буквы в данной ячейке, начните рекурсивный вызов функции backtracking(cell).

3⃣В функции backtracking(cell) исследуйте соседние ячейки (i.e. neighborCell) вокруг текущей ячейки для следующего рекурсивного вызова backtracking(neighborCell).
На каждом вызове проверяйте, соответствует ли последовательность букв, которую мы прошли до сих пор, какому-либо слову в словаре, используя структуру Trie, построенную в начале.

😎 Решение:

class TrieNode {
    val children = HashMap<Char, TrieNode>()
    var word: String? = null
}

class Solution {
    private lateinit var board: Array<CharArray>
    private val result = ArrayList<String>()

    fun findWords(board: Array<CharArray>, words: Array<String>): List<String> {
        val root = TrieNode()
        for (word in words) {
            var node = root
            for (letter in word) {
                node = node.children.computeIfAbsent(letter) { TrieNode() }
            }
            node.word = word
        }

        this.board = board
        for (row in board.indices) {
            for (col in board[0].indices) {
                if (root.children.containsKey(board[row][col])) {
                    backtracking(row, col, root)
                }
            }
        }

        return result
    }

    private fun backtracking(row: Int, col: Int, parent: TrieNode) {
        val letter = board[row][col]
        val currNode = parent.children[letter] ?: return

        currNode.word?.let {
            result.add(it)
            currNode.word = null
        }

        board[row][col] = '#'

        val rowOffset = intArrayOf(-1, 0, 1, 0)
        val colOffset = intArrayOf(0, 1, 0, -1)
        for (i in 0 until 4) {
            val newRow = row + rowOffset[i]
            val newCol = col + colOffset[i]
            if (newRow in board.indices && newCol in board[0].indices) {
                if (currNode.children.containsKey(board[newRow][newCol])) {
                    backtracking(newRow, newCol, currNode)
                }
            }
        }

        board[row][col] = letter

        if (currNode.children.isEmpty()) {
            parent.children.remove(letter)
        }
    }
}

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

Задача: 142. Linked List Cycle II
Сложность: medium

Дана голова связного списка. Верните узел, с которого начинается цикл. Если цикла нет, верните null.

Цикл в связном списке существует, если есть такой узел в списке, до которого можно добраться снова, последовательно следуя по указателю next. Внутренне переменная pos используется для обозначения индекса узла, к которому подключен указатель next последнего узла (индексация с нуля). Она равна -1, если цикла нет. Обратите внимание, что pos не передается в качестве параметра.

Не модифицируйте связный список.

Пример:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

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

1⃣Инициализируйте узел указателем на голову связного списка и создайте пустое множество nodes_seen для отслеживания посещенных узлов.
Начните обход со связного списка, перемещая узел на один шаг за раз.

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

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

😎 Решение:

class ListNode(var `val`: Int) {
    var next: ListNode? = null
}

class Solution {
    fun detectCycle(head: ListNode?): ListNode? {
        val nodesSeen = mutableSetOf<ListNode>()
        var node = head
        while (node != null) {
            if (node in nodesSeen) {
                return node
            } else {
                nodesSeen.add(node)
                node = node.next
            }
        }
        return null
    }
}

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

Задача: 684. Redundant Connection
Сложность: medium

В этой задаче дерево — это неориентированный граф, который является связным и не содержит циклов.

Вам дан граф, который изначально был деревом с n узлами, пронумерованными от 1 до n, и к которому добавили одно дополнительное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее. Граф представлен массивом edges длины n, где edges[i] = [ai, bi] указывает на то, что существует ребро между узлами ai и bi в графе.

Верните ребро, которое можно удалить, чтобы результирующий граф стал деревом из n узлов. Если существует несколько ответов, верните тот, который встречается последним в исходных данных.
Пример:

Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]

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

1⃣Для каждого ребра (u, v) создайте представление графа с использованием списка смежности. Это позволит легко выполнять обход в глубину (DFS) для проверки соединений между узлами.

2⃣Выполняйте обход в глубину для каждого ребра, временно удаляя его из графа. Проверьте, можно ли соединить узлы u и v с помощью обхода в глубину. Если узлы остаются соединенными, значит, это ребро является дублирующимся.

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

😎 Решение:

class Solution {
    val seen = mutableSetOf<Int>()
    val MAX_EDGE_VAL = 1000

    fun findRedundantConnection(edges: Array<IntArray>): IntArray {
        val graph = Array(MAX_EDGE_VAL + 1) { mutableListOf<Int>() }

        for (edge in edges) {
            seen.clear()
            if (graph[edge[0]].isNotEmpty() && graph[edge[1]].isNotEmpty() && dfs(graph, edge[0], edge[1])) {
                return edge
            }
            graph[edge[0]].add(edge[1])
            graph[edge[1]].add(edge[0])
        }
        return intArrayOf()
    }

    fun dfs(graph: Array<MutableList<Int>>, source: Int, target: Int): Boolean {
        if (!seen.contains(source)) {
            seen.add(source)
            if (source == target) return true
            for (nei in graph[source]) {
                if (dfs(graph, nei, target)) return true
            }
        }
        return false
    }
}

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

Задача: 149. Max Points on a Line
Сложность: hard

Дан массив точек, где points[i] = [xi, yi] представляет точку на плоскости XY. Верните максимальное количество точек, которые лежат на одной прямой.

Пример:

Input: points = [[1,1],[2,2],[3,3]]
Output: 3

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

1⃣Проходим по всем точкам массива. Пусть текущая точка будет points[i]. Создаём хеш-таблицу cnt для подсчёта углов.

2⃣Для каждой точки j, не равной i, рассчитываем арктангенс вектора points[j] - points[i] и добавляем это значение в хеш-таблицу

3⃣Пусть k будет максимальным количеством вхождений какого-либо значения угла в хеш-таблице. Обновляем ответ значением k + 1 (прибавляем 1, потому что точка points[i] также лежит на этой линии, и её нужно включить в ответ).

😎 Решение:

class Solution {
    fun maxPoints(points: Array<IntArray>): Int {
        val n = points.size
        if (n == 1) {
            return 1
        }
        var result = 2
        for (i in 0 until n) {
            val cnt = mutableMapOf<Double, Int>()
            for (j in 0 until n) {
                if (j != i) {
                    val dy = (points[j][1] - points[i][1]).toDouble()
                    val dx = (points[j][0] - points[i][0]).toDouble()
                    val angle = Math.atan2(dy, dx)
                    cnt[angle] = cnt.getOrDefault(angle, 0) + 1
                }
            }
            for ((_, count) in cnt) {
                result = maxOf(result, count + 1)
            }
        }
        return result
    }
}

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

Задача: 148. Sort List
Сложность: medium

Дан указатель на начало связанного списка. Верните список после его сортировки в порядке возрастания.

Пример:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

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

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

2⃣Рекурсивно сортируйте каждый подсписок и объединяйте их в один отсортированный список. Это аналогично задаче слияния двух отсортированных связанных списков.

3⃣Процесс продолжается до тех пор, пока не будет получен исходный список в отсортированном порядке. Например, для связанного списка [10,1,60,30,5] описан процесс сортировки слиянием с использованием подхода сверху вниз. Если у нас есть отсортированные списки list1 = [1,10] и list2 = [5,30,60], следующая анимация иллюстрирует процесс слияния обоих списков в один отсортированный список.

😎 Решение:

class ListNode(var `val`: Int) {
    var next: ListNode? = null
}

class Solution {
    fun sortList(head: ListNode?): ListNode? {
        if (head == null || head.next == null) {
            return head
        }
        val mid = getMid(head)
        val left = sortList(head)
        val right = sortList(mid)
        return merge(left, right)
    }

    private fun merge(list1: ListNode?, list2: ListNode?): ListNode? {
        val dummyHead = ListNode(0)
        var tail = dummyHead
        var list1 = list1
        var list2 = list2
        while (list1 != null && list2 != null) {
            if (list1.`val` < list2.`val`) {
                tail.next = list1
                list1 = list1.next
            } else {
                tail.next = list2
                list2 = list2.next
            }
            tail = tail.next!!
        }
        tail.next = list1 ?: list2
        return dummyHead.next
    }

    private fun getMid(head: ListNode?): ListNode? {
        var midPrev: ListNode? = null
        var slow = head
        var fast = head
        while (fast != null && fast.next != null) {
            midPrev = if (midPrev == null) slow else midPrev.next
            slow = slow.next
            fast = fast.next?.next
        }
        val mid = midPrev?.next
        midPrev?.next = null
        return mid
    }
}

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

Задача: 813. Largest Sum of Averages
Сложность: medium

Вам дан целочисленный массив nums и целое число k. Вы можете разбить массив на не более чем k непустых смежных подмассивов. Оценка разбиения равна сумме средних значений каждого подмассива.

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

Верните максимальную оценку, которую можно достичь среди всех возможных разбиений. Ответы, отличающиеся от фактического ответа не более чем на 10^-6, будут приняты.

Пример:

Input: nums = [9,1,2,3,9], k = 3
Output: 20.00000
Explanation: 
The best choice is to partition nums into [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20.
We could have also partitioned nums into [9, 1], [2], [3, 9], for example.
That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.

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

1⃣Пусть dp(i, k) будет лучшей оценкой для разбиения массива A[i:] на не более чем k частей. Если первая группа, в которую мы разбиваем A[i:], заканчивается перед j, тогда наше разбиение-кандидат имеет оценку average(i, j) + dp(j, k-1), где average(i, j) = (A[i] + A[i+1] + ... + A[j-1]) / (j - i) (деление с плавающей запятой). Мы берем наивысшую оценку из этих вариантов, помня, что разбиение необязательно - dp(i, k) также может быть просто average(i, N).

2⃣В общем случае наша рекурсия выглядит так: dp(i, k) = max(average(i, N), max_{j > i}(average(i, j) + dp(j, k-1))). Мы можем рассчитывать average немного быстрее, используя префиксные суммы. Если P[x+1] = A[0] + A[1] + ... + A[x], тогда average(i, j) = (P[j] - P[i]) / (j - i).

3⃣Наша реализация демонстрирует подход "снизу вверх" для динамического программирования. На шаге k во внешнем цикле, dp[i] представляет собой dp(i, k) из обсуждения выше, и мы рассчитываем следующий слой dp(i, k+1). Завершение второго цикла для i = 0..N-1 означает завершение расчета правильного значения для dp(i, t), а внутренний цикл выполняет расчет max_{j > i}(average(i, j) + dp(j, k)).

😎 Решение:

class Solution {
    fun largestSumOfAverages(A: IntArray, K: Int): Double {
        val P = DoubleArray(A.size + 1)
        for (i in A.indices) {
            P[i + 1] = P[i] + A[i]
        }
        
        fun average(i: Int, j: Int): Double {
            return (P[j] - P[i]) / (j - i)
        }

        val N = A.size
        val dp = DoubleArray(N) { average(it, N) }
        for (k in 0 until K - 1) {
            for (i in 0 until N) {
                for (j in i + 1 until N) {
                    dp[i] = maxOf(dp[i], average(i, j) + dp[j])
                }
            }
        }
        
        return dp[0]
    }
}

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