Задача: 1473. Paint House III
Сложность: hard

Есть ряд из m домов в маленьком городе, каждый дом должен быть покрашен одним из n цветов (обозначены от 1 до n), некоторые дома, которые были покрашены прошлым летом, не должны быть перекрашены.

Соседство — это максимальная группа непрерывных домов, которые покрашены в один и тот же цвет.

Например: дома = [1,2,2,3,3,2,1,1] содержат 5 соседств [{1}, {2,2}, {3,3}, {2}, {1,1}].
Дан массив домов, матрица m x n стоимости и целое число target, где:
houses[i]: цвет дома i, и 0, если дом ещё не покрашен.
cost[i][j]: стоимость покраски дома i в цвет j + 1.
Верните минимальную стоимость покраски всех оставшихся домов таким образом, чтобы было ровно target соседств. Если это невозможно, верните -1.

Пример:

Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 9
Explanation: Paint houses of this way [1,2,2,1,1]
This array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}].
Cost of paint all houses (1 + 1 + 1 + 1 + 5) = 9.

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

1⃣Инициализация и базовые случаи:
Создайте класс Solution и массив memo для мемоизации результатов. Установите MAX_COST как максимально возможную стоимость плюс 1.
Создайте метод findMinCost, который проверяет базовые случаи:
- если все дома пройдены, возвращайте 0, если количество соседств равно target, иначе возвращайте MAX_COST.
- если количество соседств больше target, возвращайте MAX_COST.
Если результат уже вычислен, возвращайте его из memo.

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

3⃣Метод minCost:
Запустите метод findMinCost с начальными параметрами и верните результат. Если результат равен MAX_COST, верните -1.

😎 Решение:

class Solution {
    private val MAX_COST = 1000001
    private val memo = Array(100) { Array(100) { arrayOfNulls<Int>(22) } }

    private fun findMinCost(houses: IntArray, cost: Array<IntArray>, targetCount: Int, currIndex: Int, neighborhoodCount: Int, prevHouseColor: Int): Int {
        if (currIndex == houses.size) {
            return if (neighborhoodCount == targetCount) 0 else MAX_COST
        }
        
        if (neighborhoodCount > targetCount) {
            return MAX_COST
        }

        memo[currIndex][neighborhoodCount][prevHouseColor]?.let {
            return it
        }
        
        var minCost = MAX_COST

        if (houses[currIndex] != 0) {
            val newNeighborhoodCount = neighborhoodCount + if (houses[currIndex] != prevHouseColor) 1 else 0
            minCost = findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, houses[currIndex])
        } else {
            for (color in 1..cost[0].size) {
                val newNeighborhoodCount = neighborhoodCount + if (color != prevHouseColor) 1 else 0
                val currCost = cost[currIndex][color - 1] + findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, color)
                minCost = kotlin.math.min(minCost, currCost)
            }
        }
        
        memo[currIndex][neighborhoodCount][prevHouseColor] = minCost
        return minCost
    }

    fun minCost(houses: IntArray, cost: Array<IntArray>, m: Int, n: Int, target: Int): Int {
        val answer = findMinCost(houses, cost, target, 0, 0, 0)
        return if (answer == MAX_COST) -1 else answer
    }
}

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

Задача: 998. Maximum Binary Tree II
Сложность: medium

Максимальное дерево - это дерево, в котором каждый узел имеет значение большее, чем любое другое значение в его поддереве. Вам дан корень максимального двоичного дерева и целое число val. Как и в предыдущей задаче, данное дерево было построено из списка a (root = Construct(a)) рекурсивно с помощью следующей процедуры Construct(a): Если a пусто, верните null.
В противном случае пусть a[i] - наибольший элемент a. Создайте корневой узел со значением a[i]. Левым ребенком root будет Construct([a[0], a[1], ..., a[i - 1]]). Правым ребенком root будет Construct([a[i + 1], a[i + 2], ..., a[a.length])...., a[a.length - 1]]). Возвращаем root. Обратите внимание, что нам не было дано непосредственно a, а только корневой узел root = Construct(a). Предположим, что b - это копия a с добавленным к ней значением val. Гарантируется, что b имеет уникальные значения. Возвращаем Construct(b).

Пример:

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

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

