Задача: 153. Find Minimum in Rotated Sorted Array
Сложность: medium

Дан массив nums, отсортированный по возрастанию и повернутый несколько раз.
Нужно найти минимальный элемент массива.
Все элементы уникальны, и требуется решение за O(log n).

Пример:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

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

1⃣Если массив уже отсортирован (nums[0] < nums[n-1]), то минимум — первый элемент.

2⃣Иначе используем бинарный поиск: Если nums[mid] > nums[mid + 1] — минимум справа (mid+1). Если nums[mid - 1] > nums[mid] — минимум в mid.

3⃣В зависимости от значения nums[mid], сдвигаем границы поиска влево или вправо, пока не найдём точку перегиба.

😎 Решение:

class Solution {
    fun findMin(nums: IntArray): Int {
        if (nums.size == 1) {
            return nums[0]
        }
        
        var left = 0
        var right = nums.size - 1
        
        if (nums[right] > nums[0]) {
            return nums[0]
        }
        
        while (left <= right) {
            val mid = left + (right - left) / 2
            
            if (nums[mid] > nums[mid + 1]) {
                return nums[mid + 1]
            }
            
            if (mid > 0 && nums[mid - 1] > nums[mid]) {
                return nums[mid]
            }
            
            if (nums[mid] > nums[0]) {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        
        return -1
    }
}

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

Задача: 1102. Path With Maximum Minimum Value
Сложность: medium

Дана целочисленная матрица grid размером m x n. Верните максимальное значение пути, начинающегося в (0, 0) и заканчивающегося в (m - 1, n - 1), двигаясь в 4 кардинальных направлениях.

Значение пути определяется минимальным числом на этом пути.

Пример:

Input: grid = [[5,4,5],[1,2,6],[7,4,6]]
Output: 4
Explanation: The path with the maximum score is highlighted in yellow. 

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

1⃣Начните с оценки curScore = min(grid[0][0], grid[m-1][n-1]), где m и n - общее количество строк и столбцов входной матрицы.

2⃣Выполните BFS на матрице и проверьте, существует ли путь, где все значения больше или равны curScore:
Используйте очередь (deque) для хранения всех непосещенных ячеек со значением, большим или равным curScore.
Извлекайте ячейку из начала очереди, проверяйте, есть ли у нее непосещенные соседние ячейки, и добавляйте их в конец очереди.
Если успешно достигли правой нижней ячейки, значит путь существует.
Если очередь опустела до достижения правой нижней ячейки, пути не существует.

3⃣Если пути не существует, что означает, что curScore слишком велик, уменьшите его на 1 и повторите шаг 2.
В противном случае, верните curScore как ответ.

😎 Решение:

class Solution {
    private val dirs = arrayOf(
        intArrayOf(1, 0), intArrayOf(0, 1), intArrayOf(-1, 0), intArrayOf(0, -1)
    )

    fun maximumMinimumPath(grid: Array<IntArray>): Int {
        var curScore = minOf(grid[0][0], grid[grid.size - 1][grid[0].size - 1])

        while (curScore >= 0) {
            if (pathExists(grid, curScore)) {
                return curScore
            }
            curScore -= 1
        }
        return -1
    }

    private fun pathExists(grid: Array<IntArray>, curScore: Int): Boolean {
        val R = grid.size
        val C = grid[0].size
        val visited = Array(R) { BooleanArray(C) }
        val dq = ArrayDeque<Pair<Int, Int>>()
        dq.add(0 to 0)
        visited[0][0] = true

        fun push(row: Int, col: Int) {
            if (row in 0 until R && col in 0 until C && !visited[row][col] && grid[row][col] >= curScore) {
                dq.add(row to col)
                visited[row][col] = true
            }
        }

        while (dq.isNotEmpty()) {
            val (curRow, curCol) = dq.removeFirst()
            if (curRow == R - 1 && curCol == C - 1) {
                return true
            }

            for (dir in dirs) {
                push(curRow + dir[0], curCol + dir[1])
            }
        }
        return false
    }
}

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

Задача: 653. Two Sum IV - Input is a BST
Сложность: easy

Вам дан целочисленный массив nums без дубликатов. Из nums можно рекурсивно построить максимальное двоичное дерево, используя следующий алгоритм: создайте корневой узел, значение которого равно максимальному значению в nums. Рекурсивно постройте левое поддерево по префиксу подмассива слева от максимального значения. Рекурсивно постройте правое поддерево по суффиксу подмассива справа от максимального значения. Верните максимальное двоичное дерево, построенное из nums.

Пример:

Input: root = [5,3,6,2,4,null,7], k = 9
Output: true

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

1⃣Выполните обход BST и сохраните все значения узлов в набор.

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

3⃣Если найдена такая пара, верните true. Если обход завершен и пары не найдены, верните false.

😎 Решение:

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

fun findTarget(root: TreeNode?, k: Int): Boolean {
    val seen = mutableSetOf<Int>()
    fun find(node: TreeNode?): Boolean {
        if (node == null) return false
        if (seen.contains(k - node.`val`)) return true
        seen.add(node.`val`)
        return find(node.left) || find(node.right)
    }
    return find(root)
}

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

Задача: 636. Exclusive Time of Functions
Сложность: medium

На однопоточном процессоре выполняется программа, содержащая n функций. Каждая функция имеет уникальный ID от 0 до n-1. Вызовы функций хранятся в стеке вызовов: когда начинается вызов функции, ее ID заталкивается в стек, а когда вызов функции заканчивается, ее ID выгружается из стека. Функция, чей идентификатор находится в верхней части стека, является текущей выполняемой функцией. Каждый раз, когда функция запускается или завершается, мы пишем лог с идентификатором, началом или завершением и меткой времени. Вам предоставляется список logs, где logs[i] представляет собой i-е сообщение лога, отформатированное как строка "{function_id}:{"start" | "end"}:{timestamp}". Например, "0:start:3" означает, что вызов функции с идентификатором 0 начался в начале временной метки 3, а "1:end:2" означает, что вызов функции с идентификатором 1 завершился в конце временной метки 2. Обратите внимание, что функция может быть вызвана несколько раз, возможно, рекурсивно. Исключительное время функции - это сумма времен выполнения всех вызовов функции в программе. Например, если функция вызывается дважды, причем один вызов выполняется за 2 единицы времени, а другой - за 1 единицу, то эксклюзивное время равно 2 + 1 = 3. Верните эксклюзивное время каждой функции в массив, где значение по i-му индексу представляет собой эксклюзивное время для функции с идентификатором i.

Пример:

Input: n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
Output: [3,4]

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

1⃣Парсинг логов
Пройдитесь по каждому логу, чтобы распознать действие (start или end) и идентификатор функции вместе с временной меткой.

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

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

😎 Решение:

class Solution {
    fun exclusiveTime(n: Int, logs: List<String>): IntArray {
        val stack = mutableListOf<Int>()
        val times = IntArray(n)
        var prevTime = 0
        
        for (log in logs) {
            val parts = log.split(":")
            val fid = parts[0].toInt()
            val type = parts[1]
            val time = parts[2].toInt()
            
            if (type == "start") {
                if (stack.isNotEmpty()) {
                    times[stack.last()] += time - prevTime
                }
                stack.add(fid)
                prevTime = time
            } else {
                times[stack.removeAt(stack.size - 1)] += time - prevTime + 1
                prevTime = time + 1
            }
        }
        
        return times
    }
}

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

Задача: 995. Minimum Number of K Consecutive Bit Flips
Сложность: hard

Дан бинарный массив nums и целое число k.

Операция переворота k-бит заключается в выборе подмассива длиной k из nums и одновременном изменении каждого 0 в подмассиве на 1 и каждого 1 в подмассиве на 0.

Верните минимальное количество k-битных переворотов, необходимых для того, чтобы в массиве не осталось 0. Если это невозможно, верните -1.

Подмассив - это непрерывная часть массива.

Пример:

Input: nums = [0,1,0], k = 1
Output: 2
Explanation: Flip nums[0], then flip nums[2].

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

1⃣Инициализация переменных:
Создайте массив flip, чтобы отслеживать, сколько раз был перевернут каждый элемент.
Инициализируйте flips для отслеживания количества текущих переворотов.

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

3⃣Проверка возможности выполнения задачи:
Если количество переворотов больше длины массива, верните -1.

😎 Решение:

class Solution {
    fun minKBitFlips(nums: IntArray, k: Int): Int {
        val n = nums.size
        var flip = 0
        var flips = 0
        val flipQueue = IntArray(n)
        
        for (i in 0 until n) {
            if (i >= k) {
                flip = flip xor flipQueue[i - k]
            }
            if (nums[i] == flip) {
                if (i + k > n) return -1
                flips++
                flip = flip xor 1
                flipQueue[i] = 1
            }
        }
        return flips
    }
}

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

Задача: 1009. Complement of Base 10 Integer
Сложность: easy

Дополнение целого числа - это целое число, которое получается, если перевернуть все 0 в 1 и все 1 в 0 в его двоичном представлении. Например, целое число 5 - это "101" в двоичном представлении, а его дополнение - "010", то есть целое число 2. Если задано целое число n, верните его дополнение.

Пример:

Input: n = 5
Output: 2

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

1⃣Определение длины двоичного представления:
Найдите длину двоичного представления числа n.

2⃣Создание маски:
Создайте маску, которая состоит из всех единиц и имеет ту же длину, что и двоичное представление числа n.

3⃣Вычисление дополнения:
Примените побитовую операцию XOR между числом n и маской, чтобы получить дополнение числа.

😎 Решение:

class Solution {
    fun findComplement(num: Int): Int {
        val length = 32 - Integer.numberOfLeadingZeros(num)
        val mask = (1 shl length) - 1
        return num xor mask
    }
}

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

Задача: 1437. Check If All 1's Are at Least Length K Places Away
Сложность: easy

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

Пример:

Input: nums = [1,0,0,0,1,0,0,1], k = 2
Output: true
Explanation: Each of the 1s are at least 2 places away from each other.

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

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

2⃣Итерировать по массиву nums, проверяя, если текущий элемент равен 1. Если число нулей между единицами меньше k, вернуть false; иначе сбросить счетчик нулей на 0.

3⃣Если текущий элемент равен 0, увеличить счетчик нулей. В конце итерации вернуть true.

😎 Решение:

class Solution {
    fun kLengthApart(nums: IntArray, k: Int): Boolean {
        var count = k
        for (num in nums) {
            if (num == 1) {
                if (count < k) {
                    return false
                }
                count = 0
            } else {
                count++
            }
        }
        return true
    }
}

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

Задача: 1250. Check If It Is a Good Array
Сложность: hard

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

Пример:

Input: nums = [12,5,7,23]
Output: true

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

1⃣Если наибольший общий делитель (НОД) всех чисел в массиве равен 1, то массив считается хорошим.

2⃣Если НОД всех чисел больше 1, то массив не считается хорошим

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

😎 Решение:

class Solution {
    fun isGoodArray(nums: IntArray): Boolean {
        var gcd = nums[0]
        for (num in nums) {
            gcd = gcd(gcd, num)
            if (gcd == 1) {
                return true
            }
        }
        return gcd == 1
    }

    private fun gcd(a: Int, b: Int): Int {
        var a = a
        var b = b
        while (b != 0) {
            val temp = b
            b = a % b
            a = temp
        }
        return a
    }
}

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

Задача: 542. 01 Matrix
Сложность: medium

Дана бинарная матрица размера m x n, верните расстояние до ближайшего нуля для каждой ячейки.

Расстояние между двумя соседними ячейками равно 1.

Пример:

Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]

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

1⃣Создайте копию матрицы mat, назовем её matrix. Используйте структуру данных seen для пометки уже посещенных узлов и очередь для выполнения BFS. Поместите все узлы с 0 в очередь и отметьте их в seen.

2⃣Выполните BFS:
Пока очередь не пуста, извлекайте текущие row, col, steps из очереди.
Итеративно пройдите по четырем направлениям. Для каждой nextRow, nextCol проверьте, находятся ли они в пределах границ и не были ли они уже посещены в seen.

3⃣Если так, установите matrix[nextRow][nextCol] = steps + 1 и поместите nextRow, nextCol, steps + 1 в очередь. Также отметьте nextRow, nextCol в seen. Верните matrix.

😎 Решение:

import java.util.*

class Solution {
    var m: Int = 0
    var n: Int = 0
    val directions = arrayOf(intArrayOf(0, 1), intArrayOf(1, 0), intArrayOf(0, -1), intArrayOf(-1, 0))
    
