Задача: 1038. Binary Search Tree to Greater Sum Tree
Сложность: medium

Получив корень двоичного дерева поиска (BST), преобразуйте его в большее дерево таким образом, чтобы каждый ключ исходного BST был заменен на исходный ключ плюс сумма всех ключей, превышающих исходный ключ в BST. Напомним, что двоичное дерево поиска - это дерево, удовлетворяющее следующим ограничениям: левое поддерево узла содержит только узлы с ключами меньше, чем ключ узла. Правое поддерево узла содержит только узлы с ключами больше, чем ключ узла. И левое, и правое поддеревья должны быть двоичными деревьями поиска.

Пример:

Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

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

1⃣Обратный обход in-order:
Пройдите по дереву в порядке "правый, корень, левый" (обратный in-order обход). Это обеспечит посещение узлов в порядке убывания их значений.

2⃣Накопление суммы:
Во время обхода поддерживайте переменную для хранения накопленной суммы. На каждом узле добавляйте значение узла к накопленной сумме и обновляйте значение узла этой накопленной суммой.

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

😎 Решение:

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

class Solution {
    private var sum = 0
    
    fun bstToGst(root: TreeNode?): TreeNode? {
        reverseInorder(root)
        return root
    }
    
    private fun reverseInorder(node: TreeNode?) {
        if (node == null) return
        reverseInorder(node.right)
        sum += node.`val`
        node.`val` = sum
        reverseInorder(node.left)
    }
}

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

Ура, друзья! Изиоффер переходит в публичное бета-тестирование!

🎉 Что нового:
🟢Анализ IT собеседований на основе 4500+ реальных интервью
🟢Вопросы из собеседований с вероятностью встречи
🟢Видео-примеры ответов на вопросы от Senior, Middle, Junior грейдов
🟢Пример лучшего ответа
🟢Задачи из собеседований
🟢Тестовые задания
🟢Примеры собеседований
🟢Фильтрация всего контента по грейдам, компаниям
🟢Тренажер подготовки к собеседованию на основе интервальных повторений и флеш карточек
🟡Тренажер "Реальное собеседование" с сценарием вопросов из реальных собеседований (скоро)
🟢Автоотклики на HeadHunter
🟢Закрытое сообщество easyoffer


💎 Акция в честь открытия для первых 500 покупателей:
🚀 Скидка 50% на PRO тариф на 1 год (15000₽ → 7500₽)

🔥 Акция уже стартовала! 👉 https://easyoffer.ru/pro

Задача: 433. Minimum Genetic Mutation
Сложность: medium

Генетическая строка может быть представлена строкой длиной 8 символов, содержащей символы 'A', 'C', 'G' и 'T'.

Предположим, нам нужно исследовать мутацию от генетической строки startGene до генетической строки endGene, где одна мутация определяется как изменение одного символа в генетической строке.

Например, "AACCGGTT" --> "AACCGGTA" является одной мутацией.
Также существует генетический банк bank, который содержит все допустимые генетические мутации. Генетическая строка должна быть в банке, чтобы считаться допустимой.

Даны две генетические строки startGene и endGene и генетический банк bank, верните минимальное количество мутаций, необходимых для мутации от startGene до endGene. Если такой мутации не существует, верните -1.

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

Пример:

Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1

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

1⃣Инициализируйте очередь и множество seen. Очередь будет использоваться для выполнения BFS, а множество seen будет использоваться для предотвращения повторного посещения одного и того же узла. Изначально в очередь и множество должен быть помещен startGene.

2⃣Выполняйте BFS. На каждом узле, если node == endGene, верните количество шагов, пройденных до этого момента. В противном случае, итеративно заменяйте каждый символ в строке на один из "A", "C", "G", "T" для нахождения соседей. Для каждого соседа, если он еще не был посещен и находится в bank, добавьте его в очередь и в множество seen.

3⃣Если BFS завершился и endGene не был найден, задача невыполнима. Верните -1.

😎 Решение:

import java.util.*

