Задача: 688. Knight Probability in Chessboard
Сложность: medium

На шахматной доске размером n x n конь начинает в клетке (row, column) и пытается сделать ровно k ходов. Строки и столбцы нумеруются с 0, так что верхняя левая клетка — это (0, 0), а нижняя правая — (n - 1, n - 1).

Шахматный конь имеет восемь возможных ходов, как показано ниже. Каждый ход — это два поля в кардинальном направлении, затем одно поле в ортогональном направлении.

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

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

Верните вероятность того, что конь останется на доске после того, как он завершит свои ходы.

Пример:

Input: n = 3, k = 2, row = 0, column = 0
Output: 0.06250
Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board.
From each of those positions, there are also two moves that will keep the knight on the board.
The total probability the knight stays on the board is 0.0625.

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

1⃣Определите возможные направления для ходов коня в directions. Инициализируйте таблицу динамического программирования dp нулями. Установите dp[0][row][column] равным 1, что представляет начальную позицию коня.

2⃣Итерация по ходам от 1 до k. Итерация по строкам от 0 до n−1. Итерация по столбцам от 0 до n−1. Итерация по возможным направлениям: вычислите i' как i минус вертикальный компонент направления. Вычислите j' как j минус горизонтальный компонент направления. Проверьте, находятся ли i' и j' в диапазоне [0, n−1]. Если находятся, добавьте (1/8) * dp[moves−1][i'][j'] к dp[moves][i][j].

3⃣Вычислите общую вероятность, суммируя все значения в dp[k]. Верните общую вероятность.

😎 Решение:

class Solution {
    fun knightProbability(n: Int, k: Int, row: Int, column: Int): Double {
        val directions = arrayOf(
            1 to 2, 1 to -2, -1 to 2, -1 to -2,
            2 to 1, 2 to -1, -2 to 1, -2 to -1
        )
        val dp = Array(k + 1) { Array(n) { DoubleArray(n) } }
        dp[0][row][column] = 1.0

        for (moves in 1..k) {
            for (i in 0 until n) {
                for (j in 0 until n) {
                    for (direction in directions) {
                        val prevI = i - direction.first
                        val prevJ = j - direction.second
                        if (prevI in 0 until n && prevJ in 0 until n) {
                            dp[moves][i][j] += dp[moves - 1][prevI][prevJ] / 8
                        }
                    }
                }
            }
        }

        return dp[k].sumOf { it.sum() }
    }
}

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

Задача: 369. Plus One Linked List
Сложность: hard

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

Цифры хранятся таким образом, что самая значимая цифра находится в начале списка.

Пример:

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

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

1⃣Инициализируйте стражевой узел как ListNode(0) и установите его как новую голову списка: sentinel.next = head. Найдите крайний правый элемент, не равный девяти.

2⃣Увеличьте найденную цифру на единицу и установите все следующие девятки в ноль.

3⃣Верните sentinel, если его значение было установлено на 1, иначе верните head (sentinel.next).

😎 Решение:

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

class Solution {
    fun plusOne(head: ListNode?): ListNode? {
        val sentinel = ListNode(0)
        sentinel.next = head
        var notNine = sentinel

        var current = head
        while (current != null) {
            if (current.`val` != 9) {
                notNine = current
            }
            current = current.next
        }

        notNine.`val` += 1
        notNine = notNine.next

        while (notNine != null) {
            notNine.`val` = 0
            notNine = notNine.next
        }

        return if (sentinel.`val` == 0) sentinel.next else sentinel
    }
}

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

Задача: 501. Find Mode in Binary Search Tree
Сложность: easy

Дано корень бинарного дерева поиска (BST) с дубликатами. Необходимо вернуть все моды (т.е. самые часто встречающиеся элементы) в этом дереве.
Если в дереве более одной моды, верните их в любом порядке.

Предположим, что BST определяется следующим образом:
Левое поддерево узла содержит только узлы с ключами, меньшими или равными ключу этого узла.
Правое поддерево узла содержит только узлы с ключами, большими или равными ключу этого узла.
Оба поддерева также должны быть бинарными деревьями поиска.