1⃣Поиск места вставки:
Итерируйте через дерево, начиная с корня. Найдите место для вставки нового значения val так, чтобы дерево оставалось максимальным деревом. Если значение val больше, чем значение текущего узла, создайте новый узел с val и сделайте текущий узел его левым ребенком.

2⃣Вставка нового узла:
Если значение val меньше, чем значение текущего узла, продолжайте спускаться по правому поддереву, пока не найдете место для вставки.

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

😎 Решение:

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

class Solution {
    fun insertIntoMaxTree(root: TreeNode?, `val`: Int): TreeNode? {
        if (root == null || `val` > root.`val`) {
            val newNode = TreeNode(`val`)
            newNode.left = root
            return newNode
        }
        root.right = insertIntoMaxTree(root.right, `val`)
        return root
    }
}

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

Задача: 146. LRU Cache
Сложность: medium

Реализуйте класс LRUCache:
LRUCache(int capacity) - инициализирует LRU-кэш с положительным размером capacity.
int get(int key) - возвращает значение по ключу, если ключ существует, в противном случае возвращает -1.
void put(int key, int value) - обновляет значение по ключу, если ключ существует. В противном случае добавляет пару ключ-значение в кэш. Если количество ключей превышает установленную емкость после этой операции, удаляет наименее недавно использованный ключ.

Функции get и put должны выполняться за среднее время O(1).

Пример:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

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

1⃣Используем хеш-таблицу map для хранения ключей и двусвязный список для отслеживания порядка использования. Самый недавно использованный узел — в хвосте, наименее — в голове.

2⃣При get(key) проверяем наличие ключа в map. Если найден — перемещаем узел в конец списка и возвращаем значение. Иначе возвращаем -1.

3⃣При put(key, value) — если ключ уже есть, удаляем старый узел. Добавляем новый узел в конец списка и map. Если размер превышает capacity, удаляем узел из головы и из map.

😎 Решение:

class ListNode(val key: Int, var value: Int) {
    var next: ListNode? = null
    var prev: ListNode? = null
}

class LRUCache(private val capacity: Int) {
    private val map = mutableMapOf<Int, ListNode>()
    private val head = ListNode(-1, -1)
    private val tail = ListNode(-1, -1)

    init {
        head.next = tail
        tail.prev = head
    }

    fun get(key: Int): Int {
        val node = map[key] ?: return -1
        remove(node)
        add(node)
        return node.value
    }

    fun put(key: Int, value: Int) {
        if (map.containsKey(key)) {
            remove(map[key]!!)
        }
        val newNode = ListNode(key, value)
        map[key] = newNode
        add(newNode)
        if (map.size > capacity) {
            map.remove(head.next!!.key)?.also { remove(it) }
        }
    }

    private fun add(node: ListNode) {
        val prev = tail.prev
        node.prev = prev
        node.next = tail
        prev?.next = node
        tail.prev = node
    }

    private fun remove(node: ListNode) {
        val prev = node.prev
        val next = node.next
        prev?.next = next
        next?.prev = prev
    }
}

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

Задача: 783. Minimum Distance Between BST Nodes
Сложность: easy

Дан корень дерева поиска (BST). Верните минимальную разницу между значениями любых двух различных узлов в дереве.

Пример:

Input: root = [4,2,6,1,3]
Output: 1

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

1⃣Инициализируйте minDistance значением MAX_VALUE; это переменная для хранения минимальной разницы.

2⃣Выполните обход дерева поиска в порядке возрастания (in-order traversal) и сохраните узлы в списке inorderNodes.

3⃣Итеративно проходите по списку inorderNodes, начиная с индекса 1. Для каждого элемента на позиции i найдите разницу с элементом на индексе i - 1 и соответствующим образом обновите переменную minDistance.
Верните minDistance.

😎 Решение:

class Solution {
    private val inorderNodes = mutableListOf<Int>()
    
    private fun inorderTraversal(root: TreeNode?) {
        if (root == null) return
        
        inorderTraversal(root.left)
        inorderNodes.add(root.`val`)
        inorderTraversal(root.right)
    }
    
