Задача: 289. Game of Life
Сложность: medium

Согласно статье Википедии: "Игра Жизнь, также известная просто как Жизнь, — это клеточный автомат, созданный британским математиком Джоном Хортоном Конуэем в 1970 году."

Доска состоит из сетки клеток размером m x n, где каждая клетка имеет начальное состояние: живая (представляется числом 1) или мёртвая (представляется числом 0). Каждая клетка взаимодействует с восемью соседями (по горизонтали, вертикали и диагоналям) согласно следующим четырём правилам (взято из вышеупомянутой статьи Википедии):

Любая живая клетка с менее чем двумя живыми соседями умирает, как будто из-за недостатка населения.
Любая живая клетка с двумя или тремя живыми соседями остаётся живой до следующего поколения.
Любая живая клетка с более чем тремя живыми соседями умирает, как будто из-за перенаселения.
Любая мёртвая клетка с ровно тремя живыми соседями становится живой, как будто вследствие размножения.
Следующее состояние создаётся путем одновременного применения вышеупомянутых правил ко всем клеткам в текущем состоянии, где рождения и смерти происходят одновременно. Дано текущее состояние сетки m x n, верните следующее состояние.

Пример:

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

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

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

2⃣Применение правил:
На основе количества живых соседей и текущего состояния клетки примените правила игры:
Любая живая клетка с менее чем двумя живыми соседями умирает (становится -1).
Любая живая клетка с двумя или тремя живыми соседями остаётся живой (без изменений).
Любая живая клетка с более чем тремя живыми соседями умирает (становится -1).
Любая мёртвая клетка с ровно тремя живыми соседями становится живой (становится 2).

3⃣Обновление доски:
Пройдите через доску ещё раз и обновите состояния клеток:
Если значение клетки больше 0, установите её в 1 (живая).
Если значение клетки меньше или равно 0, установите её в 0 (мёртвая).

😎 Решение:

class Solution {
    fun gameOfLife(board: Array<IntArray>) {
        val neighbors = intArrayOf(0, 1, -1)
        val rows = board.size
        val cols = board[0].size

        for (row in 0 until rows) {
            for (col in 0 until cols) {
                var liveNeighbors = 0
                for (i in neighbors) {
                    for (j in neighbors) {
                        if (!(i == 0 && j == 0)) {
                            val r = row + i
                            val c = col + j
                            if (r in 0 until rows && c in 0 until cols && Math.abs(board[r][c]) == 1) {
                                liveNeighbors++
                            }
                        }
                    }
                }

                if (board[row][col] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
                    board[row][col] = -1
                }
                if (board[row][col] == 0 && liveNeighbors == 3) {
                    board[row][col] = 2
                }
            }
        }

        for (row in 0 until rows) {
            for (col in 0 until cols) {
                board[row][col] = if (board[row][col] > 0) 1 else 0
            }
        }
    }
}

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

Задача: 392. Is Subsequence
Сложность: easy

Даны две строки s и t. Верните true, если s является подпоследовательностью t, иначе верните false.

Подпоследовательность строки — это новая строка, которая формируется из исходной строки путем удаления некоторых (возможно, ни одного) символов без нарушения относительных позиций оставшихся символов. (например, "ace" является подпоследовательностью "abcde", тогда как "aec" не является).

Пример:

Input: s = "abc", t = "ahbgdc"
Output: true

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

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

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

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

😎 Решение:

class Solution {
    fun isSubsequence(s: String, t: String): Boolean {
        val leftBound = s.length
        val rightBound = t.length
        var pLeft = 0
        var pRight = 0

        while (pLeft < leftBound && pRight < rightBound) {
            if (s[pLeft] == t[pRight]) {
                pLeft++
            }
            pRight++
        }
        return pLeft == leftBound
    }
}

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

Задача: 672. Bulb Switcher II
Сложность: medium

Есть комната с n лампочками, пронумерованными от 1 до n, которые изначально все включены, и четыре кнопки на стене. Каждая из четырех кнопок имеет разную функциональность:

Кнопка 1: Переключает состояние всех лампочек.
Кнопка 2: Переключает состояние всех лампочек с четными номерами (т.е. 2, 4, ...).
Кнопка 3: Переключает состояние всех лампочек с нечетными номерами (т.е. 1, 3, ...).
Кнопка 4: Переключает состояние всех лампочек с номером j = 3k + 1, где k = 0, 1, 2, ... (т.е. 1, 4, 7, 10, ...).
Необходимо сделать ровно presses нажатий кнопок. Для каждого нажатия можно выбрать любую из четырех кнопок для нажатия.

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

Пример:

Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2

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

1⃣Рассчитаем возможные множества остатков: то есть какие множества c_i = f_i (mod 2) возможны.

