Задача: 419. Battleships in a Board
Сложность: medium

Если задана матричная доска размером m x n, где каждая клетка - линкор 'X' или пустая '.', верните количество линкоров на доске. Линкоры могут располагаться на доске только горизонтально или вертикально. Другими словами, они могут быть выполнены только в форме 1 x k (1 строка, k столбцов) или k x 1 (k строк, 1 столбец), где k может быть любого размера. Между двумя линкорами есть хотя бы одна горизонтальная или вертикальная клетка (т. е. нет соседних линкоров).

Пример:

Input: board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
Output: 2

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

1⃣Пройдите по каждой клетке матрицы.

2⃣Если текущая клетка содержит 'X' и она не является продолжением линкора (т.е. не имеет 'X' сверху или слева), увеличьте счетчик линкоров.

3⃣Верните итоговый счетчик.

😎 Решение:

fun countBattleships(board: Array<CharArray>): Int {
    val m = board.size
    val n = board[0].size
    var count = 0
    
    for (i in 0 until m) {
        for (j in 0 until n) {
            if (board[i][j] == 'X') {
                if ((i == 0 || board[i-1][j] != 'X') && (j == 0 || board[i][j-1] != 'X')) {
                    count++
                }
            }
        }
    }
    
    return count
}

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

Задача: 1376. Time Needed to Inform All Employees
Сложность: medium

В компании работает n сотрудников, каждому из которых присвоен уникальный идентификатор от 0 до n - 1. Руководитель компании имеет идентификатор headID.

У каждого сотрудника есть один непосредственный начальник, указанный в массиве manager, где manager[i] — это непосредственный начальник i-го сотрудника, manager[headID] = -1. Также гарантируется, что отношения подчинения образуют древовидную структуру.

Руководитель компании хочет сообщить всем сотрудникам компании срочную новость. Он сообщит своим непосредственным подчиненным, а они сообщат своим подчиненным и так далее, пока все сотрудники не узнают о срочной новости.

i-й сотрудник нуждается в informTime[i] минутах, чтобы сообщить всем своим непосредственным подчиненным (т.е. через informTime[i] минут все его непосредственные подчиненные могут начать распространять новость).

Верните количество минут, необходимых для того, чтобы сообщить всем сотрудникам о срочной новости.

Пример:

Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
Output: 1
Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all.
The tree structure of the employees in the company is shown.

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

1⃣Создайте список смежности adjList; индекс i будет хранить смежные узлы для сотрудника с идентификатором i.

2⃣Итерируйте по сотрудникам от 0 до N - 1, и для каждого сотрудника i добавляйте ребро manager[i] -> i, если manager[i] не равен -1.

3⃣Начните выполнение DFS с узла headID и временем 0 для каждого узла как curr. Обновите максимальное время maxTime, сравнив его с текущим временем. Итерируйте по смежным узлам curr и для каждого смежного узла выполните DFS с временем time + informTime[curr]. Когда DFS завершится, верните maxTime.

😎 Решение:

class Solution {
    private var maxTime = Int.MIN_VALUE
    
    private fun DFS(adjList: Array<MutableList<Int>>, informTime: IntArray, curr: Int, time: Int) {
        maxTime = maxOf(maxTime, time)
        for (adjacent in adjList[curr]) {
            DFS(adjList, informTime, adjacent, time + informTime[curr])
        }
    }
    
    fun numOfMinutes(n: Int, headID: Int, manager: IntArray, informTime: IntArray): Int {
        val adjList = Array(n) { mutableListOf<Int>() }
        for (i in 0 until n) {
            if (manager[i] != -1) {
                adjList[manager[i]].add(i)
            }
        }
        DFS(adjList, informTime, headID, 0)
        return maxTime
    }
}

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

Задача: 732. My Calendar III
Сложность: hard

k-бронирование происходит, когда k событий имеют некоторое непустое пересечение (т.е, дано некоторое время, общее для всех k событий). Даны некоторые события [startTime, endTime), после каждого данного события верните целое число k, представляющее максимальное k-бронирование между всеми предыдущими событиями. Реализация класса MyCalendarThree: MyCalendarThree() Инициализирует объект. int book(int startTime, int endTime) Возвращает целое число k, представляющее наибольшее целое число, при котором в календаре существует k-бронирование.

Пример:

Input
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, 1, 1, 2, 3, 3, 3]

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

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

2⃣Для каждого нового события обновите словари начала и конца событий.

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