    fun minDiffInBST(root: TreeNode?): Int {
        inorderTraversal(root)
        
        var minDistance = Int.MAX_VALUE
        for (i in 1 until inorderNodes.size) {
            minDistance = minOf(minDistance, inorderNodes[i] - inorderNodes[i - 1])
        }
        
        return minDistance
    }
}

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

Задача: 666. Path Sum IV
Сложность: medium

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

Сотни представляют глубину d этого узла, где 1 <= d <= 4.
Десятки представляют позицию p этого узла на уровне, которому он принадлежит, где 1 <= p <= 8. Позиция соответствует позиции в полном бинарном дереве.
Единицы представляют значение v этого узла, где 0 <= v <= 9.
Дан массив возрастающих трехзначных чисел nums, представляющих бинарное дерево с глубиной меньше 5. Верните сумму всех путей от корня к листьям.

Гарантируется, что данный массив представляет собой валидное связанное бинарное дерево.

Пример:

Input: nums = [113,215,221]
Output: 12
Explanation: The tree that the list represents is shown.
The path sum is (3 + 5) + (3 + 1) = 12.

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

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

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

3⃣Подсчет суммы путей:
Выполните обход дерева (например, используя DFS) и подсчитайте сумму всех путей от корня к листьям.

😎 Решение:

class Solution {
    fun pathSum(nums: IntArray): Int {
        val tree = mutableMapOf<Pair<Int, Int>, Int>()
        
        for (num in nums) {
            val depth = num / 100
            val pos = (num / 10) % 10
            val val = num % 10
            tree[depth to pos] = val
        }
        
        var totalSum = 0
        
        fun dfs(depth: Int, pos: Int, currentSum: Int) {
            val node = tree[depth to pos] ?: return
            val newSum = currentSum + node
            val leftChild = depth + 1 to 2 * pos - 1
            val rightChild = depth + 1 to 2 * pos
            
            if (tree[leftChild] == null && tree[rightChild] == null) {
                totalSum += newSum
            } else {
                dfs(depth + 1, 2 * pos - 1, newSum)
                dfs(depth + 1, 2 * pos, newSum)
            }
        }
        
        dfs(1, 1, 0)
        return totalSum
    }
}

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

Задача: 310. Minimum Height Trees
Сложность: medium

Дерево — это неориентированный граф, в котором любые две вершины соединены ровно одним путем. Другими словами, любое связное граф без простых циклов является деревом.

Дано дерево из n узлов, помеченных от 0 до n - 1, и массив из n - 1 ребер, где edges[i] = [ai, bi] указывает на наличие неориентированного ребра между узлами ai и bi в дереве. Вы можете выбрать любой узел дерева в качестве корня. Когда вы выбираете узел x в качестве корня, дерево имеет высоту h. Среди всех возможных корневых деревьев те, которые имеют минимальную высоту (то есть min(h)), называются деревьями с минимальной высотой (MHT).

Верните список всех меток корней MHT. Вы можете вернуть ответ в любом порядке.

Высота корневого дерева — это количество ребер на самом длинном нисходящем пути между корнем и листом.

Пример:

Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.

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

1⃣Создание списка смежности
Создайте список смежности, представляющий граф.

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

3⃣Повторение процесса
Повторяйте процесс до тех пор, пока не останется два или менее узлов. Эти узлы будут корнями деревьев с минимальной высотой (MHT).

😎 Решение:

class Solution {
    fun findMinHeightTrees(n: Int, edges: Array<IntArray>): List<Int> {
        if (n == 1) return listOf(0)
        
        val adj = Array(n) { mutableListOf<Int>() }
        for (edge in edges) {
            adj[edge[0]].add(edge[1])
            adj[edge[1]].add(edge[0])
        }
        
        val leaves = mutableListOf<Int>()
        for (i in 0 until n) {
            if (adj[i].size == 1) {
                leaves.add(i)
            }
        }
        
        var remainingNodes = n
        while (remainingNodes > 2) {
            remainingNodes -= leaves.size
            val newLeaves = mutableListOf<Int>()
            for (leaf in leaves) {
                val neighbor = adj[leaf].removeAt(0)
                adj[neighbor].remove(leaf)
                if (adj[neighbor].size == 1) {
                    newLeaves.add(neighbor)
                }
            }
            leaves.clear()
            leaves.addAll(newLeaves)
        }
        
        return leaves
    }
}

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

