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

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

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

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