    fun updateMatrix(mat: Array<IntArray>): Array<IntArray> {
        m = mat.size
        n = mat[0].size
        val matrix = Array(m) { IntArray(n) }
        val seen = Array(m) { BooleanArray(n) }
        val queue: Queue<IntArray> = LinkedList()

        for (row in 0 until m) {
            for (col in 0 until n) {
                matrix[row][col] = mat[row][col]
                if (matrix[row][col] == 0) {
                    queue.add(intArrayOf(row, col, 0))
                    seen[row][col] = true
                }
            }
        }
        
        while (queue.isNotEmpty()) {
            val curr = queue.poll()
            val row = curr[0]
            val col = curr[1]
            val steps = curr[2]
            
            for (direction in directions) {
                val nextRow = row + direction[0]
                val nextCol = col + direction[1]
                if (valid(nextRow, nextCol) && !seen[nextRow][nextCol]) {
                    seen[nextRow][nextCol] = true
                    queue.add(intArrayOf(nextRow, nextCol, steps + 1))
                    matrix[nextRow][nextCol] = steps + 1
                }
            }
        }
        
        return matrix
    }
    
    fun valid(row: Int, col: Int): Boolean {
        return 0 <= row && row < m && 0 <= col && col < n
    }
}

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

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

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

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

Пример:

Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]

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