Задача: 216. Combination Sum III
Сложность: medium

Найдите все допустимые комбинации k чисел, которые в сумме дают n, при условии, что:

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

Пример:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

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

1⃣Запускаем backtrack: передаем оставшуюся величину, размер k, текущую зависимость и следующий индекс.

2⃣Если длина 0 и размер = k — добавьте соединение. Иначе пробуем числа от текущего до 9.

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

😎 Решение:

class Solution {
    fun backtrack(remain: Int, k: Int, comb: MutableList<Int>, nextStart: Int, results: MutableList<MutableList<Int>>) {
        if (remain == 0 && comb.size == k) {
            results.add(ArrayList(comb))
            return
        } else if (remain < 0 || comb.size == k) {
            return
        }

        for (i in nextStart until 9) {
            comb.add(i + 1)
            backtrack(remain - i - 1, k, comb, i + 1, results)
            comb.removeAt(comb.size - 1)
        }
    }

    fun combinationSum3(k: Int, n: Int): List<List<Int>> {
        val results = mutableListOf<MutableList<Int>>()
        val comb = mutableListOf<Int>()
        backtrack(n, k, comb, 0, results)
        return results
    }
}

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

Задача: 1019. Next Greater Node In Linked List
Сложность: medium

Вам дана голова связного списка с n узлами. Для каждого узла в списке найдите значение следующего большего узла. То есть для каждого узла найдите значение первого узла, который находится рядом с ним и имеет строго большее значение, чем он. Верните целочисленный массив answer, где answer[i] - это значение следующего большего узла ith-узла (с индексацией по 1). Если у узла ith нет следующего большего узла, установите answer[i] = 0.

Пример:

Input: head = [2,1,5]
Output: [5,5,0]

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

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

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

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

😎 Решение:

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

class Solution {
    fun nextLargerNodes(head: ListNode?): IntArray {
        val values = mutableListOf<Int>()
        var current = head
        while (current != null) {
            values.add(current.`val`)
            current = current.next
        }
        
        val answer = IntArray(values.size)
        val stack = mutableListOf<Int>()
        
        for (i in values.indices) {
            while (stack.isNotEmpty() && values[stack.last()] < values[i]) {
                answer[stack.removeAt(stack.size - 1)] = values[i]
            }
            stack.add(i)
        }
        
        return answer
    }
}

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

Задача: 25. Reverse Nodes in k-Group
Сложность: hard

Учитывая заголовок связанного списка, поменяйте местами узлы списка k за раз и верните измененный список.

k — целое положительное число, меньшее или равное длине связанного списка. Если количество узлов не кратно k, то пропущенные узлы в конечном итоге должны остаться такими, какие они есть.

Вы не можете изменять значения в узлах списка, можно изменять только сами узлы.

Пример:

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

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

1⃣ Проверяем, хватает ли элементов в текущей группе (не менее k узлов).

2⃣ Если хватает, переворачиваем узлы в группе, используя указатели.

3⃣ Рекурсивно вызываем reverseKGroup для следующей группы и соединяем с уже перевернутыми узлами.

😎 Решение:

class Solution {
    fun reverseKGroup(head: ListNode?, k: Int): ListNode? {
        var count = 0
        var cur = head
        while (count < k && cur != null) {
            cur = cur.next
            count++
        }
        if (count < k) return head

        var prev: ListNode? = null
        cur = head
        repeat(k) {
            val next = cur?.next
            cur?.next = prev
            prev = cur
            cur = next
        }

        head?.next = reverseKGroup(cur, k)
        return prev
    }
}

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

Задача: 622. Design Circular Queue
Сложность: medium

Разработайте свою реализацию круговой очереди. Круговая очередь - это линейная структура данных, в которой операции выполняются по принципу FIFO (First In First Out), а последняя позиция соединяется с первой, образуя круг. Одно из преимуществ круговой очереди заключается в том, что мы можем использовать пространство перед очередью. В обычной очереди, когда очередь становится полной, мы не можем вставить следующий элемент, даже если перед очередью есть свободное место. Но с помощью круговой очереди мы можем использовать пространство для хранения новых значений. Реализация класса MyCircularQueue: MyCircularQueue(k) Инициализирует объект с размером очереди k. int Front() Получает первый элемент из очереди. Если очередь пуста, возвращается -1. int Rear() Получает последний элемент из очереди. Если очередь пуста, возвращается -1. boolean enQueue(int value) Вставляет элемент в циклическую очередь. Возвращает true, если операция прошла успешно. boolean deQueue() Удаляет элемент из круговой очереди. Возвращает true, если операция выполнена успешно. boolean isEmpty() Проверяет, пуста ли круговая очередь. boolean isFull() Проверяет, заполнена ли круговая очередь. Вы должны решить проблему без использования встроенной структуры данных очереди в вашем языке программирования.