Пример:

Input: root = [1,null,2,2]
Output: [2]

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

1⃣Обход дерева
Выполните обход дерева (inorder DFS) с использованием рекурсивной функции dfs, чтобы пройти по всем узлам дерева. На каждом узле добавьте node.val в список values.

2⃣Поиск мод
Инициализируйте переменные maxStreak, currStreak, currNum как 0 и пустой список ans. Пройдите по списку values. Для каждого числа num: если num равно currNum, увеличьте currStreak. Иначе, установите currStreak равным 1, а currNum равным num. Если currStreak больше maxStreak, обновите maxStreak и сбросьте ans. Если currStreak равен maxStreak, добавьте num в ans.

3⃣Возврат результата
Верните список ans.

😎 Решение:

class Solution {
    fun findMode(root: TreeNode?): IntArray {
        val values = mutableListOf<Int>()
        dfs(root, values)
        
        var maxStreak = 0
        var currStreak = 0
        var currNum = 0
        val ans = mutableListOf<Int>()
        
        for (num in values) {
            if (num == currNum) {
                currStreak++
            } else {
                currStreak = 1
                currNum = num
            }
            
            if (currStreak > maxStreak) {
                ans.clear()
                ans.add(num)
                maxStreak = currStreak
            } else if (currStreak == maxStreak) {
                ans.add(num)
            }
        }
        
        return ans.toIntArray()
    }
    
    private fun dfs(node: TreeNode?, values: MutableList<Int>) {
        if (node == null) return
        dfs(node.left, values)
        values.add(node.val)
        dfs(node.right, values)
    }
}

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

Задача: 765. Couples Holding Hands
Сложность: hard

Есть n пар, сидящих на 2n местах, расположенных в ряд, и они хотят держаться за руки.

Люди и места представлены массивом целых чисел row, где row[i] — это ID человека, сидящего на i-м месте. Пары пронумерованы по порядку: первая пара — (0, 1), вторая пара — (2, 3) и так далее, до последней пары — (2n - 2, 2n - 1).

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

Пример:

Input: row = [0,2,1,3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

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

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

2⃣При таком предположении, для какого-то дивана с несчастливыми людьми X и Y, мы либо заменяем Y на партнера X, либо заменяем X на партнера Y. Для каждой из двух возможностей мы можем попробовать оба варианта, используя подход с возвратом.

3⃣Для каждого дивана с двумя возможностями (т.е. оба человека на диване несчастливы) мы попробуем первый вариант, найдем ответ как ans1, затем отменим наш ход и попробуем второй вариант, найдем связанный ответ как ans2, отменим наш ход и затем вернем наименьший ответ.

😎 Решение:

class Solution {
    private var N = 0
    private lateinit var pairs: Array<IntArray>
    
    fun minSwapsCouples(row: IntArray): Int {
        N = row.size / 2
        pairs = Array(N) { IntArray(2) }
        for (i in 0 until N) {
            pairs[i][0] = row[2 * i] / 2
            pairs[i][1] = row[2 * i + 1] / 2
        }
        return solve(0)
    }
    
    private fun swap(a: Int, b: Int, c: Int, d: Int) {
        val t = pairs[a][b]
        pairs[a][b] = pairs[c][d]
        pairs[c][d] = t
    }
    
    private fun solve(i: Int): Int {
        if (i == N) return 0
        val x = pairs[i][0]
        val y = pairs[i][1]
        if (x == y) return solve(i + 1)
        
        var jx = 0
        var kx = 0
        var jy = 0
        var ky = 0
        for (j in i + 1 until N) {
            for (k in 0..1) {
                if (pairs[j][k] == x) { jx = j; kx = k }
                if (pairs[j][k] == y) { jy = j; ky = k }
            }
        }
        
        swap(i, 1, jx, kx)
        val ans1 = 1 + solve(i + 1)
        swap(i, 1, jx, kx)
        
        swap(i, 0, jy, ky)
        val ans2 = 1 + solve(i + 1)
        swap(i, 0, jy, ky)
        
        return minOf(ans1, ans2)
    }
}

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

Задача: 1057. Campus Bikes
Сложность: medium

В городке, изображенном на плоскости X-Y, есть n рабочих и m велосипедов, причем n <= m. Вам дан массив workers длины n, где workers[i] = [xi, yi] - положение i-го рабочего. Вам также дан массив bikes длины m, где bikes[j] = [xj, yj] - позиция j-го велосипеда. Все заданные позиции уникальны. Назначаем велосипед каждому работнику. Среди доступных велосипедов и работников мы выбираем пару (workeri, bikej) с наименьшим манхэттенским расстоянием между ними и назначаем велосипед этому работнику. Если существует несколько пар (workeri, bikej) с одинаковым наименьшим манхэттенским расстоянием, мы выбираем пару с наименьшим индексом работника. Если существует несколько способов сделать это, мы выбираем пару с наименьшим индексом велосипеда. Повторяем этот процесс до тех пор, пока не останется свободных работников. Возвращаем массив answer длины n, где answer[i] - индекс (с индексом 0) велосипеда, на который назначен i-й работник. Манхэттенское расстояние между двумя точками p1 и p2 равно Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.

Пример:

Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: [1,0]

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

1⃣Для каждой пары (работник, велосипед) вычисли Манхэттенское расстояние и сохрани все пары вместе с расстоянием в список.

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

3⃣Заполни и верни массив назначений.

😎 Решение:

fun assignBikes(workers: Array<IntArray>, bikes: Array<IntArray>): IntArray {
    val pairs = mutableListOf<Triple<Int, Int, Int>>()
    
    for (i in workers.indices) {
        for (j in bikes.indices) {
            val distance = Math.abs(workers[i][0] - bikes[j][0]) + Math.abs(workers[i][1] - bikes[j][1])
            pairs.add(Triple(distance, i, j))
        }
    }
    
    pairs.sortWith(compareBy({ it.first }, { it.second }, { it.third }))
    
    val result = IntArray(workers.size) { -1 }
    val bikeTaken = BooleanArray(bikes.size)
    val workerAssigned = BooleanArray(workers.size)
    
    for ((distance, workerIdx, bikeIdx) in pairs) {
        if (!workerAssigned[workerIdx] && !bikeTaken[bikeIdx]) {
            result[workerIdx] = bikeIdx
            bikeTaken[bikeIdx] = true
            workerAssigned[workerIdx] = true
        }
    }
    
    return result
}

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

⚡ Официальный релиз easyoffer 2.0 состоится уже в течение нескольких дней.

Напоминаю, что в честь релиза запускаем акцию.

Первые 500 покупателей получат:

🚀 Скидку 50% на PRO тариф на 1 год
🎁 Подарок ценностью 5000₽ для тех, кто подписан на этот канал

🔔 Подпишитесь на этот канал: https://t.iss.one/+b2fZN17A9OQ3ZmJi
В нем мы опубликуем сообщение о релизе в первую очередь

Задача: 1503. Last Moment Before All Ants Fall Out of a Plank
Сложность: medium

У нас есть деревянная доска длиной n единиц. Некоторые муравьи ходят по доске, каждый муравей движется со скоростью 1 единица в секунду. Некоторые муравьи движутся влево, другие движутся вправо.

Когда два муравья, движущиеся в разных направлениях, встречаются в какой-то точке, они меняют свои направления и продолжают двигаться дальше. Предполагается, что изменение направлений не занимает дополнительного времени.

Когда муравей достигает одного из концов доски в момент времени t, он сразу же падает с доски.

Дано целое число n и два целых массива left и right, обозначающие позиции муравьев, движущихся влево и вправо соответственно. Верните момент, когда последний(е) муравей(и) падает(ют) с доски.

Пример:

Input: n = 4, left = [4,3], right = [0,1]
Output: 4
Explanation: In the image above:
-The ant at index 0 is named A and going to the right.
-The ant at index 1 is named B and going to the right.
-The ant at index 3 is named C and going to the left.
-The ant at index 4 is named D and going to the left.
The last moment when an ant was on the plank is t = 4 seconds. After that, it falls immediately out of the plank. (i.e., We can say that at t = 4.0000000001, there are no ants on the plank).

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

1⃣Инициализируйте переменную ans значением 0.

2⃣Итерация по массиву left и обновление ans значением num, если оно больше текущего значения ans.

3⃣Итерация по массиву right и обновление ans значением n - num, если оно больше текущего значения ans. Верните значение ans.

😎 Решение:

class Solution {
    fun getLastMoment(n: Int, left: IntArray, right: IntArray): Int {
        var ans = 0
        for (num in left) {
            ans = maxOf(ans, num)
        }
        for (num in right) {
            ans = maxOf(ans, n - num)
        }
        return ans
    }
}

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

Задача: 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix
Сложность: hard

Дана бинарная матрица mat размером m x n. За один шаг вы можете выбрать одну ячейку и перевернуть её и всех её четырех соседей, если они существуют (Перевернуть означает изменить 1 на 0 и 0 на 1). Пара ячеек называется соседями, если они имеют общую границу.

Верните минимальное количество шагов, необходимых для преобразования матрицы mat в нулевую матрицу или -1, если это невозможно.

Бинарная матрица - это матрица, в которой все ячейки равны 0 или 1.
Нулевая матрица - это матрица, в которой все ячейки равны 0.

Пример:

Input: mat = [[0,0],[0,1]]
Output: 3
Explanation: One possible solution is to flip (1, 0) then (0, 1) and finally (1, 1) as shown.

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

1⃣Переберите все возможные варианты решений для первой строки матрицы. Каждое решение представляется массивом, где каждый элемент равен 0 или 1, указывая, перевернут ли соответствующий элемент в первой строке. Инициализируйте два бинарных массива для каждой строки: lastState[], содержащий значения предыдущей строки, и changed[], представляющий, были ли значения в текущей строке перевернуты при работе с предыдущей строкой.

2⃣Для каждой строки в матрице используйте следующий шаг для вычисления состояния, инициализированного как changed:
Для каждой позиции j в диапазоне [0, n - 1] текущей строки измените значение state[j] соответственно, если lastState[j] равно 1. Переверните state[j], state[j - 1] и state[j + 1], если они существуют. Увеличьте счетчик переворотов на 1.
Значения, которые будут перевернуты в следующей строке, точно равны lastState, а решение для следующей строки точно равно массиву state. Поэтому установите changed = lastState и lastState = state, затем переходите к следующей строке.

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

😎 Решение:

class Solution {
    private fun better(x: Int, y: Int): Int {
        return if (x < 0 || (y >= 0 && y < x)) y else x
    }

    private fun dfs(mat: Array<IntArray>, operations: MutableList<Int>): Int {
        if (operations.size == mat[0].size) {
            var changed = IntArray(mat[0].size)
            var lastState = operations.toIntArray()
            var maybe = 0
            for (row in mat) {
                val state = changed.clone()
                for (j in row.indices) {
                    state[j] = state[j] xor row[j]
                    if (lastState[j] == 1) {
                        state[j] = state[j] xor 1
                        if (j > 0) {
                            state[j - 1] = state[j - 1] xor 1
                        }
                        if (j + 1 < row.size) {
                            state[j + 1] = state[j + 1] xor 1
                        }
                        maybe++
                    }
                }
                changed = lastState
                lastState = state
            }
            for (x in lastState) {
                if (x != 0) {
                    return -1
                }
            }
            return maybe
        }
        operations.add(0)
        val maybe1 = dfs(mat, operations)
        operations[operations.size - 1] = 1
        val maybe2 = dfs(mat, operations)
        operations.removeAt(operations.size - 1)
        return better(maybe1, maybe2)
    }

    fun minFlips(mat: Array<IntArray>): Int {
        val operations = mutableListOf<Int>()
        return dfs(mat, operations)
    }
}

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

Задача: 127. Word Ladder
Сложность: hard

Секвенция трансформации от слова beginWord к слову endWord с использованием словаря wordList представляет собой последовательность слов beginWord -> s1 -> s2 -> ... -> sk, при которой:

Каждая пара соседних слов отличается ровно одной буквой.
Каждый элемент si для 1 <= i <= k присутствует в wordList. Отметим, что beginWord не обязан быть в wordList.
sk равно endWord.
Для двух слов, beginWord и endWord, и словаря wordList, верните количество слов в кратчайшей секвенции трансформации от beginWord к endWord, или 0, если такая секвенция не существует.

Пример:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

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

1⃣Препроцессинг списка слов: Осуществите препроцессинг заданного списка слов (wordList), чтобы найти все возможные промежуточные состояния слов. Сохраните эти состояния в словаре, где ключом будет промежуточное слово, а значением — список слов, имеющих то же промежуточное состояние.

2⃣Использование очереди для обхода: Поместите в очередь кортеж, содержащий beginWord и число 1, где 1 обозначает уровень узла. Вам нужно вернуть уровень узла endWord, так как он будет представлять длину кратчайшей последовательности преобразования. Используйте словарь посещений, чтобы избежать циклов.

3⃣Поиск кратчайшего пути через BFS (обход в ширину): Пока в очереди есть элементы, получите первый элемент очереди. Для каждого слова определите все промежуточные преобразования и проверьте, не являются ли эти преобразования также преобразованиями других слов из списка. Для каждого найденного слова, которое имеет общее промежуточное состояние с текущим словом, добавьте в очередь пару (слово, уровень + 1), где уровень — это уровень текущего слова. Если вы достигли искомого слова, его уровень покажет длину кратчайшей последовательности преобразования.

😎 Решение:

import java.util.*

class Solution {
    fun ladderLength(beginWord: String, endWord: String, wordList: List<String>): Int {
        if (endWord !in wordList || endWord.isEmpty() || beginWord.isEmpty() || wordList.isEmpty()) {
            return 0
        }

        val L = beginWord.length
        val allComboDict = HashMap<String, MutableList<String>>()
        wordList.forEach { word ->
            for (i in 0 until L) {
                val newWord = word.substring(0, i) + "*" + word.substring(i + 1)
                allComboDict.getOrPut(newWord) { mutableListOf() }.add(word)
            }
        }

        val queue: Deque<Pair<String, Int>> = ArrayDeque()
        queue.add(Pair(beginWord, 1))
        val visited = mutableMapOf(beginWord to true)

        while (queue.isNotEmpty()) {
            val (currentWord, level) = queue.poll()
            for (i in 0 until L) {
                val intermediateWord = currentWord.substring(0, i) + "*" + currentWord.substring(i + 1)
                allComboDict[intermediateWord]?.forEach { word ->
                    if (word == endWord) {
                        return level + 1
                    }
                    if (word !in visited) {
                        visited[word] = true
                        queue.add(Pair(word, level + 1))
                    }
                }
                allComboDict[intermediateWord]?.clear()
            }
        }

        return 0
    }
}

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

Задача: 41. First Missing Positive
Сложность: hard

Дан неотсортированный массив nums.
Найдите наименьшее положительное число, которого нет в массиве.
Алгоритм должен работать за O(n) и использовать O(1) дополнительной памяти.

Пример:

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

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

1⃣Используем циклическую сортировку, чтобы поставить числа в правильные позиции (nums[i] == i + 1).

2⃣Проходим по массиву, если nums[i] != i + 1, то возвращаем i + 1.

3⃣Если все элементы на своих местах, возвращаем n + 1.

😎 Решение:

class Solution {
    fun firstMissingPositive(nums: IntArray): Int {
        val n = nums.size

        for (i in nums.indices) {
            while (nums[i] in 1..n && nums[nums[i] - 1] != nums[i]) {
                nums[nums[i] - 1] = nums[i].also { nums[i] = nums[nums[i] - 1] }
            }
        }

        for (i in nums.indices) {
            if (nums[i] != i + 1) return i + 1
        }

        return n + 1
    }
}

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

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

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