1⃣Преобразуйте wordDict в Set для быстрого поиска. Запустите backtrack с индексом 0 и пустым текущим предложением.

2⃣На каждом шаге пробуйте все подстроки от startIndex до конца. Если подстрока в wordSet, добавьте её в текущее предложение и рекурсивно вызовите backtrack.

3⃣Когда достигли конца строки, объедините текущие слова в строку и добавьте в результат. После рекурсии — удалите последнее слово (откат).

😎 Решение:

class Solution {
    fun wordBreak(s: String, wordDict: List<String>): List<String> {
        val wordSet = wordDict.toSet()
        val results = mutableListOf<String>()
        backtrack(s, wordSet, mutableListOf(), results, 0)
        return results
    }

    private fun backtrack(s: String, wordSet: Set<String>, currentSentence: MutableList<String>, results: MutableList<String>, startIndex: Int) {
        if (startIndex == s.length) {
            results.add(currentSentence.joinToString(" "))
            return
        }

        for (endIndex in startIndex + 1..s.length) {
            val word = s.substring(startIndex, endIndex)
            if (word in wordSet) {
                currentSentence.add(word)
                backtrack(s, wordSet, currentSentence, results, endIndex)
                currentSentence.removeAt(currentSentence.size - 1)
            }
        }
    }
}

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