Пример:

Input
["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 3, true, true, true, 4]

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

1⃣Используйте массив фиксированного размера для хранения элементов очереди и два указателя: front для отслеживания начала очереди и rear для отслеживания конца очереди.

2⃣Реализуйте методы enQueue и deQueue для вставки и удаления элементов, обновляя указатели по круговому принципу.

3⃣Реализуйте методы Front, Rear, isEmpty и isFull для доступа к элементам и проверки состояния очереди.

😎 Решение:

class MyCircularQueue(k: Int) {
    private val queue: IntArray = IntArray(k) { -1 }
    private var front: Int = 0
    private var rear: Int = -1
    private var size: Int = 0
    private val capacity: Int = k
    
    fun enQueue(value: Int): Boolean {
        if (isFull()) {
            return false
        }
        rear = (rear + 1) % capacity
        queue[rear] = value
        size++
        return true
    }
    
    fun deQueue(): Boolean {
        if (isEmpty()) {
            return false
        }
        front = (front + 1) % capacity
        size--
        return true
    }
    
    fun Front(): Int {
        return if (isEmpty()) -1 else queue[front]
    }
    
    fun Rear(): Int {
        return if (isEmpty()) -1 else queue[rear]
    }
    
    fun isEmpty(): Boolean {
        return size == 0
    }
    
    fun isFull(): Boolean {
        return size == capacity
    }
}

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

Задача: 1272. Remove Interval
Сложность: medium

Множество вещественных чисел можно представить как объединение нескольких несовпадающих интервалов, где каждый интервал имеет вид [a, b). Вещественное число x входит в множество, если один из его интервалов [a, b) содержит x (то есть a <= x < b). Вам дан отсортированный список непересекающихся интервалов, представляющих множество вещественных чисел, как описано выше, где intervals[i] = [ai, bi] представляет интервал [ai, bi). Вам также дан еще один интервал toBeRemoved. Верните набор вещественных чисел с интервалом toBeRemoved, удаленным из intervals. Другими словами, верните набор вещественных чисел, каждый x в котором находится в интервале, но не в toBeRemoved. Вашим ответом должен быть отсортированный список непересекающихся интервалов, как описано выше.

Пример:

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

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

1⃣Итерируйтесь по каждому интервалу в списке intervals.

2⃣Для каждого интервала, проверяйте пересечения с toBeRemoved и обновляйте список результатов.

3⃣Добавляйте непересекающиеся части текущего интервала в результат.

😎 Решение:

class Solution {
    fun removeInterval(intervals: List<List<Double>>, toBeRemoved: List<Double>): List<List<Double>> {
        val result = mutableListOf<List<Double>>()
        for (interval in intervals) {
            if (interval[0] < toBeRemoved[0]) {
                result.add(listOf(interval[0], minOf(interval[1], toBeRemoved[0])))
            }
            if (interval[1] > toBeRemoved[1]) {
                result.add(listOf(maxOf(interval[0], toBeRemoved[1]), interval[1]))
            }
        }
        return result
    }
}

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

Задача: 720. Longest Word in Dictionary
Сложность: medium

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

Пример:

Input: words = ["w","wo","wor","worl","world"]
Output: "world"

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

1⃣Отсортируйте массив слов по длине и лексикографическому порядку.

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

3⃣Пройдите по каждому слову в отсортированном массиве и добавьте его в множество, если все его префиксы уже существуют в множестве.

😎 Решение:

fun longestWord(words: Array<String>): String {
    words.sort()
    val validWords = mutableSetOf("")
    var longest = ""
    for (word in words) {
        if (validWords.contains(word.dropLast(1))) {
            validWords.add(word)
            if (word.length > longest.length) {
                longest = word
            }
        }
    }
    return longest
}

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

Задача: 302. Smallest Rectangle Enclosing Black Pixels
Сложность: hard

Вам дана бинарная матрица размером m x n, где 0 представляет собой белый пиксель, а 1 представляет собой черный пиксель.
Черные пиксели соединены (то есть существует только одна черная область). Пиксели соединены по горизонтали и вертикали.
Даны два целых числа x и y, которые представляют местоположение одного из черных пикселей. Верните площадь наименьшего (выравненного по осям) прямоугольника, который охватывает все черные пиксели.
Вы должны написать алгоритм со сложностью менее O(mn).

Пример:

Input: image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x = 0, y = 2
Output: 6

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

1⃣Инициализация границ прямоугольника: Инициализируйте переменные left, right, top и bottom. left и top задаются значениями координат (x, y), right и bottom - значениями x + 1 и y + 1 соответственно.

2⃣Обход всех пикселей: Пройдите по всем координатам (x, y) матрицы. Если текущий пиксель является черным (image[x][y] == 1), обновите границы прямоугольника:
left = min(left, x)
right = max(right, x + 1)
top = min(top, y)
bottom = max(bottom, y + 1)

3⃣Вычисление и возврат площади: После завершения обхода матрицы, верните площадь прямоугольника, используя формулу (right - left) * (bottom - top).

😎 Решение:

class Solution {
    fun minArea(image: Array<CharArray>, x: Int, y: Int): Int {
        val m = image.size
        val n = image[0].size
        val left = searchColumns(image, 0, y, 0, m, true)
        val right = searchColumns(image, y + 1, n, 0, m, false)
        val top = searchRows(image, 0, x, left, right, true)
        val bottom = searchRows(image, x + 1, m, left, right, false)
        return (right - left) * (bottom - top)
    }

    private fun searchColumns(image: Array<CharArray>, i: Int, j: Int, top: Int, bottom: Int, whiteToBlack: Boolean): Int {
        var i = i
        var j = j
        while (i != j) {
            var k = top
            val mid = (i + j) / 2
            while (k < bottom && image[k][mid] == '0') {
                k++
            }
            if ((k < bottom) == whiteToBlack) {
                j = mid
            } else {
                i = mid + 1
            }
        }
        return i
    }

    private fun searchRows(image: Array<CharArray>, i: Int, j: Int, left: Int, right: Int, whiteToBlack: Boolean): Int {
        var i = i
        var j = j
        while (i != j) {
            var k = left
            val mid = (i + j) / 2
            while (k < right && image[mid][k] == '0') {
                k++
            }
            if ((k < right) == whiteToBlack) {
                j = mid
            } else {
                i = mid + 1
            }
        }
        return i
    }
}

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

Задача: 1150. Check If a Number Is Majority Element in a Sorted Array
Сложность: easy

Дан целочисленный массив nums, отсортированный в неубывающем порядке, и целое число target. Верните true, если target является элементом большинства, или false в противном случае.

Элемент большинства в массиве nums — это элемент, который встречается в массиве более чем nums.length / 2 раз.

Пример:

Input: nums = [2,4,5,5,5,5,5,6,6], target = 5
Output: true
Explanation: The value 5 appears 5 times and the length of the array is 9.
Thus, 5 is a majority element because 5 > 9/2 is true.

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

1⃣Инициализация переменной count:
Инициализируйте переменную count значением 0..

2⃣Итерация по списку nums:
Пройдите по каждому элементу списка nums.
Если элемент num равен target, увеличьте значение переменной count.

3⃣Проверка условия мажоритарного элемента:
Если count больше чем половина длины списка nums, верните true.
В противном случае верните false.

😎 Решение:

class Solution {
    fun isMajorityElement(nums: IntArray, target: Int): Boolean {
        var count = 0
        for (num in nums) {
            if (num == target) {
                count++
            }
        }
        return count > nums.size / 2
    }
}

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

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

Напишите алгоритм для определения, является ли число n счастливым.

Счастливое число определяется следующим процессом:

Начиная с любого положительного целого числа, замените число суммой квадратов его цифр.
Повторяйте процесс, пока число не станет равным 1 (где оно и останется), или пока оно бесконечно не будет циклически повторяться в цикле, который не включает 1.
Те числа, для которых этот процесс завершается 1, являются счастливыми.
Верните true, если n является счастливым числом, и false, если нет.

Пример:

Input: n = 2
Output: false

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

1⃣Для заданного числа n определите следующее число в последовательности: используйте операторы деления и взятия остатка для последовательного извлечения цифр из числа, пока не закончатся все цифры. Каждую извлеченную цифру возводите в квадрат и суммируйте полученные значения. Это техника "последовательного извлечения цифр" является полезным инструментом для решения множества задач.

2⃣Отслеживайте цепочку чисел и определяйте, не вошли ли вы в цикл, используя структуру данных HashSet. Каждый раз, генерируя следующее число в цепочке, проверяйте, присутствует ли оно уже в HashSet.

3⃣Если числа нет в HashSet, добавьте его туда. Если число уже есть в HashSet, это означает, что вы находитесь в цикле, и следует вернуть false. HashSet используется вместо Vector, List или Array, потому что проверка присутствия числа в HashSet занимает время O(1), тогда как в других структурах данных это займет время O(n). Правильный выбор структур данных является ключевым элементом решения подобных задач.

😎 Решение:

class Solution {
    private fun getNext(n: Int): Int {
        var n = n
        var totalSum = 0
        while (n > 0) {
            val digit = n % 10
            n /= 10
            totalSum += digit * digit
        }
        return totalSum
    }

    fun isHappy(n: Int): Boolean {
        var n = n
        val seen = mutableSetOf<Int>()
        while (n != 1 && n !in seen) {
            seen.add(n)
            n = getNext(n)
        }
        return n == 1
    }
}

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

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

Дан односвязный список.
Нужно отсортировать его с помощью сортировки вставками и вернуть новую голову списка.

Пример:

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

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

1⃣Создайте фиктивный узел dummy, указывающий на начало нового отсортированного списка. Он упростит вставку элементов, в том числе в начало.

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

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

😎 Решение:

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

class Solution {
    fun insertionSortList(head: ListNode?): ListNode? {
        val dummy = ListNode(0)
        var curr = head

        while (curr != null) {
            var prev = dummy
            while (prev.next != null && prev.next!!.`val` <= curr.`val`) {
                prev = prev.next!!
            }
            val next = curr.next
            curr.next = prev.next
            prev.next = curr
            curr = next
        }
        return dummy.next
    }
}

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

Задача: 446. Arithmetic Slices II - Subsequence
Сложность: hard

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

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

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

Например, [2, 5, 10] является подпоследовательностью [1, 2, 1, 2, 4, 1, 5, 10].
Тестовые случаи сгенерированы таким образом, что ответ помещается в 32-битное целое число.

Пример:

Input: nums = [2,4,6,8,10]
Output: 7
Explanation: All arithmetic subsequence slices are:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

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

1⃣Мы можем использовать поиск в глубину (DFS) для генерации всех подпоследовательностей.

2⃣Мы можем проверить, является ли подпоследовательность арифметической, согласно ее определению.

3⃣Возвращаем количество всех арифметических подпоследовательностей.

😎 Решение:

class Solution {
    private var n = 0
    private var ans = 0

    private fun dfs(dep: Int, A: IntArray, cur: MutableList<Long>) {
        if (dep == n) {
            if (cur.size < 3) return
            for (i in 1 until cur.size) {
                if (cur[i] - cur[i - 1] != cur[1] - cur[0]) return
            }
            ans++
            return
        }
        dfs(dep + 1, A, cur)
        cur.add(A[dep].toLong())
        dfs(dep + 1, A, cur)
        cur.removeAt(cur.size - 1)
    }

    fun numberOfArithmeticSlices(A: IntArray): Int {
        n = A.size
        ans = 0
        dfs(0, A, mutableListOf())
        return ans
    }
}

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

Задача: 272. Closest Binary Search Tree Value II
Сложность: hard

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

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

Пример:

Input: root = [4,2,5,1,3], target = 3.714286, k = 2
Output: [4,3]

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

1⃣Выполнить обход дерева в глубину (DFS) и собрать все значения в массив:
Пройти по дереву в глубину, добавляя каждое значение узла в массив.

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

3⃣Вернуть первые k значений из отсортированного массива:
Извлечь первые k элементов из отсортированного массива и вернуть их.

😎 Решение:

class Solution {
    fun closestKValues(root: TreeNode?, target: Double, k: Int): List<Int> {
        val arr = mutableListOf<Int>()
        dfs(root, arr)
        arr.sortBy { Math.abs(it - target) }
        return arr.take(k)
    }
    
    private fun dfs(node: TreeNode?, arr: MutableList<Int>) {
        if (node == null) return
        arr.add(node.`val`)
        dfs(node.left, arr)
        dfs(node.right, arr)
    }
}

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

Задача: 1217. Minimum Cost to Move Chips to The Same Position
Сложность: easy

У нас есть n фишек, где позиция i-й фишки равна position[i].

Нам нужно переместить все фишки в одну и ту же позицию. За один шаг мы можем изменить позицию i-й фишки с position[i] на:
position[i] + 2 или position[i] - 2 с затратами = 0.
position[i] + 1 или position[i] - 1 с затратами = 1.
Верните минимальные затраты, необходимые для перемещения всех фишек в одну и ту же позицию.

Пример:

Input: position = [2,2,2,3,3]
Output: 2
Explanation: We can move the two chips at position  3 to position 2. Each move has cost = 1. The total cost = 2.

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

1⃣Посчитать количество фишек на четных и нечетных позициях.

2⃣Сравнить количество фишек на четных и нечетных позициях.

3⃣Вернуть минимальное количество фишек как минимальную стоимость для перемещения всех фишек в одну позицию.

😎 Решение:

class Solution {
    fun minCostToMoveChips(position: IntArray): Int {
        var evenCount = 0
        var oddCount = 0
        
        for (pos in position) {
            if (pos % 2 == 0) {
                evenCount++
            } else {
                oddCount++
            }
        }
        
        return minOf(evenCount, oddCount)
    }
}

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

Задача: 381. Insert Delete GetRandom O(1) - Duplicates allowed
Сложность: hard

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

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

RandomizedCollection(): Инициализирует пустой объект RandomizedCollection.
bool insert(int val): Вставляет элемент val в мультимножество, даже если элемент уже присутствует. Возвращает true, если элемента не было, и false в противном случае.
bool remove(int val): Удаляет элемент val из мультимножества, если он присутствует. Возвращает true, если элемент присутствовал, и false в противном случае. Если у val несколько вхождений в мультимножестве, удаляется только одно из них.
int getRandom(): Возвращает случайный элемент из текущего мультимножества. Вероятность возврата каждого элемента пропорциональна числу вхождений этого элемента в мультимножество.
Реализуйте функции класса так, чтобы каждая функция работала в среднем за O(1) времени.

Пример:

Input
["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"]
[[], [1], [1], [2], [], [1], []]
Output
[null, true, false, true, 2, true, 1]

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

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

2⃣Метод insert(val): Добавить значение в конец списка и обновить словарь, добавив индекс этого значения. Возвращать true, если значение отсутствовало ранее, и false в противном случае.
Метод remove(val): Удалить одно вхождение значения из словаря и списка. Для удаления значения заменить его последним элементом списка и обновить словарь. Возвращать true, если значение присутствовало, и false в противном случае.

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

😎 Решение:

import kotlin.random.Random

class RandomizedCollection {
    private val dict = mutableMapOf<Int, MutableSet<Int>>()
    private val list = mutableListOf<Int>()

    fun insert(val: Int): Boolean {
        val exists = dict.containsKey(val)
        if (!exists) {
            dict[val] = mutableSetOf()
        }
        dict[val]?.add(list.size)
        list.add(val)
        return !exists
    }

    fun remove(val: Int): Boolean {
        val indices = dict[val] ?: return false
        val index = indices.first()
        indices.remove(index)
        val lastElement = list.removeAt(list.size - 1)
        if (index < list.size) {
            list[index] = lastElement
            dict[lastElement]?.remove(list.size)
            dict[lastElement]?.add(index)
        }
        if (indices.isEmpty()) {
            dict.remove(val)
        }
        return true
    }

    fun getRandom(): Int {
        return list[Random.nextInt(list.size)]
    }
}

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