😎 Решение:

class MyCalendarThree {
    private val events = mutableMapOf<Int, Int>()
    
    fun book(startTime: Int, endTime: Int): Int {
        events[startTime] = events.getOrDefault(startTime, 0) + 1
        events[endTime] = events.getOrDefault(endTime, 0) - 1
        
        var active = 0
        var maxActive = 0
        for (time in events.keys.sorted()) {
            active += events[time]!!
            maxActive = maxOf(maxActive, active)
        }
        
        return maxActive
    }
}

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

Задача: 55. Jump Game
Сложность: medium

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

Верните true, если вы можете достичь последнего индекса, или false в противном случае.

Пример:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

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

1⃣ Инициализация таблицы памяти:
Изначально все элементы таблицы памяти имеют статус UNKNOWN, за исключением последнего, который является (тривиально) GOOD (может достичь сам себя).

2⃣Модификация алгоритма обратного трассирования:
Измените алгоритм обратного трассирования таким образом, чтобы на рекурсивном шаге сначала проверялось, известен ли индекс (GOOD/BAD).
Если индекс известен, тогда возвращается True/False.

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

😎 Решение:

class Solution {
    private lateinit var memo: IntArray
    private lateinit var nums: IntArray

    private fun canJumpFromPosition(position: Int): Boolean {
        if (memo[position] != -1) {
            return memo[position] == 1
        }
        val furthestJump = minOf(position + nums[position], nums.size - 1)
        for (nextPosition in position + 1..furthestJump) {
            if (canJumpFromPosition(nextPosition)) {
                memo[position] = 1
                return true
            }
        }
        memo[position] = 0
        return false
    }

    fun canJump(nums: IntArray): Boolean {
        this.nums = nums
        memo = IntArray(nums.size) { -1 }
        memo[nums.lastIndex] = 1 // The last position is always "good"
        return canJumpFromPosition(0)
    }
}

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

Задача: 943. Find the Shortest Superstring
Сложность: hard

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

Пример:

Input: words = ["alex","loves","leetcode"]
Output: "alexlovesleetcode"

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

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

2⃣Реализовать функцию merge для объединения двух строк с максимальным перекрытием.
Использовать жадный алгоритм для нахождения двух строк с максимальным перекрытием и объединить их, повторяя до тех пор, пока не останется одна строка.

3⃣Вернуть результат.

😎 Решение:

class Solution {
    fun shortestSuperstring(words: Array<String>): String {
        var words = words.toList()
        while (words.size > 1) {
            var maxOverlap = -1
            var l = 0
            var r = 0
            var merged = ""
            for (i in words.indices) {
                for (j in words.indices) {
                    if (i != j) {
                        val ovlp = overlap(words[i], words[j])
                        if (ovlp > maxOverlap) {
                            maxOverlap = ovlp
                            l = i
                            r = j
                            merged = merge(words[i], words[j], ovlp)
                        }
                    }
                }
            }
            words = words.toMutableList().apply {
                this[l] = merged
                removeAt(r)
            }
        }
        return words[0]
    }

    private fun overlap(a: String, b: String): Int {
        var maxOverlap = 0
        for (i in 1..minOf(a.length, b.length)) {
            if (a.takeLast(i) == b.take(i)) {
                maxOverlap = i
            }
        }
        return maxOverlap
    }

    private fun merge(a: String, b: String, overlapLen: Int): String {
        return a + b.drop(overlapLen)
    }
}

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

Задача: CodeTestcaseTest ResultTest Result1187. Make Array Strictly Increasing
Сложность: hard

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

В одной операции вы можете выбрать два индекса 0 <= i < arr1.length и 0 <= j < arr2.length и выполнить присваивание arr1[i] = arr2[j].

Если нет способа сделать arr1 строго возрастающим, верните -1.

Пример:

Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7].

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

1⃣Сначала отсортируйте массив arr2 и инициализируйте хэш-таблицу dp для хранения промежуточных результатов. Определите функцию dfs(i, prev), которая вычисляет минимальное количество операций для сортировки массива arr1, начиная с индекса i, при условии, что предыдущий элемент равен prev. Если результат для (i, prev) уже существует в dp, то просто верните сохраненное значение.

2⃣Внутри функции dfs инициализируйте переменную cost значением float('inf'). Если arr1[i] больше, чем prev, обновите значение cost результатом вызова dfs(i + 1, arr1[i]). Используйте бинарный поиск, чтобы найти индекс idx наименьшего значения в arr2, которое больше prev. Если такой индекс существует, обновите значение cost результатом минимального значения между текущим значением cost и 1 + dfs(i + 1, arr2[idx]).