class Solution {
    fun minMutation(start: String, end: String, bank: Array<String>): Int {
        val queue: Queue<String> = LinkedList()
        val seen: MutableSet<String> = HashSet()
        queue.offer(start)
        seen.add(start)
        
        var steps = 0
        while (queue.isNotEmpty()) {
            val nodesInQueue = queue.size
            
            for (j in 0 until nodesInQueue) {
                val node = queue.poll()
                
                if (node == end) {
                    return steps
                }
                
                for (c in "ACGT") {
                    for (i in node.indices) {
                        val neighbor = StringBuilder(node)
                        neighbor[i] = c
                        val neighborStr = neighbor.toString()
                        if (!seen.contains(neighborStr) && bank.contains(neighborStr)) {
                            queue.offer(neighborStr)
                            seen.add(neighborStr)
                        }
                    }
                }
            }
            
            steps++
        }
        
        return -1
    }
}

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

Задача: 561. Array Partition
Сложность: easy

Дан массив целых чисел nums из 2n элементов. Разделите эти числа на n пар (a1, b1), (a2, b2), ..., (an, bn) так, чтобы сумма min(ai, bi) для всех i была максимальной. Верните максимальную сумму.

Пример:

Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) are:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.

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

1⃣Отсортируйте массив nums в неубывающем порядке.

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

3⃣Суммируйте выбранные элементы и верните эту сумму.

😎 Решение:

class Solution {
    fun arrayPairSum(nums: IntArray): Int {
        nums.sort()
        var sum = 0
        for (i in nums.indices step 2) {
            sum += nums[i]
        }
        return sum
    }
}

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

Задача: 43. Multiply Strings
Сложность: hard

Даны два неотрицательных целых числа num1 и num2, представленные в виде строк. Верните произведение num1 и num2, также представленное в виде строки.

Примечание: Вы не должны использовать встроенную библиотеку BigInteger или прямо преобразовывать входные данные в целые числа.

Пример:

Input: num1 = "2", num2 = "3"
Output: "6"

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

1⃣Переверните оба числа. Инициализируйте массив ans с (N+M) нулями. Для каждой цифры в secondNumber:
Инициализируйте переменную carry, первоначально равную 0.
Инициализируйте массив (currentResult), который начинается с некоторого количества нулей, основываясь на позиции цифры в secondNumber.

2⃣Для каждой цифры в firstNumber:
Умножьте цифру из secondNumber на цифру из firstNumber и добавьте предыдущий carry к умножению.
Возьмите остаток от деления умножения на 10, чтобы получить последнюю цифру.
Добавьте последнюю цифру в массив currentResult.
Разделите умножение на 10, чтобы получить новое значение для carry.

3⃣После итерации по каждой цифре в первом числе, если carry не равен нулю, добавьте carry в currentResult.
Добавьте currentResult к ans.
Если последняя цифра в ans равна нулю, перед тем как перевернуть ans, необходимо удалить ноль из ans. В противном случае в финальном ответе будет ведущий ноль.
Переверните ans и верните его.

😎 Решение:

class Solution {
    fun multiply(num1: String, num2: String): String {
        if (num1 == "0" || num2 == "0") {
            return "0"
        }

        val firstNumber = num1.reversed()
        val secondNumber = num2.reversed()

        val N = firstNumber.length + secondNumber.length
        val answer = IntArray(N) { 0 }

        for ((index, digit) in secondNumber.withIndex()) {
            val result = multiplyOneDigit(firstNumber, digit, index)
            addStrings(result, answer)
        }

        while (answer.last() == 0 && answer.size > 1) {
            answer.dropLast(1)
        }

        answer.reverse()
        return answer.joinToString(separator = "") { it.toString() }
    }

    private fun multiplyOneDigit(firstNumber: String, digit2: Char, numZeros: Int): IntArray {
        val result = IntArray(firstNumber.length + numZeros + 1) { 0 }
        var carry = 0

        for (i in 0 until numZeros) {
            result[i] = 0
        }

        for ((i, digit1) in firstNumber.withIndex()) {
            val multiplication = Character.getNumericValue(digit1) * Character.getNumericValue(digit2) + carry
            result[i + numZeros] = multiplication % 10
            carry = multiplication / 10
        }

        if (carry != 0) {
            result[firstNumber.length + numZeros] = carry
        }
        return result
    }

