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

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

Задача: 480. Sliding Window Median
Сложность: Hard

Медиана — это среднее значение в упорядоченном списке целых чисел. Если размер списка четный, среднего значения не существует, поэтому медианой считается среднее значение двух средних чисел.

Например, если arr = [2, 3, 4], медиана равна 3.
Например, если arr = [1, 2, 3, 4], медиана равна (2 + 3) / 2 = 2.5.

Вам дан целочисленный массив nums и целое число k. Существует скользящее окно размера k, которое перемещается от самого левого края массива до самого правого. Вы можете видеть только k чисел в окне. Каждый раз скользящее окно перемещается вправо на одну позицию.

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

Пример:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]
Explanation: 
Window position                Median
---------------                -----
[1  3  -1] -3  5  3  6  7        1
 1 [3  -1  -3] 5  3  6  7       -1
 1  3 [-1  -3  5] 3  6  7       -1
 1  3  -1 [-3  5  3] 6  7        3
 1  3  -1  -3 [5  3  6] 7        5
 1  3  -1  -3  5 [3  6  7]       6

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

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

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

3⃣ Поддерживайте окно в отсортированном состоянии до и после операций вставки и удаления.

😎 Решение:

fun medianSlidingWindow(nums: IntArray, k: Int): DoubleArray {
    val medians = mutableListOf<Double>()

    for (i in 0..(nums.size - k)) {
        val window = nums.sliceArray(i until i + k).sorted()

        if (k % 2 == 1) {
            medians.add(window[k / 2].toDouble())
        } else {
            medians.add((window[k / 2 - 1] + window[k / 2]) / 2.0)
        }
    }

    return medians.toDoubleArray()
}

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

Задача: 611. Valid Triangle Number
Сложность: medium

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

Пример:

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

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

1⃣Отсортируйте массив nums.

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

3⃣Увеличивайте счетчик на количество подходящих пар для каждого третьего элемента.

😎 Решение:

fun triangleNumber(nums: IntArray): Int {
    nums.sort()
    val n = nums.size
    var count = 0
    
    for (k in n - 1 downTo 2) {
        var i = 0
        var j = k - 1
        while (i < j) {
            if (nums[i] + nums[j] > nums[k]) {
                count += j - i
                j--
            } else {
                i++
            }
        }
    }
    
    return count
}

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

Задача: 716. Max Stack
Сложность: hard

Разработайте структуру данных max-стека, поддерживающую операции со стеком и поиск максимального элемента стека. Реализуйте класс MaxStack: MaxStack() Инициализирует объект стека. void push(int x) Вставляет элемент x в стек. int pop() Удаляет элемент на вершине стека и возвращает его. int top() Получает элемент на вершине стека без его удаления. int peekMax() Получает максимальный элемент в стеке без его удаления. int popMax() Получает максимальный элемент в стеке и удаляет его. Если максимальных элементов несколько, удалите только самый верхний. Вы должны придумать решение, которое поддерживает O(1) для каждого вызова вершины и O(logn) для каждого другого вызова.

Пример:

Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

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

1⃣Инициализируйте MaxStack с двумя стеками: один для хранения всех элементов, другой для отслеживания максимальных элементов.

2⃣Для операции push(x) добавьте элемент в оба стека: в основной стек и, если это необходимо, в стек максимумов. Для операции pop() удалите элемент из основного стека и, если этот элемент является текущим максимальным, удалите его и из стека максимумов. Для операции top() верните верхний элемент основного стека.

3⃣Для операции peekMax() верните верхний элемент стека максимумов. Для операции popMax() удалите и верните верхний элемент стека максимумов. Для этого временно извлеките элементы из основного стека до тех пор, пока не будет найден максимальный элемент, затем верните остальные элементы обратно.

😎 Решение:

class MaxStack {

    private val stack = mutableListOf<Int>()
    private val maxStack = mutableListOf<Int>()

    fun push(x: Int) {
        stack.add(x)
        if (maxStack.isEmpty() || x >= maxStack.last()) {
            maxStack.add(x)
        }
    }

    fun pop(): Int {
        val x = stack.removeAt(stack.size - 1)
        if (x == maxStack.last()) {
            maxStack.removeAt(maxStack.size - 1)
        }
        return x
    }

    fun top(): Int {
        return stack.last()
    }

    fun peekMax(): Int {
        return maxStack.last()
    }