2⃣Так как c_i ≡ f_i и c_i ≤ f_i, если ∑f_i ≠ ∑c_i, или если ∑f_i < ∑c_i, это невозможно. В противном случае это возможно простым построением: выполните операции, указанные c_i, затем выполните операцию номер 1 с четным числом оставшихся операций.

3⃣Для каждого возможного множества остатков симулируем и запоминаем, как будут выглядеть первые 6 лампочек, сохраняя это в структуре Set. В конце возвращаем размер этого множества.

😎 Решение:

class Solution {
    fun flipLights(n: Int, m: Int): Int {
        val seen = mutableSetOf<Int>()
        val n = minOf(n, 6)
        val shift = maxOf(0, 6 - n)
        for (cand in 0 until 16) {
            val bcount = Integer.bitCount(cand)
            if (bcount % 2 == m % 2 && bcount <= m) {
                var lights = 0
                if ((cand shr 0 and 1) > 0) lights = lights xor (0b111111 shr shift)
                if ((cand shr 1 and 1) > 0) lights = lights xor (0b010101 shr shift)
                if ((cand shr 2 and 1) > 0) lights = lights xor (0b101010 shr shift)
                if ((cand shr 3 and 1) > 0) lights = lights xor (0b100100 shr shift)
                seen.add(lights)
            }
        }
        return seen.size
    }
}

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

Задача: 1382. Balance a Binary Search Tree
Сложность: medium

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

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

Пример:

Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2] is also correct.

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

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

2⃣Выполнение обхода в порядке возрастания. Обойдите бинарное дерево поиска (BST) и заполните список inorder значениями узлов в отсортированном порядке.

3⃣Перестроение сбалансированного BST. Определите рекурсивную функцию createBalancedBST, которая принимает список inorder, начальный индекс и конечный индекс в качестве параметров. Если начальный индекс больше конечного, верните null (или эквивалент). Вычислите средний индекс как середину текущего диапазона. Создайте новый узел дерева со значением в среднем индексе. Рекурсивно создайте левое поддерево, используя левую половину текущего диапазона. Рекурсивно создайте правое поддерево, используя правую половину текущего диапазона. Верните корень вновь построенного сбалансированного BST.

😎 Решение:

class Solution {
    fun balanceBST(root: TreeNode?): TreeNode? {
        if (root == null) return null

        val vineHead = TreeNode(0)
        vineHead.right = root
        var current: TreeNode? = vineHead

        while (current?.right != null) {
            if (current.right!!.left != null) {
                rightRotate(current, current.right)
            } else {
                current = current.right
            }
        }

        var nodeCount = 0
        current = vineHead.right
        while (current != null) {
            nodeCount++
            current = current.right
        }

        var m = Math.pow(2.0, Math.floor(Math.log((nodeCount + 1).toDouble()) / Math.log(2.0))).toInt() - 1
        makeRotations(vineHead, nodeCount - m)
        while (m > 1) {
            m /= 2
            makeRotations(vineHead, m)
        }

        return vineHead.right
    }

    private fun rightRotate(parent: TreeNode?, node: TreeNode?) {
        val tmp = node!!.left
        node.left = tmp!!.right
        tmp.right = node
        parent!!.right = tmp
    }

    private fun leftRotate(parent: TreeNode?, node: TreeNode?) {
        val tmp = node!!.right
        node.right = tmp!!.left
        tmp.left = node
        parent!!.right = tmp
    }

    private fun makeRotations(vineHead: TreeNode?, count: Int) {
        var current = vineHead
        for (i in 0 until count) {
            val tmp = current!!.right
            leftRotate(current, tmp)
            current = current.right
        }
    }
}

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

Задача: 605. Can Place Flowers
Сложность: Easy

У вас есть длинная клумба, на которой некоторые участки засажены, а некоторые нет. Однако цветы нельзя сажать на соседних участках.

Дан целочисленный массив flowerbed, содержащий 0 и 1, где 0 означает пустой участок, а 1 — занятый участок, и целое число n. Верните true, если n новых цветов можно посадить на клумбе, не нарушая правила о соседних цветах, и false в противном случае.

Пример:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: true

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

1⃣Решение очень простое. Мы можем определить максимальное количество дополнительных цветов, count, которые можно посадить для данного расположения клумбы. Для этого мы проходим по всем элементам массива flowerbed и находим те элементы, которые равны 0 (означает пустую позицию).

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

3⃣Если полученное количество count больше или равно n, требуемому количеству цветов для посадки, мы можем посадить n цветов на пустые места, иначе - нет.

😎 Решение:

class Solution {
    fun canPlaceFlowers(flowerbed: IntArray, n: Int): Boolean {
        var count = 0
        for (i in flowerbed.indices) {
            if (flowerbed[i] == 0) {
                val emptyLeft = i == 0 || flowerbed[i - 1] == 0
                val emptyRight = i == flowerbed.size - 1 || flowerbed[i + 1] == 0
                if (emptyLeft && emptyRight) {
                    flowerbed[i] = 1
                    count++
                }
            }
        }
        return count >= n
    }
}

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

Задача: 924. Minimize Malware Spread
Сложность: hard

Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока не останется ни одного узла, который можно было бы заразить таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим из initial ровно один узел. Верните тот узел, удаление которого минимизирует M(initial). Если можно удалить несколько узлов, чтобы минимизировать M(initial), верните такой узел с наименьшим индексом. Обратите внимание, что если узел был удален из начального списка зараженных узлов, он все равно может быть заражен позже из-за распространения вредоносного ПО.

Пример:

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20

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

1⃣Определить количество зараженных узлов после распространения вредоносного ПО для исходного списка initial.

2⃣Для каждого узла в initial удалить его и вычислить количество зараженных узлов после распространения вредоносного ПО.

3⃣Найти узел, удаление которого минимизирует количество зараженных узлов. Если есть несколько таких узлов, выбрать узел с наименьшим индексом.

😎 Решение:

class Solution {
    fun minMalwareSpread(graph: Array<IntArray>, initial: IntArray): Int {
        val n = graph.size
        val initialSet = initial.toHashSet()
        initial.sort()
        var minInfected = Int.MAX_VALUE
        var bestNode = initial[0]
        
        for (node in initial) {
            val infected = initialSet.toHashSet()
            infected.remove(node)
            for (i in initialSet) {
                if (i != node) {
                    dfs(graph, i, infected)
                }
            }
            if (infected.size < minInfected) {
                minInfected = infected.size
                bestNode = node
            }
        }
        
        return bestNode
    }
    
    private fun dfs(graph: Array<IntArray>, node: Int, infected: MutableSet<Int>) {
        for (neighbor in graph.indices) {
            if (graph[node][neighbor] == 1 && neighbor !in infected) {
                infected.add(neighbor)
                dfs(graph, neighbor, infected)
            }
        }
    }
}

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

Задача: 1091. Shortest Path in Binary Matrix
Сложность: medium

Дан бинарный матричный массив grid размером n x n. Верните длину самого короткого чистого пути в матрице. Если чистого пути не существует, верните -1.

Чистый путь в бинарной матрице — это путь из верхнего левого угла (т.е. (0, 0)) в нижний правый угол (т.е. (n - 1, n - 1)), такой что:

Все посещенные клетки пути равны 0.
Все соседние клетки пути соединены по 8 направлениям (т.е. они различны и имеют общую сторону или угол).
Длина чистого пути — это количество посещенных клеток этого пути.

Пример:

Input: grid = [[0,1],[1,0]]
Output: 2

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

1⃣Проверить, что начальная и конечная клетки открыты (равны 0). Если нет, вернуть -1.

2⃣Выполнить поиск в ширину (BFS) из начальной клетки, добавляя в очередь соседние клетки, если они открыты и еще не посещены. Обновлять длину пути для каждой клетки.

3⃣Если достигнута конечная клетка, вернуть длину пути. Если очередь пуста и конечная клетка не достигнута, вернуть -1.

😎 Решение:

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

    fun shortestPathBinaryMatrix(grid: Array<IntArray>): Int {
        if (grid[0][0] != 0 || grid[grid.size - 1][grid[0].size - 1] != 0) {
            return -1
        }

        val queue: Queue<Pair<Int, Int>> = LinkedList()
        queue.add(Pair(0, 0))
        grid[0][0] = 1

        while (queue.isNotEmpty()) {
            val (row, col) = queue.poll()
            val distance = grid[row][col]
            if (row == grid.size - 1 && col == grid[0].size - 1) {
                return distance
            }
            for (direction in directions) {
                val newRow = row + direction[0]
                val newCol = col + direction[1]
                if (newRow in 0 until grid.size && newCol in 0 until grid[0].size && grid[newRow][newCol] == 0) {
                    queue.add(Pair(newRow, newCol))
                    grid[newRow][newCol] = distance + 1
                }
            }
        }
        return -1
    }
}

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

Задача: 1214. Two Sum BSTs
Сложность: medium

Даны корни двух бинарных деревьев поиска, root1 и root2, верните true, если и только если существует узел в первом дереве и узел во втором дереве, значения которых в сумме равны заданному целому числу target.

Пример:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18
Output: false

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

1⃣Создайте два пустых множества node_set1 и node_set2. Выполните обход дерева root1, добавляя значения каждого узла в node_set1, и выполните обход дерева root2, добавляя значения каждого узла в node_set2.

2⃣Итерация по элементам в node_set1: для каждого элемента value1 проверяйте, находится ли target - value1 в node_set2.