    private fun addStrings(result: IntArray, answer: IntArray) {
        var carry = 0
        for (i in result.indices) {
            val sum = (if (i < answer.size) answer[i] else 0) + result[i] + carry
            if (i < answer.size) {
                answer[i] = sum % 10
            } else {
                answer[i] = sum
            }
            carry = sum / 10
        }
        var i = result.size
        while (carry != 0) {
            val sum = (if (i < answer.size) answer[i] else 0) + carry
            if (i < answer.size) {
                answer[i] = sum % 10
            } else {
                answer[i] = sum
            }
            carry = sum / 10
            i++
        }
    }
}

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

Задача: 1271. Hexspeak
Сложность: easy

Десятичное число можно преобразовать в его шестнадцатеричное представление, сначала преобразовав его в прописную шестнадцатеричную строку, а затем заменив все вхождения цифры '0' на букву 'O', а цифры '1' - на букву 'I'. Такое представление допустимо тогда и только тогда, когда оно состоит только из букв набора {'A', 'B', 'C', 'D', 'E', 'F', 'I', 'O'}. Получив строку num, представляющую десятичное целое число n, верните шестнадцатеричное представление n, если оно допустимо, иначе верните "ERROR".

Пример:

Input: num = "257"
Output: "IOI"

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

1⃣Преобразуйте десятичное число в шестнадцатеричную строку в верхнем регистре.

2⃣Замените все вхождения цифры '0' на букву 'O', а цифры '1' на букву 'I'

3⃣Проверьте, что преобразованная строка содержит только допустимые символы. Если это так, верните строку, иначе верните "ERROR".

😎 Решение:

class Solution {
    fun toHexString(num: String): String {
        val hexStr = num.toLong().toString(16).uppercase().replace('0', 'O').replace('1', 'I')
        for (char in hexStr) {
            if (!"ABCDEFIO".contains(char)) {
                return "ERROR"
            }
        }
        return hexStr
    }
}

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

Задача: 841. Keys and Rooms
Сложность: medium

Есть n комнат, пронумерованных от 0 до n - 1, и все комнаты закрыты, кроме комнаты 0. Ваша цель — посетить все комнаты. Однако вы не можете войти в закрытую комнату, не имея ключа от нее.
Когда вы посещаете комнату, вы можете найти в ней набор различных ключей. Каждый ключ имеет номер, указывающий, какую комнату он открывает, и вы можете взять их все с собой, чтобы открыть другие комнаты.

Дан массив rooms, где rooms[i] — это набор ключей, которые вы можете получить, если посетите комнату i. Верните true, если вы можете посетить все комнаты, или false в противном случае.

Пример:

Input: rooms = [[1],[2],[3],[]]
Output: true
Explanation: 
We visit room 0 and pick up key 1.
We then visit room 1 and pick up key 2.
We then visit room 2 and pick up key 3.
We then visit room 3.
Since we were able to visit every room, we return true.

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

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

2⃣Поместите ключ от комнаты 0 в стек и отметьте комнату 0 как посещенную.

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

😎 Решение:

class Solution {
    fun canVisitAllRooms(rooms: List<List<Int>>): Boolean {
        val seen = BooleanArray(rooms.size) { false }
        seen[0] = true
        val stack = Stack<Int>()
        stack.push(0)

        while (stack.isNotEmpty()) {
            val node = stack.pop()
            for (nei in rooms[node]) {
                if (!seen[nei]) {
                    seen[nei] = true
                    stack.push(nei)
                }
            }
        }

        return seen.all { it }
    }
}

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

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

Дана m на n доска символов и список строк words, верните все слова, находящиеся на доске.

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

Пример:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

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

1⃣Постройте структуру Trie из слов в словаре. Trie будет использоваться для процесса сопоставления позже.

2⃣Начните обход доски с каждой ячейки. Если существует слово в словаре, которое начинается с буквы в данной ячейке, начните рекурсивный вызов функции backtracking(cell).

3⃣В функции backtracking(cell) исследуйте соседние ячейки (i.e. neighborCell) вокруг текущей ячейки для следующего рекурсивного вызова backtracking(neighborCell).
На каждом вызове проверяйте, соответствует ли последовательность букв, которую мы прошли до сих пор, какому-либо слову в словаре, используя структуру Trie, построенную в начале.

😎 Решение:

class TrieNode {
    val children = HashMap<Char, TrieNode>()
    var word: String? = null
}

class Solution {
    private lateinit var board: Array<CharArray>
    private val result = ArrayList<String>()

    fun findWords(board: Array<CharArray>, words: Array<String>): List<String> {
        val root = TrieNode()
        for (word in words) {
            var node = root
            for (letter in word) {
                node = node.children.computeIfAbsent(letter) { TrieNode() }
            }
            node.word = word
        }

        this.board = board
        for (row in board.indices) {
            for (col in board[0].indices) {
                if (root.children.containsKey(board[row][col])) {
                    backtracking(row, col, root)
                }
            }
        }

        return result
    }

    private fun backtracking(row: Int, col: Int, parent: TrieNode) {
        val letter = board[row][col]
        val currNode = parent.children[letter] ?: return

        currNode.word?.let {
            result.add(it)
            currNode.word = null
        }

        board[row][col] = '#'

        val rowOffset = intArrayOf(-1, 0, 1, 0)
        val colOffset = intArrayOf(0, 1, 0, -1)
        for (i in 0 until 4) {
            val newRow = row + rowOffset[i]
            val newCol = col + colOffset[i]
            if (newRow in board.indices && newCol in board[0].indices) {
                if (currNode.children.containsKey(board[newRow][newCol])) {
                    backtracking(newRow, newCol, currNode)
                }
            }
        }

        board[row][col] = letter

        if (currNode.children.isEmpty()) {
            parent.children.remove(letter)
        }
    }
}

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

Задача: 142. Linked List Cycle II
Сложность: medium

Дана голова связного списка. Верните узел, с которого начинается цикл. Если цикла нет, верните null.

Цикл в связном списке существует, если есть такой узел в списке, до которого можно добраться снова, последовательно следуя по указателю next. Внутренне переменная pos используется для обозначения индекса узла, к которому подключен указатель next последнего узла (индексация с нуля). Она равна -1, если цикла нет. Обратите внимание, что pos не передается в качестве параметра.

Не модифицируйте связный список.

Пример:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

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

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

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

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

😎 Решение:

class ListNode(var `val`: Int) {
    var next: ListNode? = null
}

class Solution {
    fun detectCycle(head: ListNode?): ListNode? {
        val nodesSeen = mutableSetOf<ListNode>()
        var node = head
        while (node != null) {
            if (node in nodesSeen) {
                return node
            } else {
                nodesSeen.add(node)
                node = node.next
            }
        }
        return null
    }
}

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

Задача: 684. Redundant Connection
Сложность: medium

В этой задаче дерево — это неориентированный граф, который является связным и не содержит циклов.

Вам дан граф, который изначально был деревом с n узлами, пронумерованными от 1 до n, и к которому добавили одно дополнительное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее. Граф представлен массивом edges длины n, где edges[i] = [ai, bi] указывает на то, что существует ребро между узлами ai и bi в графе.

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

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

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

1⃣Для каждого ребра (u, v) создайте представление графа с использованием списка смежности. Это позволит легко выполнять обход в глубину (DFS) для проверки соединений между узлами.

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

3⃣Верните дублирующееся ребро, которое встречается последним в исходных данных. Это обеспечит корректность решения, даже если существует несколько ответов.

😎 Решение:

class Solution {
    val seen = mutableSetOf<Int>()
    val MAX_EDGE_VAL = 1000

    fun findRedundantConnection(edges: Array<IntArray>): IntArray {
        val graph = Array(MAX_EDGE_VAL + 1) { mutableListOf<Int>() }

        for (edge in edges) {
            seen.clear()
            if (graph[edge[0]].isNotEmpty() && graph[edge[1]].isNotEmpty() && dfs(graph, edge[0], edge[1])) {
                return edge
            }
            graph[edge[0]].add(edge[1])
            graph[edge[1]].add(edge[0])
        }
        return intArrayOf()
    }

    fun dfs(graph: Array<MutableList<Int>>, source: Int, target: Int): Boolean {
        if (!seen.contains(source)) {
            seen.add(source)
            if (source == target) return true
            for (nei in graph[source]) {
                if (dfs(graph, nei, target)) return true
            }
        }
        return false
    }
}

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

