Задача: 210. Course Schedule II
Сложность: medium

Всего есть numCourses курсов, которые вы должны пройти, пронумерованных от 0 до numCourses - 1. Вам дан массив prerequisites, где prerequisites[i] = [ai, bi] указывает на то, что вы должны сначала пройти курс bi, если хотите взять курс ai.
Например, пара [0, 1] указывает на то, что для прохождения курса 0 сначала нужно пройти курс 1.
Верните порядок курсов, которые вы должны пройти, чтобы завершить все курсы. Если существует несколько правильных ответов, верните любой из них. Если невозможно завершить все курсы, верните пустой массив.

Пример:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Объяснение: Всего есть 4 курса, которые нужно пройти. Чтобы взять курс 3, вы должны завершить оба курса 1 и 2. Оба курса 1 и 2 должны быть взяты после того, как вы завершите курс 0.
Таким образом, один из правильных порядков курсов — [0,1,2,3]. Другой правильный порядок — [0,2,1,3].

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

1⃣Инициализация и построение графа:
Инициализируйте стек S, который будет содержать топологически отсортированный порядок курсов в нашем графе.
Постройте список смежности, используя пары ребер, указанные на входе. Важно отметить, что пара вида [a, b] указывает на то, что курс b должен быть пройден, чтобы взять курс a. Это подразумевает ребро вида b ➔ a. Учтите это при реализации алгоритма.

2⃣Запуск поиска в глубину (DFS):
Для каждого узла в нашем графе выполните поиск в глубину (DFS), если этот узел еще не был посещен во время DFS другого узла.
Предположим, что мы выполняем поиск в глубину для узла N. Рекурсивно обойдите всех соседей узла N, которые еще не были обработаны.

3⃣Обработка узлов и возвращение результата:
После обработки всех соседей добавьте узел N в стек. Мы используем стек для моделирования необходимого порядка. Когда мы добавляем узел N в стек, все узлы, которые требуют узел N в качестве предшественника (среди других), уже будут в стеке.
После обработки всех узлов просто верните узлы в порядке их присутствия в стеке от вершины до основания.

😎 Решение:

class Solution {
    companion object {
        const val WHITE = 1
        const val GRAY = 2
        const val BLACK = 3
    }

    private var isPossible: Boolean = true
    private lateinit var color: MutableMap<Int, Int>
    private val adjList: MutableMap<Int, MutableList<Int>> = HashMap()
    private val topologicalOrder: MutableList<Int> = ArrayList()

    private fun init(numCourses: Int) {
        isPossible = true
        color = HashMap()
        adjList.clear()
        topologicalOrder.clear()
        for (i in 0 until numCourses) {
            color[i] = WHITE
        }
    }

    private fun dfs(node: Int) {
        if (!isPossible) return
        color[node] = GRAY
        for (neighbor in adjList.getOrDefault(node, mutableListOf())) {
            when (color[neighbor]) {
                WHITE -> dfs(neighbor)
                GRAY -> isPossible = false
            }
        }
        color[node] = BLACK
        topologicalOrder.add(node)
    }

    fun findOrder(numCourses: Int, prerequisites: Array<IntArray>): IntArray {
        init(numCourses)
        for (prerequisite in prerequisites) {
            val (dest, src) = prerequisite
            adjList.computeIfAbsent(src) { mutableListOf() }.add(dest)
        }
        for (i in 0 until numCourses) {
            if (color[i] == WHITE) {
                dfs(i)
            }
        }
        return if (isPossible) {
            val order = IntArray(numCourses)
            for (i in 0 until numCourses) {
                order[i] = topologicalOrder[numCourses - i - 1]
            }
            order
        } else {
            intArrayOf()
        }
    }
}

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

Задача: 1053. Previous Permutation With One Swap
Сложность: medium

Учитывая массив целых положительных чисел arr (не обязательно различных), верните лексикографически наибольшую перестановку, которая меньше arr и может быть сделана ровно с одной подстановкой. Если это невозможно, то верните тот же массив. Обратите внимание, что перестановка меняет местами два числа arr[i] и arr[j].

Пример:

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

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

1⃣Определи общее количество покупателей, которые удовлетворены в минуты, когда владелец магазина не ворчлив.

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

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

😎 Решение:

fun prevPermOpt1(arr: IntArray): IntArray {
    val n = arr.size
    var i = n - 2
    while (i >= 0 && arr[i] <= arr[i + 1]) {
        i--
    }
    if (i == -1) return arr
    
    var j = n - 1
    while (arr[j] >= arr[i] || (j < n - 1 && arr[j] == arr[j + 1])) {
        j--
    }
    
    val temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
    
    return arr
}

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