Задача: 1675. Minimize Deviation in Array
Сложность: hard

Вам дан массив nums из n положительных целых чисел.

Вы можете выполнять два типа операций над любым элементом массива любое количество раз:
Если элемент четный, разделите его на 2.
Например, если массив [1,2,3,4], то вы можете выполнить эту операцию на последнем элементе, и массив станет [1,2,3,2].
Если элемент нечетный, умножьте его на 2.
Например, если массив [1,2,3,4], то вы можете выполнить эту операцию на первом элементе, и массив станет [2,2,3,4].
Отклонение массива — это максимальная разница между любыми двумя элементами в массиве.

Верните минимальное отклонение, которое может иметь массив после выполнения некоторого числа операций.

Пример:

Input: nums = [1,2,3,4]
Output: 1
Explanation: You can transform the array to [1,2,3,2], then to [2,2,3,2], then the deviation will be 3 - 2 = 1.

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

1⃣Инициализируйте max-heap под названием evens. Если элемент массива четный, добавьте его в evens; если элемент нечетный, умножьте его на 2 и добавьте в evens. Одновременно отслеживайте минимальный элемент в evens.

2⃣Извлекайте максимальный элемент из evens, обновляйте минимальное отклонение, используя максимальный элемент и текущий минимальный элемент. Если максимальный элемент четный, делите его на 2 и снова добавляйте в evens.

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

😎 Решение:

import java.util.PriorityQueue