3⃣Если target - value1 находится в node_set2, верните true. Если после завершения итерации не найдено ни одной подходящей пары, верните false.

😎 Решение:

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

class Solution {
    private fun dfs(node: TreeNode?, nodeSet: MutableSet<Int>) {
        if (node == null) return
        dfs(node.left, nodeSet)
        nodeSet.add(node.`val`)
        dfs(node.right, nodeSet)
    }

    fun twoSumBSTs(root1: TreeNode?, root2: TreeNode?, target: Int): Boolean {
        val nodeSet1 = mutableSetOf<Int>()
        val nodeSet2 = mutableSetOf<Int>()
        dfs(root1, nodeSet1)
        dfs(root2, nodeSet2)
        
        for (value1 in nodeSet1) {
            if (nodeSet2.contains(target - value1)) {
                return true
            }
        }
        
        return false
    }
}

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

Задача: 1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
Сложность: medium

Дан прямоугольный торт размером h x w и два массива целых чисел horizontalCuts и verticalCuts, где:
horizontalCuts[i] — это расстояние от верхнего края прямоугольного торта до i-го горизонтального разреза,
verticalCuts[j] — это расстояние от левого края прямоугольного торта до j-го вертикального разреза.
Верните максимальную площадь кусочка торта после разрезания в каждом горизонтальном и вертикальном положении, указанном в массивах horizontalCuts и verticalCuts. Так как ответ может быть очень большим числом, верните его по модулю 10^9 + 7.

Пример:

Input: h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
Output: 4 
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts.
 After you cut the cake, the green piece of cake has the maximum area.

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

1⃣Отсортируйте массивы horizontalCuts и verticalCuts в порядке возрастания. Найдите максимальную высоту, учитывая верхний и нижний края торта, и пройдитесь по массиву horizontalCuts, чтобы найти максимальное расстояние между соседними разрезами.

2⃣Найдите максимальную ширину, учитывая левый и правый края торта, и пройдитесь по массиву verticalCuts, чтобы найти максимальное расстояние между соседними разрезами.

3⃣Верните произведение максимальной высоты и максимальной ширины, взятое по модулю 10^9+7.

😎 Решение:

class Solution {
    fun maxArea(h: Int, w: Int, horizontalCuts: IntArray, verticalCuts: IntArray): Int {
        horizontalCuts.sort()
        verticalCuts.sort()
        
        var maxHeight = maxOf(horizontalCuts[0], h - horizontalCuts.last())
        for (i in 1 until horizontalCuts.size) {
            maxHeight = maxOf(maxHeight, horizontalCuts[i] - horizontalCuts[i - 1])
        }
        
        var maxWidth = maxOf(verticalCuts[0], w - verticalCuts.last())
        for (i in 1 until verticalCuts.size) {
            maxWidth = maxOf(maxWidth, verticalCuts[i] - verticalCuts[i - 1])
        }
        
        return ((maxHeight.toLong() * maxWidth.toLong()) % 1000000007).toInt()
    }

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

Задача: 1200. Minimum Absolute Difference
Сложность: easy

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

Верните список пар в порядке возрастания (по отношению к парам), каждая пара [a, b] следует условиям:
a, b из arr
a < b
b - a равна минимальной абсолютной разнице между любыми двумя элементами в arr

Пример:

Input: arr = [4,2,1,3]
Output: [[1,2],[2,3],[3,4]]
Explanation: The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.

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

1⃣Инициализация вспомогательного массива:
Найдите минимальный элемент minElement и максимальный элемент maxElement в массиве arr.
Инициализируйте вспомогательный массив line размером maxElement - minElement + 1 и установите смещение shift равным -minElement.
Пройдите по массиву arr и для каждого элемента value увеличьте значение в индексе value + shift на 1.

2⃣Поиск минимальной абсолютной разницы:
Пройдите по вспомогательному массиву line, начиная с индекса, соответствующего минимальному элементу.
Проверьте значения на каждом индексе curr:
- если line[curr] равно 0, пропустите этот индекс.
- если line[curr] равно 1, сравните абсолютную разницу текущей пары currPairDiff с минимальной найденной разницей minPairDiff.
- если currPairDiff больше minPairDiff, продолжайте.
- если currPairDiff равно minPairDiff, добавьте эту пару в список ответов.
- если currPairDiff меньше minPairDiff, очистите список ответов, добавьте эту пару и обновите minPairDiff.

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

😎 Решение:

class Solution {
    fun minimumAbsDifference(arr: IntArray): List<List<Int>> {
        arr.sort()
        var minDiff = Int.MAX_VALUE
        val result = mutableListOf<List<Int>>()
        
        for (i in 1 until arr.size) {
            val diff = arr[i] - arr[i - 1]
            if (diff < minDiff) {
                minDiff = diff
                result.clear()
                result.add(listOf(arr[i - 1], arr[i]))
            } else if (diff == minDiff) {
                result.add(listOf(arr[i - 1], arr[i]))
            }
        }
        
        return result
    }
}

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

Задача: 1095. Find in Mountain Array
Сложность: hard

Массив arr является горным массивом тогда и только тогда, когда:

Длина массива arr >= 3.
Существует некоторое i с 0 < i < arr.length - 1 такое, что:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Дан горный массив mountainArr, верните минимальный индекс, такой что mountainArr.get(index) == target. Если такого индекса не существует, верните -1.

Вы не можете напрямую обращаться к массиву. Вы можете использовать интерфейс MountainArray:

MountainArray.get(k) возвращает элемент массива на индексе k (индексация начинается с 0).
MountainArray.length() возвращает длину массива.
Решения, использующие более 100 вызовов MountainArray.get, будут оценены как неправильные. Также любые решения, которые пытаются обойти ограничение, будут дисквалифицированы.

Пример:

Input: array = [1,2,3,4,5,3,1], target = 3
Output: 2
Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.

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

1⃣Найти индекс пика: Инициализируем два указателя low и high, где low начинается с 1, а high — с длины массива минус 2. Используем бинарный поиск для нахождения пикового элемента: если элемент в середине меньше следующего элемента, то пиковый элемент находится справа, иначе он находится слева. Продолжаем сужать диапазон поиска до тех пор, пока low не станет равным high. Это и будет индекс пика.

2⃣Бинарный поиск в возрастающей части массива: Устанавливаем указатели low и high для поиска в диапазоне от 0 до пикового индекса. Проводим обычный бинарный поиск: если значение в середине меньше целевого значения, перемещаем low вправо, иначе перемещаем high влево. По завершении поиска проверяем, равно ли значение по индексу low целевому значению. Если да, возвращаем индекс, иначе продолжаем.

3⃣Бинарный поиск в убывающей части массива: Устанавливаем указатели low и high для поиска в диапазоне от пикового индекса плюс 1 до конца массива. Проводим бинарный поиск, но с учетом убывающей последовательности: если значение в середине больше целевого значения, перемещаем low вправо, иначе перемещаем high влево. По завершении поиска проверяем, равно ли значение по индексу low целевому значению. Если да, возвращаем индекс. Если значение не найдено, возвращаем -1.

😎 Решение:

class Solution {
    fun findInMountainArray(target: Int, mountainArr: MountainArray): Int {
        val length = mountainArr.length()

        var low = 1
        var high = length - 2
        while (low != high) {
            val mid = (low + high) / 2
            if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
                low = mid + 1
            } else {
                high = mid
            }
        }
        val peak = low

        low = 0
        high = peak
        while (low < high) {
            val mid = (low + high) / 2
            if (mountainArr.get(mid) < target) {
                low = mid + 1
            } else {
                high = mid
            }
        }
        if (mountainArr.get(low) == target) {
            return low
        }

        low = peak + 1
        high = length - 1
        while (low < high) {
            val mid = (low + high) / 2
            if (mountainArr.get(mid) > target) {
                low = mid + 1
            } else {
                high = mid
            }
        }
        if (mountainArr.get(low) == target) {
            return low
        }

        return -1
    }
}

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

Задача: 1048. Longest String Chain
Сложность: easy

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

Например, "abc" является предшественником "abac", а "cba" не является предшественником "bcad". Цепочка слов - это последовательность слов [word1, word2, ..., wordk] с k >= 1, где word1 является предшественником word2, word2 является предшественником word3 и так далее. Одиночное слово тривиально является цепочкой слов с k == 1. Верните длину самой длинной возможной цепочки слов со словами, выбранными из заданного списка слов.

Пример:

Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4

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

1⃣Отсортируй список слов по длине.

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

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

😎 Решение:

fun longestStrChain(words: Array<String>): Int {
    words.sortBy { it.length }
    val dp = mutableMapOf<String, Int>()
    var longestChain = 1
    
    for (word in words) {
        dp[word] = 1
        for (i in word.indices) {
            val predecessor = word.removeRange(i, i + 1)
            if (predecessor in dp) {
                dp[word] = maxOf(dp[word]!!, dp[predecessor]!! + 1)
            }
        }
        longestChain = maxOf(longestChain, dp[word]!!)
    }
    
    return longestChain
}

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

Задача: 1429. First Unique Number
Сложность: medium

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

Реализуйте класс FirstUnique:
- FirstUnique(int[] nums) Инициализирует объект числами в очереди.
- int showFirstUnique() возвращает значение первого уникального элемента в очереди и возвращает -1, если такого элемента нет.
- void add(int value) вставляет значение в очередь.

Пример:

Input: 
["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"]
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
Output: 
[null,2,null,2,null,3,null,-1]
Explanation: 
FirstUnique firstUnique = new FirstUnique([2,3,5]);
firstUnique.showFirstUnique(); // return 2
firstUnique.add(5);            // the queue is now [2,3,5,5]
firstUnique.showFirstUnique(); // return 2
firstUnique.add(2);            // the queue is now [2,3,5,5,2]
firstUnique.showFirstUnique(); // return 3
firstUnique.add(3);            // the queue is now [2,3,5,5,2,3]
firstUnique.showFirstUnique(); // return -1

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

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

2⃣Метод showFirstUnique возвращает значение первого уникального элемента в очереди, если таковой существует, или -1, если уникальных элементов нет.

3⃣Метод add добавляет новое значение в очередь. Если значение уже было добавлено ранее, обновляет его статус уникальности и удаляет его из множества уникальных значений, если оно больше не уникально.

😎 Решение:

class FirstUnique(nums: IntArray) {
    private val setQueue = LinkedHashSet<Int>()
    private val isUnique = mutableMapOf<Int, Boolean>()

    init {
        nums.forEach { add(it) }
    }

    fun showFirstUnique(): Int {
        return setQueue.firstOrNull() ?: -1
    }

    fun add(value: Int) {
        when (isUnique[value]) {
            null -> {
                isUnique[value] = true
                setQueue.add(value)
            }
            true -> {
                isUnique[value] = false
                setQueue.remove(value)
            }
        }
    }
}

// LinkedHashSet implementation in Kotlin
class LinkedHashSet<T> {
    private val array = mutableListOf<T>()
    private val set = mutableSetOf<T>()

    fun add(value: T) {
        if (set.add(value)) {
            array.add(value)
        }
    }

    fun remove(value: T) {
        if (set.remove(value)) {
            array.remove(value)
        }
    }

    fun firstOrNull(): T? = array.firstOrNull()
}

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

Задача: 517. Super Washing Machines
Сложность: hard

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

За один ход вы можете выбрать любые m (1 <= m <= n) стиральные машины и одновременно передать одно платье из каждой выбранной машины в одну из её соседних стиральных машин.

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

Пример:

Input: machines = [1,0,5]
Output: 3
Explanation:
1st move:    1     0 <-- 5    =>    1     1     4
2nd move:    1 <-- 1 <-- 4    =>    2     1     3
3rd move:    2     1 <-- 3    =>    2     2     2

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

1⃣Проверьте, можно ли решить задачу: длина массива machines должна быть делителем суммы элементов массива machines. Если нет, верните -1. Вычислите количество платьев, которое должно быть в каждой машине: dresses_per_machine = sum(machines) / len(machines). Нормализуйте задачу, заменив количество платьев в каждой машине на количество платьев, которые нужно удалить из этой машины (может быть отрицательное значение).

2⃣Инициализируйте переменные curr_sum, max_sum и res нулем. Итеративно пройдитесь по всем машинам m в массиве machines, обновляя curr_sum и max_sum на каждом шагу: curr_sum += m, max_sum = max(max_sum, abs(curr_sum)).

3⃣Обновляйте результат res на каждом шагу: res = max(res, max_sum, m). Верните res.

😎 Решение:

class Solution {
    fun findMinMoves(machines: IntArray): Int {
        val n = machines.size
        val dressTotal = machines.sum()
        if (dressTotal % n != 0) return -1

        val dressPerMachine = dressTotal / n
        for (i in machines.indices) {
            machines[i] -= dressPerMachine
        }

        var currSum = 0
        var maxSum = 0
        var res = 0
        for (m in machines) {
            currSum += m
            maxSum = maxOf(maxSum, kotlin.math.abs(currSum))
            res = maxOf(res, maxOf(maxSum, m))
        }
        return res
    }
}

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

Задача: 399. Evaluate Division
Сложность: medium

Вам дан массив пар переменных equations и массив вещественных чисел values, где equations[i] = [Ai, Bi] и values[i] представляют уравнение Ai / Bi = values[i]. Каждая Ai или Bi - это строка, представляющая одну переменную. Вам также даны некоторые запросы, где queries[j] = [Cj, Dj] представляет j-й запрос, в котором вы должны найти ответ для Cj / Dj = ?. Верните ответы на все запросы. Если ни один ответ не может быть определен, верните -1.0. Замечание: входные данные всегда действительны. Можно предположить, что вычисление запросов не приведет к делению на ноль и что противоречия нет. Примечание: Переменные, которые не встречаются в списке уравнений, являются неопределенными, поэтому для них ответ не может быть определен.

Пример:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]

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

1⃣Создание графа:
Представьте каждую переменную как узел в графе.
Используйте уравнения для создания ребер между узлами, где каждое ребро имеет вес, равный значению уравнения (Ai / Bi = values[i]).
Создайте также обратные ребра с обратным весом (Bi / Ai = 1 / values[i]).