3⃣После всех вычислений обновите dp[(i, prev)] значением cost и верните cost. В конце вызовите dfs(0, -1) и верните его значение, если оно не равно float('inf'); в противном случае верните -1.

😎 Решение:

class Solution {
    fun makeArrayIncreasing(arr1: IntArray, arr2: IntArray): Int {
        val sortedArr2 = arr2.toSet().sorted()
        val dp = mutableMapOf<Pair<Int, Int>, Int>()
        
        fun dfs(i: Int, prev: Int): Int {
            if (i == arr1.size) return 0
            val key = Pair(i, prev)
            if (key in dp) return dp[key]!!
            
            var cost = 2001
            if (arr1[i] > prev) {
                cost = dfs(i + 1, arr1[i])
            }
            val idx = sortedArr2.binarySearch { if (it <= prev) -1 else 1 }
            if (idx < sortedArr2.size && idx >= 0) {
                cost = minOf(cost, 1 + dfs(i + 1, sortedArr2[idx]))
            }
            
            dp[key] = cost
            return cost
        }
        
        val result = dfs(0, -1)
        return if (result < 2001) result else -1
    }
}

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

Задача: 1129. Shortest Path with Alternating Colors
Сложность: medium

Вам дано целое число n, количество узлов в ориентированном графе, где узлы помечены от 0 до n - 1. Каждое ребро в этом графе может быть красным или синим, и могут быть самопетли и параллельные ребра.

Вам даны два массива redEdges и blueEdges, где:
redEdges[i] = [ai, bi] указывает, что в графе существует направленное красное ребро от узла ai к узлу bi, и
blueEdges[j] = [uj, vj] указывает, что в графе существует направленное синее ребро от узла uj к узлу vj.
Верните массив answer длины n, где каждый answer[x] — это длина кратчайшего пути от узла 0 до узла x, такого что цвета ребер чередуются вдоль пути, или -1, если такого пути не существует.

Пример:

Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output: [0,1,-1]

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

1⃣Создание структуры данных и инициализация:
Создайте список смежности adj, который будет содержать пары (сосед, цвет) для каждого узла.
Создайте массив answer длиной n, инициализированный значением -1, чтобы хранить длину кратчайшего пути для каждого узла.
Создайте 2D массив visit для отслеживания, были ли узлы посещены с использованием ребра определённого цвета.

2⃣Инициализация очереди и начальных условий:
Создайте очередь для хранения трёх значений (узел, количество шагов, цвет предыдущего ребра).
Добавьте в очередь начальный узел (0, 0, -1) и установите visit[0][0] и visit[0][1] в true, так как повторное посещение узла 0 бессмысленно.

3⃣Обработка очереди и обновление результата:
Пока очередь не пуста, извлекайте элемент из очереди и получайте (узел, количество шагов, цвет предыдущего ребра).
Для каждого соседа, если сосед не был посещён с использованием ребра текущего цвета и текущий цвет не равен предыдущему, обновите массив answer и добавьте соседа в очередь.

😎 Решение:

class Solution {
    fun shortestAlternatingPaths(n: Int, redEdges: Array<IntArray>, blueEdges: Array<IntArray>): IntArray {
        val adj = mutableMapOf<Int, MutableList<Pair<Int, Int>>>()
        for ((a, b) in redEdges) {
            adj.computeIfAbsent(a) { mutableListOf() }.add(Pair(b, 0))
        }
        for ((u, v) in blueEdges) {
            adj.computeIfAbsent(u) { mutableListOf() }.add(Pair(v, 1))
        }

        val answer = IntArray(n) { -1 }
        val visit = Array(n) { BooleanArray(2) }
        val queue: Queue<Triple<Int, Int, Int>> = LinkedList()
        queue.add(Triple(0, 0, -1))
        answer[0] = 0
        visit[0][0] = true
        visit[0][1] = true

        while (queue.isNotEmpty()) {
            val (node, steps, prevColor) = queue.poll()
            adj[node]?.forEach { (neighbor, color) ->
                if (!visit[neighbor][color] && color != prevColor) {
                    if (answer[neighbor] == -1) {
                        answer[neighbor] = steps + 1
                    }
                    visit[neighbor][color] = true
                    queue.add(Triple(neighbor, steps + 1, color))
                }
            }
        }
        return answer
    }
}

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