class Solution {
    fun minimumDeviation(nums: IntArray): Int {
        val evens = PriorityQueue<Int>(compareByDescending { it })
        var minimum = Int.MAX_VALUE
        
        for (num in nums) {
            if (num % 2 == 0) {
                evens.add(num)
                minimum = minOf(minimum, num)
            } else {
                evens.add(num * 2)
                minimum = minOf(minimum, num * 2)
            }
        }
        
        var minDeviation = Int.MAX_VALUE
        
        while (evens.isNotEmpty()) {
            val currentValue = evens.poll()
            minDeviation = minOf(minDeviation, currentValue - minimum)
            if (currentValue % 2 == 0) {
                evens.add(currentValue / 2)
                minimum = minOf(minimum, currentValue / 2)
            } else {
                break
            }
        }
        
        return minDeviation
    }
}

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

Задача: 830. Positions of Large Groups
Сложность: easy

В строке s из строчных букв эти буквы образуют последовательные группы одного и того же символа.
Например, строка s = "abbxxxxzyy" имеет группы "a", "bb", "xxxx", "z" и "yy".
Группа идентифицируется интервалом [start, end], где start и end обозначают начальный и конечный индексы (включительно) группы. В приведенном выше примере "xxxx" имеет интервал [3,6].
Группа считается большой, если в ней 3 или более символов.

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

Пример:

Input: s = "abcdddeeeeaabbbcd"
Output: [[3,5],[6,9],[12,14]]
Explanation: The large groups are "ddd", "eeee", and "bbb".

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

1⃣Поддерживайте указатели i и j, где i <= j. Указатель i представляет начало текущей группы, а j будет инкрементироваться вперед, пока не достигнет конца группы.

2⃣Когда j достигнет конца строки или S[j] != S[j+1], у нас будет группа [i, j]. Если длина группы больше или равна 3, добавьте её в результат.

3⃣Обновите i = j + 1 и начните новую группу.

😎 Решение:

class Solution {
    fun largeGroupPositions(S: String): List<List<Int>> {
        val ans = mutableListOf<List<Int>>()
        var i = 0
        val N = S.length

        for (j in 0 until N) {
            if (j == N - 1 || S[j] != S[j + 1]) {
                if (j - i + 1 >= 3) {
                    ans.add(listOf(i, j))
                }
                i = j + 1
            }
        }

        return ans
    }

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

Задача: 252. Meeting Rooms
Сложность: easy

Дан массив интервалов времени встреч, где intervals[i] = [starti, endi]. Определите, может ли человек посетить все встречи.

Пример:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: false

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

1⃣Создайте функцию для проверки перекрытия двух интервалов:
Возвращайте true, если начало одного интервала находится внутри другого интервала.

2⃣Проверьте каждый интервал с каждым другим интервалом:
Если найдено перекрытие, верните false.

3⃣Если все интервалы проверены и перекрытий не найдено, верните true.

😎 Решение:

class Solution {
    fun canAttendMeetings(intervals: List<List<Int>>): Boolean {
        fun overlap(interval1: List<Int>, interval2: List<Int>): Boolean {
            return (interval1[0] >= interval2[0] && interval1[0] < interval2[1]) ||
                   (interval2[0] >= interval1[0] && interval2[0] < interval1[1])
        }

        for (i in intervals.indices) {
            for (j in i + 1 until intervals.size) {
                if (overlap(intervals[i], intervals[j])) {
                    return false
                }
            }
        }
        return true
    }
}

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

Задача: 416. Partition Equal Subset Sum
Сложность: medium

Если задан целочисленный массив nums, верните третье максимальное число в этом массиве. Если третьего максимального числа не существует, верните максимальное число.

Пример:

Input: nums = [1,5,11,5]
Output: true

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

1⃣Проверьте, является ли сумма всех элементов массива четной. Если нет, верните false.

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

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

😎 Решение:

fun canPartition(nums: IntArray): Boolean {
    val sum = nums.sum()
    if (sum % 2 != 0) return false
    val target = sum / 2
    val dp = BooleanArray(target + 1) { false }
    dp[0] = true
    
    for (num in nums) {
        for (j in target downTo num) {
            dp[j] = dp[j] || dp[j - num]
        }
    }
    
    return dp[target]
}

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

Задача: 417. Pacific Atlantic Water Flow
Сложность: medium

Имеется прямоугольный остров размером m x n, который граничит с Тихим и Атлантическим океанами. Тихий океан касается левого и верхнего краев острова, а Атлантический океан - правого и нижнего краев. Остров разбит на сетку квадратных ячеек. Вам дана целочисленная матрица heights размером m x n, где heights[r][c] - высота над уровнем моря клетки с координатами (r, c). На острове выпадает много осадков, и дождевая вода может стекать в соседние клетки прямо на север, юг, восток и запад, если высота соседней клетки меньше или равна высоте текущей клетки. Вода может течь из любой клетки, прилегающей к океану, в океан. Верните двумерный список координат сетки result, где result[i] = [ri, ci] означает, что дождевая вода может течь из клетки (ri, ci) как в Тихий, так и в Атлантический океаны.

Пример:

Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

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

1⃣Определите две матрицы для отслеживания клеток, из которых вода может течь в Тихий и Атлантический океаны, используя поиск в глубину (DFS) или поиск в ширину (BFS), начиная с границ, примыкающих к каждому океану.

2⃣Выполните поиск для каждого океана, обновляя матрицы достижимости.

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

😎 Решение:

fun pacificAtlantic(heights: Array<IntArray>): List<List<Int>> {
    val m = heights.size
    val n = heights[0].size
    val pacific = Array(m) { BooleanArray(n) }
    val atlantic = Array(m) { BooleanArray(n) }
    val directions = arrayOf(intArrayOf(-1, 0), intArrayOf(1, 0), intArrayOf(0, -1), intArrayOf(0, 1))
    
    fun dfs(r: Int, c: Int, ocean: Array<BooleanArray>) {
        ocean[r][c] = true
        for (dir in directions) {
            val nr = r + dir[0]
            val nc = c + dir[1]
            if (nr in 0 until m && nc in 0 until n && !ocean[nr][nc] && heights[nr][nc] >= heights[r][c]) {
                dfs(nr, nc, ocean)
            }
        }
    }
    
    for (i in 0 until m) {
        dfs(i, 0, pacific)
        dfs(i, n - 1, atlantic)
    }
    for (j in 0 until n) {
        dfs(0, j, pacific)
        dfs(m - 1, j, atlantic)
    }
    
    val result = mutableListOf<List<Int>>()
    for (i in 0 until m) {
        for (j in 0 until n) {
            if (pacific[i][j] && atlantic[i][j]) {
                result.add(listOf(i, j))
            }
        }
    }
    return result
}

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

Задача: 999. Available Captures for Rook
Сложность: easy

Вам дана матрица 8 x 8, изображающая шахматную доску. На ней есть ровно одна белая ладья, представленная символом "R", некоторое количество белых слонов "B" и некоторое количество черных пешек "p". Пустые клетки обозначаются символом '.'. Ладья может перемещаться на любое количество клеток по горизонтали или вертикали (вверх, вниз, влево, вправо), пока не достигнет другой фигуры или края доски. Ладья атакует пешку, если она может переместиться на ее клетку за один ход. Примечание: Ладья не может перемещаться через другие фигуры, такие как слоны или пешки. Это означает, что ладья не может атаковать пешку, если путь ей преграждает другая фигура. Верните количество пешек, которые атакует белая ладья.

Пример:

Input: board = [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]

Output: 3

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

1⃣Поиск ладьи:
Найдите координаты белой ладьи "R" на шахматной доске.

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

3⃣Подсчет атакованных пешек:
Если встреченная фигура - черная пешка "p", увеличьте счетчик атакованных пешек.
Если встреченная фигура - белый слон "B" или край доски, остановитесь в этом направлении.

😎 Решение:

class Solution {
    fun numRookCaptures(board: Array<CharArray>): Int {
        fun countPawns(x: Int, y: Int, dx: Int, dy: Int): Int {
            var x = x
            var y = y
            while (x in 0..7 && y in 0..7) {
                when (board[x][y]) {
                    'B' -> return 0
                    'p' -> return 1
                }
                x += dx
                y += dy
            }
            return 0
        }

        for (i in 0..7) {
            for (j in 0..7) {
                if (board[i][j] == 'R') {
                    return countPawns(i, j, -1, 0) + countPawns(i, j, 1, 0) +
                           countPawns(i, j, 0, -1) + countPawns(i, j, 0, 1)
                }
            }
        }
        return 0
    }
}

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