2⃣Поиск пути:
Для каждого запроса используйте поиск в глубину (DFS) или поиск в ширину (BFS) для поиска пути от Cj до Dj.
Если путь найден, вычислите произведение весов вдоль пути, чтобы найти значение Cj / Dj.
Если путь не найден, верните -1.0.

3⃣Обработка запросов:
Пройдитесь по всем запросам и используйте граф для вычисления результатов каждого запроса.

😎 Решение:

class Solution {
    fun calcEquation(equations: List<List<String>>, values: List<Double>, queries: List<List<String>>): DoubleArray {
        val graph = mutableMapOf<String, MutableMap<String, Double>>()

        for ((i, equation) in equations.withIndex()) {
            val A = equation[0]
            val B = equation[1]
            val value = values[i]
            graph.computeIfAbsent(A) { mutableMapOf() }[B] = value
            graph.computeIfAbsent(B) { mutableMapOf() }[A] = 1.0 / value
        }

        fun bfs(start: String, end: String): Double {
            if (!graph.containsKey(start) || !graph.containsKey(end)) return -1.0
            val queue = ArrayDeque<Pair<String, Double>>()
            queue.add(start to 1.0)
            val visited = mutableSetOf<String>()

            while (queue.isNotEmpty()) {
                val (current, curProduct) = queue.removeFirst()
                if (current == end) return curProduct
                visited.add(current)
                for ((neighbor, value) in graph[current] ?: emptyMap()) {
                    if (neighbor !in visited) {
                        queue.add(neighbor to curProduct * value)
                    }
                }
            }
            return -1.0
        }

        return queries.map { bfs(it[0], it[1]) }.toDoubleArray()
    }
}

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

Задача: 296. Best Meeting Point
Сложность: hard

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

Общее расстояние путешествия — это сумма расстояний между домами друзей и точкой встречи.

Расстояние рассчитывается по Манхэттенскому расстоянию, где distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

Пример:

Input: grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 6
Explanation: Given three friends living at (0,0), (0,4), and (2,2).
The point (0,2) is an ideal meeting point, as the total travel distance of 2 + 2 + 2 = 6 is minimal.
So return 6.

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

1⃣Определение координат домов:
Пройдите по сетке и соберите координаты всех домов (ячейки с значением 1) в два списка: один для координат x и один для координат y.

2⃣Нахождение медианы:
Отсортируйте списки координат x и y.
Найдите медианы в обоих списках. Медианы координат x и y укажут оптимальную точку встречи.

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

😎 Решение:

class Solution {
    fun minTotalDistance(grid: Array<IntArray>): Int {
        var minDistance = Int.MAX_VALUE
        for (row in grid.indices) {
            for (col in grid[0].indices) {
                val distance = search(grid, row, col)
                minDistance = minOf(distance, minDistance)
            }
        }
        return minDistance
    }

    private fun search(grid: Array<IntArray>, row: Int, col: Int): Int {
        val q: ArrayDeque<Triple<Int, Int, Int>> = ArrayDeque()
        q.add(Triple(row, col, 0))
        val m = grid.size
        val n = grid[0].size
        val visited = Array(m) { BooleanArray(n) }
        var totalDistance = 0

        while (q.isNotEmpty()) {
            val (r, c, d) = q.removeFirst()

            if (r < 0 || c < 0 || r >= m || c >= n || visited[r][c]) {
                continue
            }

            if (grid[r][c] == 1) {
                totalDistance += d
            }

            visited[r][c] = true

            q.add(Triple(r + 1, c, d + 1))
            q.add(Triple(r - 1, c, d + 1))
            q.add(Triple(r, c + 1, d + 1))
            q.add(Triple(r, c - 1, d + 1))
        }

        return totalDistance
    }
}

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

⚡️ В сети начали массово сливать курсы и книги известных онлайн школ по айти

Вот отсортированная база с тонной материала (постепенно пополняется):

(363 видео, 87 книги) — Python
(415 видео, 68 книги) — Frontend
(143 видео, 33 книги) — ИБ/Хакинг
(352 видео, 89 книги) — С/С++/C#
(343 видео, 87 книги) — Java/QA
(176 видео, 32 книги) — Git/Linux
(174 видео, 91 книги) — DevOps
(167 видео, 53 книги) — PHP/1С
(227 видео, 83 книги) — SQL/БД
(114 видео, 77 книги) — Сисадмин
(107 видео, 43 книги) — BA/SA
(181 видео, 32 книги) — Go/Rust
(167 видео, 43 книги) — Kotlin/Swift
(112 видео, 24 книги) — Flutter
(137 видео, 93 книги) — DS/ML
(113 видео, 82 книги) — GameDev
(183 видео, 37 книги) — Дизайн
(136 видео, 33 книги) — PM/HR