    fun popMax(): Int {
        val maxVal = maxStack.removeAt(maxStack.size - 1)
        val buffer = mutableListOf<Int>()
        while (stack.last() != maxVal) {
            buffer.add(stack.removeAt(stack.size - 1))
        }
        stack.removeAt(stack.size - 1)
        while (buffer.isNotEmpty()) {
            push(buffer.removeAt(buffer.size - 1))
        }
        return maxVal
    }
}       }
        stack.pop();
        while (!buffer.empty()) {
            push(buffer.top());
            buffer.pop();
        }
        return maxVal;
    }

private:
    stack<int> stack;
    stack<int> maxStack;
};

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

Задача: 413. Arithmetic Slices
Сложность: medium

Целочисленный массив называется арифметическим, если он состоит не менее чем из трех элементов и если разность между любыми двумя последовательными элементами одинакова. Например, [1,3,5,7,9], [7,7,7] и [3,-1,-5,-9] являются арифметическими последовательностями. Если задан целочисленный массив nums, верните количество арифметических подмассивов массива nums. Подмассив - это непрерывная подпоследовательность массива.

Пример:

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

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

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

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

3⃣Суммируйте количество найденных арифметических подмассивов, учитывая, что для каждого арифметического подмассива длины len, количество таких подмассивов равно (len - 2).

😎 Решение:

fun numberOfArithmeticSlices(nums: IntArray): Int {
    if (nums.size < 3) return 0
    var count = 0
    var currentLength = 0
    for (i in 2 until nums.size) {
        if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
            currentLength++
            count += currentLength
        } else {
            currentLength = 0
        }
    }
    return count
}

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

Задача: 1480. Running Sum of 1d Array
Сложность: easy

Дан массив nums. Мы определяем текущую сумму массива как runningSum[i] = сумма(nums[0]…nums[i]).

Верните массив текущих сумм для nums.

Пример:

Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

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

1⃣Инициализация:
Определите массив result.
Инициализируйте первый элемент массива result первым элементом входного массива nums.

2⃣Вычисление текущих сумм:
На индексе i добавьте сумму элемента nums[i] и предыдущей текущей суммы result[i - 1] в массив result.

3⃣Повторение для всех индексов:
Повторите шаг 2 для всех индексов от 1 до n-1.

😎 Решение:

class Solution {
    fun runningSum(nums: IntArray): IntArray {
        val result = IntArray(nums.size)
        result[0] = nums[0]
        for (i in 1 until nums.size) {
            result[i] = result[i - 1] + nums[i]
        }
        return result
    }
}

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

Задача: 489. Robot Room Cleaner
Сложность: hard

Вы управляете роботом в комнате, представленной бинарной сеткой m x n, где 0 — стена, а 1 — пустая ячейка.
Робот начинает в неизвестном месте, гарантированно пустом. У вас нет доступа к сетке, но вы можете перемещать робота через предоставленный API Robot.
Роботу нужно очистить всю комнату (т.е. все пустые ячейки). Он может двигаться вперед, поворачивать налево или направо на 90 градусов.
Если робот наталкивается на стену, его датчик препятствия обнаруживает это, и он остается на текущей ячейке.

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

interface Robot {
  // возвращает true, если следующая ячейка открыта и робот перемещается в эту ячейку.
  // возвращает false, если следующая ячейка является препятствием и робот остается на текущей ячейке.
  boolean move();

  // Робот останется на той же ячейке после вызова turnLeft/turnRight.
  // Каждый поворот составляет 90 градусов.
  void turnLeft();
  void turnRight();

  // Очистить текущую ячейку.
  void clean();
}

Пример:

Input: room = [[1,1,1,1,1,0,1,1],[1,1,1,1,1,0,1,1],[1,0,1,1,1,1,1,1],[0,0,0,1,0,0,0,0],[1,1,1,1,1,1,1,1]], row = 1, col = 3
Output: Robot cleaned all rooms.
Explanation: All grids in the room are marked by either 0 or 1.
0 means the cell is blocked, while 1 means the cell is accessible.
The robot initially starts at the position of row=1, col=3.
From the top left corner, its position is one row below and three columns right.

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

1⃣Пометьте текущую ячейку как посещенную и очистите её.

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

3⃣Если движение невозможно (стена или посещенная ячейка), поверните направо и попробуйте снова, возвращаясь назад, если необходимо.

😎 Решение:

class Solution {
    private lateinit var robot: Robot
    private val visited = mutableSetOf<Pair<Int, Int>>()
    private val directions = listOf(Pair(-1, 0), Pair(0, 1), Pair(1, 0), Pair(0, -1))

    private fun goBack() {
        robot.turnRight()
        robot.turnRight()
        robot.move()
        robot.turnRight()
        robot.turnRight()
    }

    private fun backtrack(row: Int, col: Int, d: Int) {
        visited.add(Pair(row, col))
        robot.clean()
        for (i in 0..3) {
            val newD = (d + i) % 4
            val newRow = row + directions[newD].first
            val newCol = col + directions[newD].second
            if (!visited.contains(Pair(newRow, newCol)) && robot.move()) {
                backtrack(newRow, newCol, newD)
                goBack()
            }
            robot.turnRight()
        }
    }

    fun cleanRoom(robot: Robot) {
        this.robot = robot
        backtrack(0, 0, 0)
    }
}

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

Задача: 341. Flatten Nested List Iterator
Сложность: medium

Вам дан вложенный список целых чисел nestedList. Каждый элемент либо является целым числом, либо списком, элементы которого также могут быть целыми числами или другими списками. Реализуйте итератор для его развёртки.

Реализуйте класс NestedIterator:

NestedIterator(List<NestedInteger> nestedList) Инициализирует итератор вложенным списком nestedList.
int next() Возвращает следующий целый элемент вложенного списка.
boolean hasNext() Возвращает true, если в вложенном списке еще остались целые числа, и false в противном случае.

Пример:

Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

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

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

2⃣Метод next()
Возвращает следующий целый элемент из стека или очереди. Если текущий элемент является списком, развёртывайте его и добавляйте элементы в стек.

3⃣Метод hasNext()
Проверяет, есть ли в стеке или очереди оставшиеся целые элементы. Если на вершине стека находится список, развёртывайте его до тех пор, пока не встретится целый элемент.

😎 Решение:

class NestedIterator(nestedList: List<NestedInteger>) : Iterator<Int> {
    private val stack: Deque<NestedInteger> = ArrayDeque()
    
    init {
        flatten(nestedList)
    }
    
    private fun flatten(nestedList: List<NestedInteger>) {
        for (ni in nestedList.reversed()) {
            stack.push(ni)
        }
    }
    
    override fun next(): Int {
        return stack.pop().getInteger()
    }
    
    override fun hasNext(): Boolean {
        while (stack.isNotEmpty() && !stack.peek().isInteger()) {
            flatten(stack.pop().getList())
        }
        return stack.isNotEmpty()
    }
}

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

Задача: 476. Number Complement
Сложность: easy

Дополнение целого числа — это число, которое получается при замене всех 0 на 1 и всех 1 на 0 в его двоичном представлении.

Например, целое число 5 в двоичной системе — "101", и его дополнение — "010", что соответствует целому числу 2. Дано целое число num, верните его дополнение.

Пример:

Input: num = 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

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

1⃣Вычислите длину в битах входного числа: l=⌊log 2 (num)⌋+1.

2⃣Постройте битовую маску из 1-битов длины l: bitmask=(1≪l)−1.

3⃣Верните результат операции XOR числа и битовой маски: num⊕bitmask num⊕bitmask.

😎 Решение:

class Solution {
    fun findComplement(num: Int): Int {
        var bitmask = num
        bitmask = bitmask or (bitmask shr 1)
        bitmask = bitmask or (bitmask shr 2)
        bitmask = bitmask or (bitmask shr 4)
        bitmask = bitmask or (bitmask shr 8)
        bitmask = bitmask or (bitmask shr 16)
        return bitmask xor num
    }
}

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

Задача: 940. Distinct Subsequences II
Сложность: hard

Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7. Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (Например, "ace" является подпоследовательностью "abcde", а "aec" - нет.

Пример:

Input: s = "abc"
Output: 7

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

1⃣Определить матрицу DP, где dp[i][j] будет хранить количество подпоследовательностей строки s с длиной i, оканчивающихся символом j.

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

3⃣Вернуть сумму всех значений в DP по модулю 10^9 + 7.

😎 Решение:

class Solution {
    fun countSubsequences(s: String): Int {
        val MOD = 1000000007
        val dp = IntArray(26)
        for (c in s) {
            val index = c - 'a'
            dp[index] = (dp.sum() + 1) % MOD
        }
        return dp.sum() % MOD
    }
}

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