Задача: 623. Add One Row to Tree
Сложность: medium

Учитывая корень бинарного дерева и два целых числа val и depth, добавьте ряд узлов со значением val на заданную глубину depth. Обратите внимание, что корневой узел находится на глубине 1. Правило добавления таково: учитывая целое число depth, для каждого ненулевого узла дерева cur на глубине depth - 1 создайте два узла дерева со значением val в качестве левого поддерева корня cur и правого поддерева корня.
Оригинальное левое поддерево cur должно быть левым поддеревом нового корня левого поддерева. Оригинальное правое поддерево cur должно быть правым поддеревом нового корня правого поддерева. Если глубина == 1, то есть глубина - 1 вообще не существует, создайте узел дерева со значением val как новый корень всего оригинального дерева, а оригинальное дерево - левое поддерево нового корня.

Пример:

Input: root = [4,2,6,3,1,5], val = 1, depth = 2
Output: [4,1,1,2,null,null,6,3,1,5]

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

1⃣Если depth равна 1, создайте новый корень со значением val и сделайте текущий корень левым поддеревом нового корня.

2⃣Используйте обход в ширину (BFS) для поиска всех узлов на глубине depth - 1.

3⃣Для каждого узла на глубине depth - 1, вставьте новые узлы со значением val в качестве левого и правого поддеревьев, сохраняя исходные поддеревья.

😎 Решение:

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

fun addOneRow(root: TreeNode?, `val`: Int, depth: Int): TreeNode? {
    if (depth == 1) {
        return TreeNode(`val`).apply { left = root }
    }
    
    val queue = mutableListOf<TreeNode>()
    root?.let { queue.add(it) }
    var currentDepth = 1
    
    while (queue.isNotEmpty()) {
        if (currentDepth == depth - 1) {
            queue.forEach { node ->
                node.left = TreeNode(`val`).apply { left = node.left }
                node.right = TreeNode(`val`).apply { right = node.right }
            }
            break
        }
        currentDepth++
        val nextQueue = mutableListOf<TreeNode>()
        queue.forEach { node ->
            node.left?.let { nextQueue.add(it) }
            node.right?.let { nextQueue.add(it) }
        }
        queue.clear()
        queue.addAll(nextQueue)
    }
    
    return root
}

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

Задача: 1344. Angle Between Hands of a Clock
Сложность: medium

Даны два числа, hour и minutes. Вернуть меньший угол (в градусах), образованный часовой и минутной стрелками.

Ответы с точностью до 10^-5 от фактического значения будут считаться правильными.

Пример:

Input: hour = 12, minutes = 30
Output: 165

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

1⃣Рассчитать углы: minutes_angle = 6 * minutes и hour_angle = (hour % 12 + minutes / 60) * 30.

2⃣Найти разницу: diff = abs(hour_angle - minutes_angle).

3⃣Вернуть меньший угол: min(diff, 360 - diff).

😎 Решение:

class Solution {
    fun angleClock(hour: Int, minutes: Int): Double {
        val oneMinAngle = 6.0
        val oneHourAngle = 30.0

        val minutesAngle = oneMinAngle * minutes
        val hourAngle = (hour % 12 + minutes / 60.0) * oneHourAngle

        val diff = kotlin.math.abs(hourAngle - minutesAngle)
        return kotlin.math.min(diff, 360 - diff)
    }
}

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

Задача: 1065. Index Pairs of a String
Сложность: easy

Дана строка text и массив строк words, верните массив всех пар индексов [i, j], таких что подстрока text[i...j] находится в words.

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

Пример:

Input: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"]
Output: [[3,7],[9,13],[10,17]]

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

1⃣Поддерживайте хэш-набор слов.

2⃣Итерируйте i от 0 до text.length-1. Итерируйте j от i до text.length-1. Если подстрока text[i...j] принадлежит хэш-набору слов, добавьте пару [i, j] в ответ.

3⃣Верните ответ.

😎 Решение:

class Solution {
    fun indexPairs(text: String, words: Array<String>): List<List<Int>> {
        val wordsSet = words.toSet()
        val ans = mutableListOf<List<Int>>()
        
        for (i in text.indices) {
            for (j in i until text.length) {
                if (text.substring(i, j + 1) in wordsSet) {
                    ans.add(listOf(i, j))
                }
            }
        }
        return ans
    }
}

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