Скачивать ничего не нужно — все выложили в Telegram

Задача: 374. Guess Number Higher or Lower
Сложность: easy

Мы играем в игру "Угадай число". Правила игры следующие:

Я загадываю число от 1 до n. Вам нужно угадать, какое число я загадал.

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

Вы вызываете предопределенный API int guess(int num), который возвращает один из трех возможных результатов:

-1: Ваше предположение больше загаданного числа (т.е. num > pick).
1: Ваше предположение меньше загаданного числа (т.е. num < pick).
0: Ваше предположение равно загаданному числу (т.е. num == pick).
Верните загаданное число.

Пример:

Input: n = 10, pick = 6
Output: 6

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

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

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

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

😎 Решение:

class Solution : GuessGame() {
    fun guessNumber(n: Int): Int {
        var low = 1
        var high = n
        while (low <= high) {
            val mid = low + (high - low) / 2
            val res = guess(mid)
            if (res == 0)
                return mid
            else if (res < 0)
                high = mid - 1
            else
                low = mid + 1
        }
        return -1
    }
}

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

Задача: 1461. Check If a String Contains All Binary Codes of Size K
Сложность: medium

Дана бинарная строка s и целое число k, верните true, если каждый бинарный код длины k является подстрокой s. В противном случае верните false.

Пример:

Input: s = "00110110", k = 2
Output: true
Explanation: The binary codes of length 2 are "00", "01", "10" and "11". They can be all found as substrings at indices 0, 1, 3 and 2 respectively.

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

1⃣Определите количество возможных двоичных кодов длины k.

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

3⃣Возвращайте true, если все возможные коды найдены, иначе false.

😎 Решение:

class Solution {
    fun hasAllCodes(s: String, k: Int): Boolean {
        val need = 1 shl k
        val got = BooleanArray(need)
        val allOne = need - 1
        var hashVal = 0
        
        for (i in s.indices) {
            hashVal = ((hashVal shl 1) and allOne) or (s[i] - '0')
            if (i >= k - 1 && !got[hashVal]) {
                got[hashVal] = true
                if (got.all { it }) {
                    return true
                }
            }
        }
        return false
    }
}

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

Задача: 1466. Reorder Routes to Make All Paths Lead to the City Zero
Сложность: medium

Дано n городов, пронумерованных от 0 до n - 1, и n - 1 дорог, таких, что существует только один путь между двумя различными городами (эта сеть образует дерево). В прошлом году Министерство транспорта решило направить дороги в одном направлении, потому что они слишком узкие.

Дороги представлены массивом connections, где connections[i] = [ai, bi] представляет дорогу от города ai до города bi.
В этом году в столице (город 0) будет большое событие, и многие люди хотят приехать в этот город.
Ваша задача состоит в том, чтобы переориентировать некоторые дороги так, чтобы каждый город мог посетить город 0. Верните минимальное количество изменённых дорог.

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

Пример:

Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

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

1⃣Создайте переменную count для подсчета количества рёбер, которые необходимо изменить. Инициализируйте её нулём. Создайте список смежности adj, который содержит список пар целых чисел так, чтобы adj[node] содержал всех соседей node в форме (neighbor, sign), где neighbor - соседний узел, а sign обозначает направление ребра (оригинальное или искусственное).

2⃣Начните обход в глубину (DFS). Используйте функцию dfs для выполнения обхода. В каждом вызове передавайте параметры node, parent и adj. Начните с узла 0 и parent равным -1.

3⃣Перебирайте всех соседей узла с помощью adj[node]. Для каждого neighbor, sign в adj[node], проверьте, равен ли neighbor родителю. Если равен, не посещайте его снова. Если neighbor не равен parent, выполните count += sign и рекурсивно вызовите dfs с node = neighbor и parent = node. По завершении обхода DFS, в count будет содержаться количество рёбер, которые необходимо изменить. Верните count.

😎 Решение:

class Solution {
    var count = 0

    fun dfs(node: Int, parent: Int, adj: Map<Int, List<Pair<Int, Int>>>) {
        adj[node]?.forEach { (neighbor, sign) ->
            if (neighbor != parent) {
                count += sign
                dfs(neighbor, node, adj)
            }
        }
    }

    fun minReorder(n: Int, connections: Array<IntArray>): Int {
        val adj = mutableMapOf<Int, MutableList<Pair<Int, Int>>>()
        for (connection in connections) {
            adj.computeIfAbsent(connection[0]) { mutableListOf() }.add(connection[1] to 1)
            adj.computeIfAbsent(connection[1]) { mutableListOf() }.add(connection[0] to 0)
        }
        dfs(0, -1, adj)
        return count
    }
}

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