Задача: 523. Continuous Subarray Sum
Сложность: medium

Дан целочисленный массив nums и целое число k. Верните true, если в nums есть хорошая подмассив, или false в противном случае.

Хороший подмассив — это подмассив, который:

имеет длину не менее двух, и
сумма элементов подмассива является кратной k.
Учтите:

Подмассив — это непрерывная часть массива.
Целое число x является кратным k, если существует целое число n такое, что x = n * k. Число 0 всегда является кратным k.

Пример:

Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.

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

1⃣Инициализируйте целое число prefixMod = 0 и хеш-таблицу modSeen. Инициализируйте modSeen[0] значением -1, чтобы учесть начальное значение prefixMod.

2⃣Итеративно пройдите по всем элементам массива nums.

3⃣Вычислите prefixMod как (prefixMod + nums[i]) % k. Если prefixMod существует в хеш-таблице: Если размер самого длинного подмассива с модулем k составляет не менее 2, верните true. Если prefixMod не существует в хеш-таблице: Установите modSeen[prefixMod] = i. Если после завершения итерации не найден хороший подмассив, верните false.

😎 Решение:

class Solution {
    fun checkSubarraySum(nums: IntArray, k: Int): Boolean {
        var prefixMod = 0
        val modSeen = mutableMapOf(0 to -1)
        
        for (i in nums.indices) {
            prefixMod = (prefixMod + nums[i]) % k
            
            if (modSeen.containsKey(prefixMod)) {
                if (i - modSeen[prefixMod]!! > 1) {
                    return true
                }
            } else {
                modSeen[prefixMod] = i
            }
        }
        
        return false
    }
}

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

Задача: 594. Longest Harmonious Subsequence
Сложность: Easy

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

Дан целочисленный массив nums, верните длину его самой длинной гармоничной подпоследовательности среди всех возможных подпоследовательностей.

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

Пример:

Input: nums = [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

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

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

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

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

😎 Решение:

class Solution {
    fun findLHS(nums: IntArray): Int {
        val count = mutableMapOf<Int, Int>()
        var res = 0
        
        for (num in nums) {
            count[num] = count.getOrDefault(num, 0) + 1
            if (count.containsKey(num + 1)) {
                res = Math.max(res, count[num]!! + count[num + 1]!!)
            }
            if (count.containsKey(num - 1)) {
                res = Math.max(res, count[num]!! + count[num - 1]!!)
            }
        }
        
        return res
    }
}

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

Задача: 931. Minimum Falling Path Sum
Сложность: medium

Если задан массив целых чисел n x n, верните минимальную сумму любого падающего пути через матрицу. Падающий путь начинается с любого элемента в первой строке и выбирает элемент в следующей строке, который находится либо прямо под ним, либо по диагонали слева/справа. В частности, следующим элементом из позиции (row, col) будет (row + 1, col - 1), (row + 1, col) или (row + 1, col + 1).

Пример:

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

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

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

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

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

😎 Решение:

class Solution {
    fun minFallingPathSum(matrix: Array<IntArray>): Int {
        val n = matrix.size
        var dp = matrix[0].clone()
        
        for (i in 1 until n) {
            val newDp = IntArray(n)
            for (j in 0 until n) {
                newDp[j] = matrix[i][j] + minOf(dp[j], if (j > 0) dp[j - 1] else Int.MAX_VALUE, if (j < n - 1) dp[j + 1] else Int.MAX_VALUE)
            }
            dp = newDp
        }
        
        return dp.minOrNull()!!
    }
}

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

Задача: 348. Design Tic-Tac-Toe
Сложность: medium

Предположим, что следующие правила относятся к игре в крестики-нолики на доске размером n x n между двумя игроками:

Ход гарантированно является допустимым и делается на пустом поле.
Как только достигается выигрышное условие, дальнейшие ходы запрещены.
Игрок, который успешно размещает n своих меток в горизонтальном, вертикальном или диагональном ряду, выигрывает игру.
Реализуйте класс TicTacToe:

TicTacToe(int n) Инициализирует объект с размером доски n.
int move(int row, int col, int player) Указывает, что игрок с идентификатором player делает ход в ячейке (row, col) на доске. Ход гарантированно является допустимым, и два игрока ходят по очереди. Возвращает:
0, если после хода победителя нет.
1, если после хода игрок 1 является победителем.
2, если после хода игрок 2 является победителем.

Пример:

Input
["TicTacToe", "move", "move", "move", "move", "move", "move", "move"]
[[3], [0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]]
Output
[null, 0, 0, 0, 0, 0, 0, 1]

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

1⃣Инициализация:
Создайте массивы rows и cols для отслеживания количества маркеров в каждой строке и столбце соответственно.
Создайте переменные diagonal и antiDiagonal для отслеживания количества маркеров на главной и побочной диагоналях соответственно.
Инициализируйте размер доски n.

2⃣Выполнение хода:
Увеличьте счетчики в rows, cols, diagonal и antiDiagonal в зависимости от текущего хода.
Если текущий ход игрока попадает на диагонали, обновите соответствующие переменные diagonal и antiDiagonal.

3⃣Проверка победы:
Проверьте, достиг ли один из счетчиков в rows, cols, diagonal или antiDiagonal значения n (размер доски). Если да, верните идентификатор игрока как победителя.
Если ни одно из условий победы не выполнено, верните 0, что означает отсутствие победителя после текущего хода.

😎 Решение:

class TicTacToe(n: Int) {
    private val rows = IntArray(n)
    private val cols = IntArray(n)
    private var diagonal = 0
    private var antiDiagonal = 0
    private val n = n

    fun move(row: Int, col: Int, player: Int): Int {
        val add = if (player == 1) 1 else -1
        rows[row] += add
        cols[col] += add
        if (row == col) {
            diagonal += add
        }
        if (row + col == n - 1) {
            antiDiagonal += add
        }
        return if (Math.abs(rows[row]) == n || Math.abs(cols[col]) == n || Math.abs(diagonal) == n || Math.abs(antiDiagonal) == n) player else 0
    }
}

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

Задача: 1165. Single-Row Keyboard
Сложность: easy

Есть специальная клавиатура, на которой все клавиши расположены в один ряд.

Дана строка keyboard длиной 26, указывающая на раскладку клавиатуры (индексирована от 0 до 25). Изначально ваш палец находится на индексе 0. Чтобы напечатать символ, нужно переместить палец на индекс нужного символа. Время, затраченное на перемещение пальца с индекса i на индекс j, равно |i - j|.

Вам нужно напечатать строку word. Напишите функцию для расчета времени, необходимого для её набора одним пальцем.

Пример:

Input: keyboard = "abcdefghijklmnopqrstuvwxyz", word = "cba"
Output: 4
Explanation: The index moves from 0 to 2 to write 'c' then to 1 to write 'b' then to 0 again to write 'a'.
Total time = 2 + 1 + 1 = 4.

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

1⃣Клавиатура содержит уникальные строчные английские буквы, поэтому мы можем сопоставить её с массивом размера 26. Создадим массив размера 26, назовём его keyIndices. Сохраните индекс каждой буквы в этом массиве, проходя по строке keyboard. Инициализируйте переменную result значением 0, которая будет хранить сумму всех расстояний. Объявите переменную prev, которая будет хранить индекс предыдущей клавиши. Поскольку начальная позиция равна 0, инициализируйте её значением 0.

2⃣Проходите по строке word буква за буквой. Для каждой буквы c добавьте ∣prev−indexOf(c)∣ к result. Обновите prev до индекса c.

3⃣Повторите шаги 6 и 7 для всех букв. В конце прохода result будет содержать итоговое время, необходимое для набора слова.

😎 Решение:

class Solution {
    fun calculateTime(keyboard: String, word: String): Int {
        val keyIndices = IntArray(26) { -1 }
        for (i in keyboard.indices) {
            keyIndices[keyboard[i] - 'a'] = i
        }
        
        var prev = 0
        var result = 0
        
        for (c in word) {
            val index = keyIndices[c - 'a']
            result += kotlin.math.abs(prev - index)
            prev = index
        }
        
        return result
    }
}

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

Задача: 520. Detect Capital
Сложность: easy

Мы определяем правильное использование заглавных букв в слове, когда выполняется одно из следующих условий:

Все буквы в этом слове заглавные, как "USA".
Все буквы в этом слове строчные, как "leetcode".
Только первая буква в этом слове заглавная, как "Google".
Дана строка word. Верните true, если использование заглавных букв в ней правильное.

Пример:

Input: word = "USA"
Output: true

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

1⃣Шаблон для первого случая в регулярном выражении: [A-Z]*, где [A-Z] соответствует одной заглавной букве от 'A' до 'Z', а * означает повторение предыдущего шаблона 0 или более раз. Этот шаблон представляет "Все заглавные буквы".

2⃣Шаблон для второго случая в регулярном выражении: [a-z]*, где [a-z] соответствует одной строчной букве от 'a' до 'z'. Этот шаблон представляет "Все строчные буквы". Шаблон для третьего случая в регулярном выражении: [A-Z][a-z]*, где первая буква заглавная, а остальные строчные.

3⃣Объедините эти три шаблона: [A-Z]*|[a-z]*|[A-Z][a-z]*, где | означает "или". Мы можем объединить второй и третий случай, получив . [a-z]*, где . соответствует любому символу. Итоговый шаблон: [A-Z]*|.[a-z]*.

😎 Решение:

class Solution {
    fun detectCapitalUse(word: String): Boolean {
        val pattern = Regex("[A-Z]*|.[a-z]*")
        return pattern.matches(word)
    }
}

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

Задача: 774. Minimize Max Distance to Gas Station
Сложность: hard

Вам дан массив целых чисел stations, который представляет позиции автозаправочных станций на оси x. Вам также дано целое число k.

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

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

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

Пример:

Input: stations = [1,2,3,4,5,6,7,8,9,10], k = 9
Output: 0.50000

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

1⃣Пусть i-й интервал равен deltas[i] = stations[i+1] - stations[i]. Мы хотим найти dp[n+1][k] как рекурсию. Мы можем поставить x автозаправочных станций в интервал n+1 с наилучшим расстоянием deltas[n+1] / (x+1), затем оставшиеся интервалы можно решить с ответом dp[n][k-x]. Ответ — это минимум среди всех x.

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

3⃣Заполняем dp таблицу начиная с базового случая, когда нет добавленных станций. Затем для каждого интервала и количества добавленных станций вычисляем минимальное значение penalty, используя вышеописанную рекурсию. Итоговый ответ будет находиться в dp[n][k], где n — количество интервалов, а k — количество добавляемых станций.

😎 Решение:

class Solution {
    fun minmaxGasDist(stations: IntArray, K: Int): Double {
        val N = stations.size
        val deltas = DoubleArray(N-1)
        for (i in 0 until N-1) {
            deltas[i] = (stations[i+1] - stations[i]).toDouble()
        }

        val dp = Array(N-1) { DoubleArray(K+1) }
        for (i in 0..K) {
            dp[0][i] = deltas[0] / (i+1)
        }

        for (p in 1 until N-1) {
            for (k in 0..K) {
                var bns = Double.MAX_VALUE
                for (x in 0..k) {
                    bns = minOf(bns, maxOf(deltas[p] / (x+1), dp[p-1][k-x]))
                }
                dp[p][k] = bns
            }
        }

        return dp[N-2][K]
    }
}

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

Задача: 850. Rectangle Area II
Сложность: hard

Вам дан двумерный массив прямоугольников, выровненных по осям. Каждый прямоугольник[i] = [xi1, yi1, xi2, yi2] обозначает i-й прямоугольник, где (xi1, yi1) — координаты нижнего левого угла, а (xi2, yi2) — координаты верхнего правого угла.

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

Верните общую площадь. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
Output: 6
Explanation: A total area of 6 is covered by all three rectangles, as illustrated in the picture.
From (1,1) to (2,2), the green and red rectangles overlap.
From (1,0) to (2,3), all three rectangles overlap.

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

1⃣Переназначьте каждую x координату на 0, 1, 2, .... Аналогично, переназначьте все y координаты.

2⃣Теперь мы имеем задачу, которую можно решить методом грубой силы: для каждого прямоугольника с переназначенными координатами (rx1, ry1, rx2, ry2) заполним сетку grid[x][y] = True для rx1 <= x < rx2 и ry1 <= y < ry2.

3⃣Затем каждая ячейка grid[rx][ry] будет представлять площадь (imapx(rx+1) - imapx(rx)) * (imapy(ry+1) - imapy(ry)), где если x был переназначен на rx, то imapx(rx) = x ("обратная карта x для переназначенного x равна x"), аналогично для imapy.

😎 Решение:

class Solution {
    fun rectangleArea(rectangles: Array<IntArray>): Int {
        val N = rectangles.size
        val Xvals = mutableSetOf<Int>()
        val Yvals = mutableSetOf<Int>()

        for (rec in rectangles) {
            Xvals.add(rec[0])
            Xvals.add(rec[2])
            Yvals.add(rec[1])
            Yvals.add(rec[3])
        }

        val imapx = Xvals.sorted()
        val imapy = Yvals.sorted()

        val mapx = imapx.mapIndexed { i, v -> v to i }.toMap()
        val mapy = imapy.mapIndexed { i, v -> v to i }.toMap()

        val grid = Array(imapx.size) { BooleanArray(imapy.size) }
        for (rec in rectangles) {
            for (x in mapx[rec[0]]!! until mapx[rec[2]]!!) {
                for (y in mapy[rec[1]]!! until mapy[rec[3]]!!) {
                    grid[x][y] = true
                }
            }
        }

        var ans: Long = 0
        for (x in grid.indices) {
            for (y in grid[0].indices) {
                if (grid[x][y]) {
                    ans += (imapx[x + 1] - imapx[x]).toLong() * (imapy[y + 1] - imapy[y])
                }
            }
        }

        ans %= 1_000_000_007
        return ans.toInt()
    }
}

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

Задача: 463. Island Perimeter
Сложность: easy

Дан массив размером row x col, представляющий карту, где grid[i][j] = 1 обозначает сушу, а grid[i][j] = 0 обозначает воду.

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

У острова нет "озёр", то есть вода внутри не соединена с водой вокруг острова. Одна ячейка - это квадрат со стороной 1. Сетка прямоугольная, ширина и высота не превышают 100. Определите периметр острова.

Пример:

Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output: 16
Explanation: The perimeter is the 16 yellow stripes in the image above.

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

1⃣Пройти через каждую ячейку сетки и, когда вы находитесь в ячейке с значением 1 (ячейка суши), проверить окружающие (СВЕРХУ, СПРАВА, СНИЗУ, СЛЕВА) ячейки.

2⃣Ячейка суши без каких-либо окружающих ячеек суши будет иметь периметр 4. Вычесть 1 за каждую окружающую ячейку суши.

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

😎 Решение:

class Solution {
    fun islandPerimeter(grid: Array<IntArray>): Int {
        val rows = grid.size
        val cols = grid[0].size
        
        var result = 0
        
        for (r in 0 until rows) {
            for (c in 0 until cols) {
                if (grid[r][c] == 1) {
                    val up = if (r == 0) 0 else grid[r-1][c]
                    val left = if (c == 0) 0 else grid[r][c-1]
                    val down = if (r == rows-1) 0 else grid[r+1][c]
                    val right = if (c == cols-1) 0 else grid[r][c+1]
                    
                    result += 4 - (up + left + right + down)
                }
            }
        }
        
        return result
    }
}

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

Задача: 857. Minimum Cost to Hire K Workers
Сложность: hard

Есть n работников. Вам даны два целочисленных массива: quality и wage, где quality[i] — качество работы i-го работника, а wage[i] — минимальная ожидаемая заработная плата i-го работника.

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

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

Пример:

Input: quality = [10,20,5], wage = [70,50,30], k = 2
Output: 105.00000
Explanation: We pay 70 to 0th worker and 35 to 2nd worker.

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

1⃣Инициализируйте переменные: n для размера массивов quality и wage, totalCost для минимальной стоимости (начальное значение - максимум) и currentTotalQuality для суммы качеств текущих работников. Создайте массив wageToQualityRatio для хранения отношения заработной платы к качеству и качества каждого работника. Рассчитайте и сохраните отношение заработной платы к качеству для каждого работника в wageToQualityRatio. Отсортируйте wageToQualityRatio по возрастанию.

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

3⃣Если размер workers превышает k, удалите работника с наибольшим качеством из workers и обновите currentTotalQuality. Если размер workers равен k, рассчитайте общую стоимость, умножив currentTotalQuality на отношение заработной платы к качеству текущего работника. Обновите totalCost, если рассчитанная стоимость меньше текущей. Верните totalCost.

😎 Решение:

import java.util.PriorityQueue

class Solution {
    fun mincostToHireWorkers(quality: IntArray, wage: IntArray, k: Int): Double {
        val n = quality.size
        var totalCost = Double.MAX_VALUE
        var currentTotalQuality = 0.0
        val wageToQualityRatio = quality.indices.map { wage[it].toDouble() / quality[it] to quality[it] }.sortedBy { it.first }
        val workers = PriorityQueue<Int>(compareByDescending { it })

        wageToQualityRatio.forEach { (ratio, q) ->
            workers.add(q)
            currentTotalQuality += q

            if (workers.size > k) {
                currentTotalQuality -= workers.poll()
            }

            if (workers.size == k) {
                totalCost = minOf(totalCost, currentTotalQuality * ratio)
            }
        }

        return totalCost
    }
}

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

Задача: 764. Largest Plus Sign
Сложность: medium

Вам дано целое число n. У вас есть бинарная сетка размером n x n, в которой все значения изначально равны 1, за исключением некоторых индексов, указанных в массиве mines. Элемент массива mines с индексом i определяется как mines[i] = [xi, yi], где grid[xi][yi] == 0.

Верните порядок самого большого крестообразного знака из 1, выровненного по осям, который содержится в сетке. Если такого знака нет, верните 0.

Крестообразный знак из 1 порядка k имеет некоторый центр grid[r][c] == 1, а также четыре луча длиной k - 1, идущих вверх, вниз, влево и вправо, состоящие из 1. Обратите внимание, что за пределами лучей креста могут быть 0 или 1, проверяется только соответствующая область крестообразного знака на наличие 1.

Пример:

Input: n = 5, mines = [[4,2]]
Output: 2
Explanation: In the above grid, the largest plus sign can only be of order 2. One of them is shown.

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

1⃣Создайте сетку размером n x n, заполненную единицами. Затем используйте массив mines, чтобы установить значения нулей в соответствующих ячейках сетки.

2⃣Для каждой ячейки в сетке создайте четыре дополнительных сетки: left, right, up и down, которые будут хранить длину непрерывных единиц, простирающихся в соответствующем направлении от каждой ячейки.

3⃣Пройдите по всей сетке и для каждой ячейки определите минимальную длину луча среди четырех направлений. Эта минимальная длина будет определять порядок крестообразного знака с центром в данной ячейке. Обновите максимальный порядок крестообразного знака и верните его после завершения обхода всей сетки. Если такого знака нет, верните 0.

😎 Решение:

class Solution {
    fun orderOfLargestPlusSign(N: Int, mines: Array<IntArray>): Int {
        val banned = HashSet<Int>()
        for (mine in mines) {
            banned.add(mine[0] * N + mine[1])
        }
        
        var ans = 0
        for (r in 0 until N) {
            for (c in 0 until N) {
                var k = 0
                while (k <= r && r < N - k && k <= c && c < N - k &&
                      !banned.contains((r - k) * N + c) &&
                      !banned.contains((r + k) * N + c) &&
                      !banned.contains(r * N + c - k) &&
                      !banned.contains(r * N + c + k)) {
                    k++
                }
                ans = maxOf(ans, k)
            }
        }
        return ans
    }
}

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

Задача: 1496. Path Crossing
Сложность: easy

Дана строка path, где path[i] = 'N', 'S', 'E' или 'W', каждая из которых представляет движение на одну единицу на север, юг, восток или запад соответственно. Вы начинаете с точки (0, 0) на 2D плоскости и идете по пути, указанному в path.

Верните true, если путь пересекает сам себя в какой-либо точке, то есть если вы в какой-то момент окажетесь в месте, которое уже посещали ранее. В противном случае верните false.

Пример:

Input: path = "NESWW"
Output: true
Explanation: Notice that the path visits the origin twice.

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

1⃣Инициализация переменных
Создать хэш-карту moves, которая сопоставляет символы 'N', 'S', 'E', 'W' с соответствующими значениями. Инициализировать множество visited с начальной точкой (0, 0). Установить начальные координаты x = 0 и y = 0.

2⃣Проход по строке path
Для каждого символа c в path получить значения (dx, dy) из moves[c]. Обновить координаты: добавить dx к x и dy к y. Проверить, содержится ли текущая точка (x, y) в visited. Если да, вернуть true. Добавить текущую точку (x, y) в visited.

3⃣Возврат результата
Если ни одна точка не пересекалась, вернуть false.

😎 Решение:

class Solution {
    fun isPathCrossing(path: String): Boolean {
        val moves = mapOf('N' to Pair(0, 1), 'S' to Pair(0, -1), 'E' to Pair(1, 0), 'W' to Pair(-1, 0))
        val visited = mutableSetOf(Pair(0, 0))
        var x = 0
        var y = 0

        for (c in path) {
            val (dx, dy) = moves[c]!!
            x += dx
            y += dy
            val point = Pair(x, y)
            if (point in visited) {
                return true
            }
            visited.add(point)
        }

        return false
    }
}

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

Задача: 313. Super Ugly Number
Сложность: medium

Супер некрасивое число — это положительное целое число, простые множители которого находятся в массиве primes.

Дано целое число n и массив целых чисел primes. Верните n-е супер некрасивое число.

Гарантируется, что n-е супер некрасивое число помещается в 32-битное знаковое целое число.

Пример:

Input: n = 12, primes = [2,7,13,19]
Output: 32
Explanation: [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12 super ugly numbers given primes = [2,7,13,19].

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

1⃣Инициализация
Создайте массив ugly_numbers длиной n для хранения супер некрасивых чисел. Создайте массив indices длиной primes для отслеживания позиций в массиве ugly_numbers. Создайте массив next_ugly длиной primes для хранения следующего возможного супер некрасивого числа для каждого простого числа из primes.

2⃣Генерация супер некрасивых чисел
Установите первое значение в ugly_numbers как 1. Повторяйте до тех пор, пока не заполните массив ugly_numbers: Найдите минимальное значение в массиве next_ugly и добавьте его в ugly_numbers. Обновите соответствующий индекс в indices и пересчитайте значение в next_ugly.

3⃣Возврат результата
Верните последнее значение в массиве ugly_numbers, которое будет n-м супер некрасивым числом.

😎 Решение:

class Solution {
    fun nthSuperUglyNumber(n: Int, primes: IntArray): Int {
        val ugly_numbers = mutableListOf(1)
        val indices = IntArray(primes.size)
        val next_ugly = primes.copyOf()
        
        for (count in 1 until n) {
            val next_val = next_ugly.minOrNull() ?: 1
            ugly_numbers.add(next_val)
            
            for (i in primes.indices) {
                if (next_val == next_ugly[i]) {
                    indices[i]++
                    next_ugly[i] = ugly_numbers[indices[i]] * primes[i]
                }
            }
        }
        
        return ugly_numbers.last()
    }
}

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

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

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

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

Например, последовательность слов ["ball", "area", "lead", "lady"] образует квадрат слов, потому что каждое слово читается одинаково как по горизонтали, так и по вертикали.

Пример:

Input: words = ["area","lead","wall","lady","ball"]
Output: [["ball","area","lead","lady"],["wall","area","lead","lady"]]
Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).

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

1⃣Постройте хеш-таблицу из входных слов. Функция buildPrefixHashTable(words) создает хеш-таблицу, где ключами являются префиксы, а значениями - списки слов, начинающихся с этих префиксов.

2⃣При помощи функции getWordsWithPrefix(prefix) осуществляйте запросы к хеш-таблице для получения всех слов, обладающих данным префиксом. Это ускоряет поиск подходящих слов для построения квадрата слов.

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

😎 Решение:

class Solution {
    private var N = 0
    private lateinit var words: Array<String>
    private var prefixHashTable = mutableMapOf<String, MutableList<String>>()

    fun wordSquares(words: Array<String>): List<List<String>> {
        this.words = words
        this.N = words[0].length

        val results = mutableListOf<List<String>>()
        buildPrefixHashTable(words)

        for (word in words) {
            val wordSquares = LinkedList<String>()
            wordSquares.add(word)
            backtracking(1, wordSquares, results)
        }
        return results
    }

    private fun backtracking(step: Int, wordSquares: LinkedList<String>, results: MutableList<List<String>>) {
        if (step == N) {
            results.add(ArrayList(wordSquares))
            return
        }

        val prefix = StringBuilder()
        for (word in wordSquares) {
            prefix.append(word[step])
        }

        for (candidate in getWordsWithPrefix(prefix.toString())) {
            wordSquares.add(candidate)
            backtracking(step + 1, wordSquares, results)
            wordSquares.removeLast()
        }
    }

    private fun buildPrefixHashTable(words: Array<String>) {
        for (word in words) {
            for (i in 1 until N) {
                val prefix = word.substring(0, i)
                prefixHashTable.computeIfAbsent(prefix) { mutableListOf() }.add(word)
            }
        }
    }

    private fun getWordsWithPrefix(prefix: String): List<String> {
        return prefixHashTable.getOrDefault(prefix, emptyList())
    }
}

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

Задача: 730. Count Different Palindromic Subsequences
Сложность: hard

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

Пример:

Input: s = "bccb"
Output: 6

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

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

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

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

😎 Решение:

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

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

Задача: 959. Regions Cut By Slashes
Сложность: medium

n x n сетка состоит из квадратов размером 1 x 1, где каждый квадрат 1 x 1 содержит '/', '', или пустое пространство ' '. Эти символы делят квадрат на смежные области.

Дана сетка grid, представленная в виде строкового массива. Верните количество областей.

Обратите внимание, что обратные слеши экранированы, поэтому '' представлен как '\'.

Пример:

Input: grid = [" /","/ "]
Output: 2

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

1⃣Создайте 4*N*N узлов для каждой ячейки сетки и соедините их в соответствии с описанием.

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

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

😎 Решение:

class DSU(N: Int) {
    private val parent = IntArray(N) { it }
    
    fun find(x: Int): Int {
        if (parent[x] != x) {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }
    
    fun union(x: Int, y: Int) {
        parent[find(x)] = find(y)
    }
}

class Solution {
    fun regionsBySlashes(grid: Array<String>): Int {
        val N = grid.size
        val dsu = DSU(4 * N * N)
        
        for (r in grid.indices) {
            for (c in grid[r].indices) {
                val root = 4 * (r * N + c)
                val valChar = grid[r][c]
                
                if (valChar != '\\') {
                    dsu.union(root + 0, root + 1)
                    dsu.union(root + 2, root + 3)
                }
                if (valChar != '/') {
                    dsu.union(root + 0, root + 2)
                    dsu.union(root + 1, root + 3)
                }
                
                if (r + 1 < N) {
                    dsu.union(root + 3, (root + 4 * N) + 0)
                }
                if (r - 1 >= 0) {
                    dsu.union(root + 0, (root - 4 * N) + 3)
                }
                if (c + 1 < N) {
                    dsu.union(root + 2, (root + 4) + 1)
                }
                if (c - 1 >= 0) {
                    dsu.union(root + 1, (root - 4) + 2)
                }
            }
        }
        
        var ans = 0
        for (x in 0 until 4 * N * N) {
            if (dsu.find(x) == x) {
                ans++
            }
        }
        
        return ans
    }
}

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

Задача: 407. Trapping Rain Water II
Сложность: hard

Задав целочисленную матрицу heightMap размером m x n, представляющую высоту каждой ячейки на двумерной карте рельефа, верните объем воды, который она может задержать после дождя.

Пример:

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

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

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

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

3⃣Повторите процесс, пока все ячейки не будут обработаны.

😎 Решение:

import java.util.PriorityQueue

fun trapRainWater(heightMap: Array<IntArray>): Int {
    val m = heightMap.size
    val n = heightMap[0].size
    if (m <= 2 || n <= 2) return 0
    val visited = Array(m) { BooleanArray(n) }
    val heap = PriorityQueue(compareBy<Pair<Int, Int>> { heightMap[it.first][it.second] })
    for (i in 0 until m) {
        for (j in listOf(0, n-1)) {
            heap.add(i to j)
            visited[i][j] = true
        }
    }
    for (j in 0 until n) {
        for (i in listOf(0, m-1)) {
            heap.add(i to j)
            visited[i][j] = true
        }
    }
    val directions = arrayOf(-1 to 0, 1 to 0, 0 to -1, 0 to 1)
    var water = 0
    while (heap.isNotEmpty()) {
        val (x, y) = heap.poll()
        for ((dx, dy) in directions) {
            val nx = x + dx
            val ny = y + dy
            if (nx in 0 until m && ny in 0 until n && !visited[nx][ny]) {
                visited[nx][ny] = true
                water += maxOf(0, heightMap[x][y] - heightMap[nx][ny])
                heap.add(nx to ny)
                heightMap[nx][ny] = maxOf(heightMap[nx][ny], heightMap[x][y])
            }
        }
    }
    return water
}

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

Задача: 323. Number of Connected Components in an Undirected Graph
Сложность: medium

У вас есть граф из n узлов. Вам дано целое число n и массив edges, где edges[i] = [ai, bi] указывает на наличие ребра между ai и bi в графе.

Верните количество связных компонентов в графе.

Пример:

Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2

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

1⃣Создание списка смежности
Создайте список смежности, такой что adj[v] содержит все смежные вершины вершины v.

2⃣Инициализация посещенных узлов
Инициализируйте хэш-карту или массив visited для отслеживания посещенных вершин.

3⃣Подсчет компонентов
Определите счетчик и инициализируйте его нулем. Итерируйте по каждой вершине в edges, и если вершина еще не была посещена, начните DFS с этой вершины. Добавляйте каждую вершину, посещенную во время DFS, в visited. Каждый раз, когда начинается новый DFS, увеличивайте счетчик на один. В конце, счетчик будет содержать количество связных компонентов в неориентированном графе.

😎 Решение:

class Solution {
    fun countComponents(n: Int, edges: Array<IntArray>): Int {
        val adj = mutableMapOf<Int, MutableList<Int>>()
        for (edge in edges) {
            adj.computeIfAbsent(edge[0]) { mutableListOf() }.add(edge[1])
            adj.computeIfAbsent(edge[1]) { mutableListOf() }.add(edge[0])
        }

        val visited = mutableSetOf<Int>()
        var count = 0

        fun dfs(node: Int) {
            val stack = mutableListOf(node)
            while (stack.isNotEmpty()) {
                val current = stack.removeAt(stack.lastIndex)
                if (visited.add(current)) {
                    adj[current]?.let { stack.addAll(it) }
                }
            }
        }

        for (i in 0 until n) {
            if (visited.add(i)) {
                dfs(i)
                count++
            }
        }

        return count
    }
}

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