Задача: 149. Max Points on a Line
Сложность: hard

Дан массив точек, где points[i] = [xi, yi] представляет точку на плоскости XY. Верните максимальное количество точек, которые лежат на одной прямой.

Пример:

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

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

1⃣Проходим по всем точкам массива. Пусть текущая точка будет points[i]. Создаём хеш-таблицу cnt для подсчёта углов.

2⃣Для каждой точки j, не равной i, рассчитываем арктангенс вектора points[j] - points[i] и добавляем это значение в хеш-таблицу

3⃣Пусть k будет максимальным количеством вхождений какого-либо значения угла в хеш-таблице. Обновляем ответ значением k + 1 (прибавляем 1, потому что точка points[i] также лежит на этой линии, и её нужно включить в ответ).

😎 Решение:

class Solution {
    fun maxPoints(points: Array<IntArray>): Int {
        val n = points.size
        if (n == 1) {
            return 1
        }
        var result = 2
        for (i in 0 until n) {
            val cnt = mutableMapOf<Double, Int>()
            for (j in 0 until n) {
                if (j != i) {
                    val dy = (points[j][1] - points[i][1]).toDouble()
                    val dx = (points[j][0] - points[i][0]).toDouble()
                    val angle = Math.atan2(dy, dx)
                    cnt[angle] = cnt.getOrDefault(angle, 0) + 1
                }
            }
            for ((_, count) in cnt) {
                result = maxOf(result, count + 1)
            }
        }
        return result
    }
}

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

Задача: 148. Sort List
Сложность: medium

Дан указатель на начало связанного списка. Верните список после его сортировки в порядке возрастания.

Пример:

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

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

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

2⃣Рекурсивно сортируйте каждый подсписок и объединяйте их в один отсортированный список. Это аналогично задаче слияния двух отсортированных связанных списков.

3⃣Процесс продолжается до тех пор, пока не будет получен исходный список в отсортированном порядке. Например, для связанного списка [10,1,60,30,5] описан процесс сортировки слиянием с использованием подхода сверху вниз. Если у нас есть отсортированные списки list1 = [1,10] и list2 = [5,30,60], следующая анимация иллюстрирует процесс слияния обоих списков в один отсортированный список.

😎 Решение:

class ListNode(var `val`: Int) {
    var next: ListNode? = null
}

class Solution {
    fun sortList(head: ListNode?): ListNode? {
        if (head == null || head.next == null) {
            return head
        }
        val mid = getMid(head)
        val left = sortList(head)
        val right = sortList(mid)
        return merge(left, right)
    }

    private fun merge(list1: ListNode?, list2: ListNode?): ListNode? {
        val dummyHead = ListNode(0)
        var tail = dummyHead
        var list1 = list1
        var list2 = list2
        while (list1 != null && list2 != null) {
            if (list1.`val` < list2.`val`) {
                tail.next = list1
                list1 = list1.next
            } else {
                tail.next = list2
                list2 = list2.next
            }
            tail = tail.next!!
        }
        tail.next = list1 ?: list2
        return dummyHead.next
    }

    private fun getMid(head: ListNode?): ListNode? {
        var midPrev: ListNode? = null
        var slow = head
        var fast = head
        while (fast != null && fast.next != null) {
            midPrev = if (midPrev == null) slow else midPrev.next
            slow = slow.next
            fast = fast.next?.next
        }
        val mid = midPrev?.next
        midPrev?.next = null
        return mid
    }
}

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

Задача: 813. Largest Sum of Averages
Сложность: medium

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

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

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

Пример:

Input: nums = [9,1,2,3,9], k = 3
Output: 20.00000
Explanation: 
The best choice is to partition nums into [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20.
We could have also partitioned nums into [9, 1], [2], [3, 9], for example.
That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.

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

1⃣Пусть dp(i, k) будет лучшей оценкой для разбиения массива A[i:] на не более чем k частей. Если первая группа, в которую мы разбиваем A[i:], заканчивается перед j, тогда наше разбиение-кандидат имеет оценку average(i, j) + dp(j, k-1), где average(i, j) = (A[i] + A[i+1] + ... + A[j-1]) / (j - i) (деление с плавающей запятой). Мы берем наивысшую оценку из этих вариантов, помня, что разбиение необязательно - dp(i, k) также может быть просто average(i, N).

2⃣В общем случае наша рекурсия выглядит так: dp(i, k) = max(average(i, N), max_{j > i}(average(i, j) + dp(j, k-1))). Мы можем рассчитывать average немного быстрее, используя префиксные суммы. Если P[x+1] = A[0] + A[1] + ... + A[x], тогда average(i, j) = (P[j] - P[i]) / (j - i).

3⃣Наша реализация демонстрирует подход "снизу вверх" для динамического программирования. На шаге k во внешнем цикле, dp[i] представляет собой dp(i, k) из обсуждения выше, и мы рассчитываем следующий слой dp(i, k+1). Завершение второго цикла для i = 0..N-1 означает завершение расчета правильного значения для dp(i, t), а внутренний цикл выполняет расчет max_{j > i}(average(i, j) + dp(j, k)).

😎 Решение:

class Solution {
    fun largestSumOfAverages(A: IntArray, K: Int): Double {
        val P = DoubleArray(A.size + 1)
        for (i in A.indices) {
            P[i + 1] = P[i] + A[i]
        }
        
        fun average(i: Int, j: Int): Double {
            return (P[j] - P[i]) / (j - i)
        }

        val N = A.size
        val dp = DoubleArray(N) { average(it, N) }
        for (k in 0 until K - 1) {
            for (i in 0 until N) {
                for (j in i + 1 until N) {
                    dp[i] = maxOf(dp[i], average(i, j) + dp[j])
                }
            }
        }
        
        return dp[0]
    }
}

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

Задача: 111. Minimum Depth of Binary Tree
Сложность: easy

Дано бинарное дерево, найдите его минимальную глубину.

Минимальная глубина - это количество узлов вдоль самого короткого пути от корневого узла до ближайшего листового узла.

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: 2

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

1⃣Мы будем использовать метод обхода в глубину (dfs) с корнем в качестве аргумента.
Базовое условие рекурсии: это для узла NULL, в этом случае мы должны вернуть 0.

2⃣Если левый ребенок корня является NULL: тогда мы должны вернуть 1 + минимальную глубину для правого ребенка корневого узла, что равно 1 + dfs(root.right).

3⃣Если правый ребенок корня является NULL: тогда мы должны вернуть 1 + минимальную глубину для левого ребенка корневого узла, что равно 1 + dfs(root.left). Если оба ребенка не являются NULL, тогда вернуть 1 + min(dfs(root.left), dfs(root.right)).

😎 Решение:

class Solution {
    fun dfs(root: TreeNode?): Int {
        if (root == null) {
            return 0
        }
        if (root.left == null) {
            return 1 + dfs(root.right)
        } else if (root.right == null) {
            return 1 + dfs(root.left)
        }
        return 1 + minOf(dfs(root.left!!), dfs(root.right!!))
    }

    fun minDepth(root: TreeNode?): Int = dfs(root)
}

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

Задача: 811. Subdomain Visit Count
Сложность: medium

Веб-сайт с доменом "discuss.leetcode.com" состоит из различных поддоменов. На верхнем уровне у нас есть "com", на следующем уровне - "leetcode.com", и на самом нижнем уровне - "discuss.leetcode.com". Когда мы посещаем домен, такой как "discuss.leetcode.com", мы также автоматически посещаем родительские домены "leetcode.com" и "com".

Домен с парным счетчиком - это домен, который имеет один из двух форматов "rep d1.d2.d3" или "rep d1.d2", где rep - это количество посещений домена, а d1.d2.d3 - это сам домен.

Например, "9001 discuss.leetcode.com" - это домен с парным счетчиком, указывающий на то, что discuss.leetcode.com был посещен 9001 раз.
Дан массив доменов с парными счетчиками cpdomains, верните массив доменов с парными счетчиками для каждого поддомена во входных данных. Вы можете вернуть ответ в любом порядке.

Пример:

Input: cpdomains = ["9001 discuss.leetcode.com"]
Output: ["9001 leetcode.com","9001 discuss.leetcode.com","9001 com"]
Explanation: We only have one website domain: "discuss.leetcode.com".
As discussed above, the subdomain "leetcode.com" and "com" will also be visited. So they will all be visited 9001 times.

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

1⃣Следуем указаниям из условия задачи.

2⃣Для адреса вида a.b.c, подсчитываем a.b.c, b.c и c. Для адреса вида x.y, подсчитываем x.y и y.

3⃣Для подсчета этих строк используем хеш-таблицу. Для разделения строк на требуемые части используем библиотечные функции split.

😎 Решение:

class Solution {
    fun subdomainVisits(cpdomains: Array<String>): List<String> {
        val ans = mutableMapOf<String, Int>()
        for (domain in cpdomains) {
            val parts = domain.split(" ")
            val count = parts[0].toInt()
            val frags = parts[1].split(".")
            for (i in frags.indices) {
                val subdomain = frags.subList(i, frags.size).joinToString(".")
                ans[subdomain] = ans.getOrDefault(subdomain, 0) + count
            }
        }
        return ans.map { "${it.value} ${it.key}" }
    }
}

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

Задача: 745. Prefix and Suffix Search
Сложность: hard

Создайте специальный словарь, в котором поиск слов осуществляется по префиксу и суффиксу. Реализуйте класс WordFilter: WordFilter(string[] words) Инициализирует объект со словами в словаре. f(string pref, string suff) Возвращает индекс слова в словаре, которое имеет префикс pref и суффикс suff. Если существует более одного допустимого индекса, возвращается наибольший из них. Если в словаре нет такого слова, возвращается -1.

Пример:

Input: letters = ["c","f","j"], target = "a"
Output: "c"

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

1⃣Сохраните слова и их индексы в словаре.

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

3⃣Реализуйте функцию поиска, которая ищет наибольший индекс слова по префиксу и суффиксу.

😎 Решение:

class WordFilter(words: Array<String>) {
    private val prefixSuffixMap = mutableMapOf<String, Int>()
    
    init {
        for ((index, word) in words.withIndex()) {
            val length = word.length
            for (prefixLength in 1..length) {
                for (suffixLength in 1..length) {
                    val prefix = word.substring(0, prefixLength)
                    val suffix = word.substring(length - suffixLength)
                    val key = "$prefix#$suffix"
                    prefixSuffixMap[key] = index
                }
            }
        }
    }
    
    fun f(pref: String, suff: String): Int {
        val key = "$pref#$suff"
        return prefixSuffixMap[key] ?: -1
    }
}

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

Задача: 1029. Two City Scheduling
Сложность: medium

Компания планирует провести интервью с 2n людьми. Учитывая массив costs, где costs[i] = [aCosti, bCosti], стоимость перелета i-го человека в город a равна aCosti, а стоимость перелета i-го человека в город b равна bCosti. Выведите минимальную стоимость перелета каждого человека в город, чтобы в каждый город прибыло ровно n человек.

Пример:

Input: traversal = "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]

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

1⃣Вычислить разницу стоимости:
Для каждого человека вычислите разницу в стоимости между перелетом в город A и город B.

2⃣Сортировать по разнице:
Отсортируйте людей по разнице в стоимости перелета в город A и B. Это поможет минимизировать общую стоимость, так как мы сначала будем отправлять тех, для кого разница минимальна.

3⃣Назначить города:
Первые n человек из отсортированного списка отправьте в город A.
Оставшихся n человек отправьте в город B.

😎 Решение:

class Solution {
    fun twoCitySchedCost(costs: Array<IntArray>): Int {
        costs.sortBy { it[0] - it[1] }
        var totalCost = 0
        val n = costs.size / 2
        for (i in 0 until n) {
            totalCost += costs[i][0]
            totalCost += costs[i + n][1]
        }
        return totalCost
    }
}

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

Задача: 128. Longest Consecutive Sequence
Сложность: Medium

Дан несортированный массив целых чисел nums. Верните длину самой длинной последовательности последовательных элементов.

Необходимо написать алгоритм, который работает за время O(n).

Пример:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

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

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

2⃣Обработка чисел в массиве:
Для всех других случаев мы сортируем массив nums и рассматриваем каждое число, начиная со второго (поскольку нам нужно сравнивать каждое число с предыдущим).
Если текущее число и предыдущее равны, то текущая последовательность не удлиняется и не прерывается, поэтому мы просто переходим к следующему числу.
Если числа не равны, то нужно проверить, удлиняет ли текущее число последовательность (т.е. nums[i] == nums[i-1] + 1). Если удлиняет, то мы увеличиваем наш текущий счёт и продолжаем.

3⃣Завершение обработки и возврат результата:
В противном случае последовательность прерывается, и мы записываем нашу текущую последовательность и сбрасываем её до 1 (чтобы включить число, которое прервало последовательность).
Возможно, что последний элемент массива nums является частью самой длинной последовательности, поэтому мы возвращаем максимум из текущей последовательности и самой длинной.

😎 Решение:

class Solution {
    fun longestConsecutive(nums: IntArray): Int {
        var longestStreak = 0
        val numSet = nums.toSet()

        for (num in numSet) {
            if (num - 1 !in numSet) {
                var currentNum = num
                var currentStreak = 1

                while (currentNum + 1 in numSet) {
                    currentNum += 1
                    currentStreak += 1
                }

                longestStreak = maxOf(longestStreak, currentStreak)
            }
        }
        return longestStreak
    }
}

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

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

Есть n лампочек, которые изначально выключены. Сначала вы включаете все лампочки, затем выключаете каждую вторую лампочку.

На третьем раунде вы переключаете каждую третью лампочку (включаете, если она выключена, или выключаете, если она включена). На i-ом раунде вы переключаете каждую i-ую лампочку. На n-ом раунде вы переключаете только последнюю лампочку.

Верните количество лампочек, которые будут включены после n раундов.

Пример:

Input: n = 3
Output: 1
Explanation: At first, the three bulbs are [off, off, off].
After the first round, the three bulbs are [on, on, on].
After the second round, the three bulbs are [on, off, on].
After the third round, the three bulbs are [on, off, off]. 
So you should return 1 because there is only one bulb is on.
Explanation: The two words can be "abcw", "xtfn".

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

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

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

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

😎 Решение:

class Solution {
    fun bulbSwitch(n: Int): Int {
        return kotlin.math.sqrt(n.toDouble()).toInt()
    }
}

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

Задача: 842. Split Array into Fibonacci Sequence
Сложность: medium

Вам дана строка цифр num, такая как "123456579". Мы можем разделить её на последовательность, похожую на Фибоначчи [123, 456, 579].
Формально, последовательность, похожая на Фибоначчи, это список f неотрицательных целых чисел, таких что:
0 <= f[i] < 2^31 (то есть каждое число помещается в 32-битный знаковый целый тип),
f.length >= 3, и
f[i] + f[i + 1] == f[i + 2] для всех 0 <= i < f.length - 2.
Обратите внимание, что при разделении строки на части каждая часть не должна иметь лишних ведущих нулей, за исключением случая, если эта часть является числом 0.

Верните любую последовательность, похожую на Фибоначчи, из строки num, или верните [] если это невозможно.

Пример:

Input: num = "1101111"
Output: [11,0,11,11]
Explanation: The output [110, 1, 111] would also be accepted.

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

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

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

3⃣Если последовательность Фибоначчи найдена, верните её, иначе продолжайте перебор.

😎 Решение:

class Solution {
    fun splitIntoFibonacci(S: String): List<Int> {
        val N = S.length
        for (i in 0 until minOf(10, N)) {
            if (S[0] == '0' && i > 0) break
            val a = S.substring(0, i + 1).toLong()
            if (a >= Int.MAX_VALUE) break

            for (j in i + 1 until minOf(i + 10, N)) {
                if (S[i + 1] == '0' && j > i + 1) break
                val b = S.substring(i + 1, j + 1).toLong()
                if (b >= Int.MAX_VALUE) break

                val fib = mutableListOf(a.toInt(), b.toInt())
                var k = j + 1
                while (k < N) {
                    val nxt = fib[fib.size - 2] + fib[fib.size - 1]
                    if (nxt > Int.MAX_VALUE) break
                    val nxtS = nxt.toString()
                    if (S.substring(k).startsWith(nxtS)) {
                        k += nxtS.length
                        fib.add(nxt.toInt())
                    } else {
                        break
                    }
                }
                if (fib.size >= 3) return fib
            }
        }
        return emptyList()
    }
}

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