#hard
Задача: 381. Insert Delete GetRandom O(1) - Duplicates allowed

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>()
    private val list = mutableListOf()

    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)]
    }
}

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

#medium
Задача: 237. Delete Node in a Linked List

Дан односвязный список с головой head, и требуется удалить узел node в этом списке.

Вам дан узел node, который нужно удалить. У вас нет доступа к первому узлу head.

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

Удалите данный узел. Обратите внимание, что под удалением узла мы не подразумеваем его удаление из памяти. Мы имеем в виду:

- Значение данного узла не должно существовать в односвязном списке.
- Количество узлов в односвязном списке должно уменьшиться на один.
- Все значения перед узлом должны оставаться в том же порядке.
- Все значения после узла должны оставаться в том же порядке.

Пример:

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

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

1⃣Копирование данных: Скопируйте значение из следующего узла (node.next) в текущий узел (node). Таким образом, текущий узел будет иметь значение, которое было в следующем узле.

2⃣Обновление указателя: Обновите указатель next текущего узла, чтобы он ссылался на узел, следующий за узлом node.next. Это effectively удалит следующий узел из списка.

3⃣Удаление ссылки на следующий узел: Убедитесь, что следующий узел больше не ссылается на другие узлы, тем самым полностью исключая его из списка.

😎 Решение:

class Solution {
    fun deleteNode(node: ListNode?) {
        node?.`val` = node?.next?.`val` ?: return
        node.next = node.next?.next
    }
}

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

Привет! Меня зовут Миша, и я в IT уже более 6 лет. В настоящий момент живу в Сербии и работаю в крупном финтех продукте на рынке ОАЭ. Участвовал в проектах таких компаний как Raiffeisen, ВТБ, Evotor и других - в основном финтех и крипта.

Мой текущий совокупный доход - более 10к долларов. Пруфы

Средний доход ученика на первом месте работы - 230к. Пруфы

Помогу тебе вкатиться в IT и расскажу, как это сделать максимально эффективно 👍

💸 • Менторинг до оффера
🦝 • Советы по поиску работы
👋 • Бесплатная консультация

#medium
Задача: 339. Nested List Weight Sum

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

Глубина целого числа — это количество списков, в которых оно находится. Например, вложенный список [1,[2,2],[[3],2],1] имеет значения каждого целого числа, установленные в его глубину.

Верните сумму каждого целого числа в nestedList, умноженного на его глубину.

Пример:

Input: nestedList = [1,[4,[6]]]
Output: 27
Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3. 1*1 + 4*2 + 6*3 = 27.

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

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

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

3⃣ Возврат результата:
Возвращайте общую сумму на каждом уровне рекурсии. Основная функция возвращает итоговую сумму.

😎 Решение:

class Solution {
    fun depthSum(nestedList: List): Int {
        return dfs(nestedList, 1)
    }
    
    private fun dfs(list: List, depth: Int): Int {
        var total = 0
        for (nested in list) {
            if (nested.isInteger()) {
                total += nested.getInteger() * depth
            } else {
                total += dfs(nested.getList(), depth + 1)
            }
        }
        return total
    }
}

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

#medium
Задача: 380. Insert Delete GetRandom O(1)

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

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

Пример:

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

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

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

2⃣Метод insert(val): Проверить наличие значения в словаре. Если отсутствует, добавить значение в список и обновить словарь с новым индексом.
Метод remove(val): Проверить наличие значения в словаре. Если присутствует, заменить удаляемое значение последним элементом списка, обновить его индекс в словаре, удалить последний элемент из списка и удалить значение из словаря.

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

😎 Решение:

import kotlin.random.Random

class RandomizedSet {
    private val dict = mutableMapOf()
    private val list = mutableListOf()

    fun insert(val: Int): Boolean {
        if (dict.containsKey(val)) {
            return false
        }
        dict[val] = list.size
        list.add(val)
        return true
    }

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

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

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

#medium
Задача: 236. Lowest Common Ancestor of a Binary Tree

Дано бинарное дерево. Найдите наименьший общий предок (LCA) двух заданных узлов в дереве.

Согласно определению LCA на Википедии: "Наименьший общий предок определяется между двумя узлами p и q как наименьший узел в дереве T, который имеет как p, так и q в качестве потомков (где мы допускаем, что узел может быть потомком самого себя)."

Пример:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

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

1⃣Начало обхода дерева с корня: Начните обход дерева с корневого узла. Если текущий узел является одним из узлов p или q, установите переменную mid в значение True и продолжите поиск другого узла в левой и правой ветвях.

2⃣Проверка поддеревьев: Выполните рекурсивный обход левой и правой ветвей дерева. Если какая-либо из ветвей (левая или правая) возвращает True, это означает, что один из двух узлов найден ниже по дереву.

3⃣Определение LCA: Если в любой момент обхода дерева две из трех переменных (left, right или mid) становятся True, это означает, что найден наименьший общий предок (LCA) для узлов p и q.

😎 Решение:

class Solution {
    private var ans: TreeNode? = null

    private fun recurseTree(currentNode: TreeNode?, p: TreeNode, q: TreeNode): Boolean {
        if (currentNode == null) {
            return false
        }

        val left = if (recurseTree(currentNode.left, p, q)) 1 else 0
        val right = if (recurseTree(currentNode.right, p, q)) 1 else 0
        val mid = if (currentNode == p || currentNode == q) 1 else 0

        if (mid + left + right >= 2) {
            ans = currentNode
        }

        return mid + left + right > 0
    }

    fun lowestCommonAncestor(root: TreeNode?, p: TreeNode, q: TreeNode): TreeNode? {
        recurseTree(root, p, q)
        return ans
    }
}

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

#medium
Задача: 379. Design Phone Directory

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

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

PhoneDirectory(int maxNumbers) Инициализирует телефонный справочник с количеством доступных слотов maxNumbers.
int get() Предоставляет номер, который никому не назначен. Возвращает -1, если номера недоступны.
bool check(int number) Возвращает true, если слот доступен, и false в противном случае.
void release(int number) Перераспределяет или освобождает номер слота.

Пример:

Input
["PhoneDirectory", "get", "get", "check", "get", "check", "release", "check"]
[[3], [], [], [2], [], [2], [2], [2]]
Output
[null, 0, 1, true, 2, false, null, true]

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

1⃣Инициализировать массив isSlotAvailable размером maxNumbers, установив значение true во всех индексах.

2⃣Метод get(): Проходить по массиву isSlotAvailable. Если найдется true на каком-либо индексе, установить isSlotAvailable[i] = false и вернуть i. Если доступных слотов нет, вернуть -1.
Метод check(number): Вернуть значение isSlotAvailable[number].

3⃣Метод release(number): Установить isSlotAvailable[number] = true.

😎 Решение:

class PhoneDirectory(maxNumbers: Int) {
    private val isSlotAvailable = BooleanArray(maxNumbers) { true }

    fun get(): Int {
        for (i in isSlotAvailable.indices) {
            if (isSlotAvailable[i]) {
                isSlotAvailable[i] = false
                return i
            }
        }
        return -1
    }

    fun check(number: Int): Boolean {
        return isSlotAvailable[number]
    }

    fun release(number: Int) {
        isSlotAvailable[number] = true
    }
}

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

Репост:

#medium
Задача: 235. Lowest Common Ancestor of a Binary Search Tree

Дано бинарное дерево поиска (BST). Найдите наименьший общий предок (LCA) двух заданных узлов в BST.

Согласно определению LCA на Википедии: "Наименьший общий предок определяется между двумя узлами p и q как наименьший узел в дереве T, который имеет как p, так и q в качестве потомков (где мы допускаем, что узел может быть потомком самого себя)."

Пример:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

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

1⃣Начало обхода дерева с корня: Начните обход дерева с корневого узла. Проверьте, находятся ли узлы p и q в правом или левом поддереве текущего узла.

2⃣Продолжение поиска в поддереве: Если оба узла p и q находятся в правом поддереве текущего узла, продолжайте поиск в правом поддереве, начиная с шага 1. Если оба узла p и q находятся в левом поддереве текущего узла, продолжайте поиск в левом поддереве, начиная с шага 1.

3⃣Нахождение LCA: Если узлы p и q находятся в разных поддеревьях относительно текущего узла или один из узлов равен текущему узлу, то текущий узел является наименьшим общим предком (LCA). Верните этот узел как результат.

😎 Решение:

class Solution {
    fun lowestCommonAncestor(root: TreeNode?, p: TreeNode, q: TreeNode): TreeNode? {
        val parentVal = root?.`val`
        val pVal = p.`val`
        val qVal = q.`val`

        return if (pVal > parentVal!! && qVal > parentVal) {
            lowestCommonAncestor(root.right, p, q)
        } else if (pVal < parentVal && qVal < parentVal) {
            lowestCommonAncestor(root.left, p, q)
        } else {
            root
        }
    }
}

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

#medium
Задача: 378. Kth Smallest Element in a Sorted Matrix

Дана матрица размером n x n, где каждая строка и каждый столбец отсортированы в порядке возрастания. Верните k-й наименьший элемент в матрице.

Заметьте, что это k-й наименьший элемент в отсортированном порядке, а не k-й уникальный элемент.

Вы должны найти решение с использованием памяти лучше, чем O(n²).

Пример:

Input: matrix = [[-5]], k = 1
Output: -5

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

1⃣Инициализировать мин-кучу H. В нашем решении мы будем рассматривать каждую строку как отдельный список. Поскольку столбцы также отсортированы, мы можем рассматривать каждый столбец как отдельный список.

2⃣Взять первые элементы из min(N, K) строк, где N представляет количество строк, и добавить каждый из этих элементов в кучу. Важно знать, к какой строке и столбцу принадлежит элемент, чтобы в дальнейшем перемещаться по соответствующему списку.

3⃣Мин-куча будет содержать тройки информации (значение, строка, столбец). Куча будет упорядочена по значениям, и мы будем использовать номера строк и столбцов для добавления следующего элемента, если текущий элемент будет удален из кучи.

😎 Решение:

import java.util.PriorityQueue

data class MyHeapNode(val value: Int, val row: Int, val column: Int) : Comparable {
    override fun compareTo(other: MyHeapNode): Int {
        return value - other.value
    }
}

class Solution {
    fun kthSmallest(matrix: Array, k: Int): Int {
        val N = matrix.size
        val minHeap = PriorityQueue()

        for (r in 0 until minOf(N, k)) {
            minHeap.offer(MyHeapNode(matrix[r][0], r, 0))
        }

        var element: MyHeapNode = minHeap.peek()
        var k = k
        while (k > 0) {
            element = minHeap.poll()
            val r = element.row
            val c = element.column

            if (c < N - 1) {
                minHeap.offer(MyHeapNode(matrix[r][c + 1], r, c + 1))
            }
            k -= 1
        }

        return element.value
    }
} 

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

#hard
Задача: 472. Concatenated Words

Дан массив строк words (без дубликатов). Верните все составные слова из данного списка слов.

Составное слово определяется как строка, которая полностью состоит как минимум из двух более коротких слов (не обязательно различных) из данного массива.

Пример:

Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats"; 
"dogcatsdog" can be concatenated by "dog", "cats" and "dog"; 
"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".

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

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

2⃣Использовать поиск в глубину (DFS) для проверки, можно ли достигнуть узел с индексом word.length от узла с индексом 0 в графе.

3⃣Если узел word.length достижим от узла 0, добавить слово в ответ.

😎 Решение:

class Solution {
    private fun dfs(word: String, length: Int, visited: BooleanArray, dictionary: Set): Boolean {
        if (length == word.length) return true
        if (visited[length]) return false
        visited[length] = true
        for (i in word.length - if (length == 0) 1 else 0 downTo length + 1) {
            if (dictionary.contains(word.substring(length, i)) && dfs(word, i, visited, dictionary)) {
                return true
            }
        }
        return false
    }

    fun findAllConcatenatedWordsInADict(words: List): List {
        val dictionary = words.toSet()
        val answer = mutableListOf()
        for (word in words) {
            val visited = BooleanArray(word.length)
            if (dfs(word, 0, visited, dictionary)) {
                answer.add(word)
            }
        }
        return answer
    }
}

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

#medium
Задача: 470. Implement Rand10() Using Rand7()

Дано API rand7(), которое генерирует случайное целое число в диапазоне [1, 7]. Напишите функцию rand10(), которая генерирует случайное целое число в диапазоне [1, 10]. Вы можете вызывать только API rand7(), и не должны вызывать другие API. Пожалуйста, не используйте встроенные в язык функции для генерации случайных чисел.

Каждый тестовый случай будет содержать один внутренний аргумент n, который указывает количество вызовов вашей реализованной функции rand10() во время тестирования. Обратите внимание, что это не аргумент, передаваемый в rand10().

Пример:

Input: n = 1
Output: [2]

😎 Решение:

class Solution {
    fun rand10(): Int {
        var row: Int
        var col: Int
        var idx: Int
        do {
            row = rand7()
            col = rand7()
            idx = col + (row - 1) * 7
        } while (idx > 40)
        return 1 + (idx - 1) % 10
    }
}

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

#easy
Задача: 338. Counting Bits

Дано целое число n, верните массив ans длиной n + 1, такой что для каждого i (0 <= i <= n), ans[i] будет равняться количеству единиц в двоичном представлении числа i.

Пример:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

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

1⃣Инициализация массива:
Создайте массив ans длиной n + 1, заполненный нулями. Этот массив будет содержать количество единиц в двоичном представлении каждого числа от 0 до n.

2⃣Итерация и вычисление:
Пройдите в цикле по всем числам от 1 до n. Для каждого числа x используйте битовую операцию x & (x - 1), чтобы убрать последнюю установленную биту, и добавьте 1 к значению ans для этого результата. Это количество единиц в двоичном представлении числа x.

3⃣Возврат результата:
Верните заполненный массив ans, который содержит количество единиц для каждого числа от 0 до n.

😎 Решение:

class Solution {
    fun countBits(num: Int): IntArray {
        val ans = IntArray(num + 1)
        for (x in 1..num) {
            ans[x] = ans[x and (x - 1)] + 1
        }
        return ans
    }
}

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

#medium
Задача: 468. Validate IP Address

Допустимый IPv4-адрес — это IP в форме "x1.x2.x3.x4", где 0 <= xi <= 255 и xi не может содержать ведущие нули. Например, "192.168.1.1" и "192.168.1.0" являются допустимыми IPv4-адресами, тогда как "192.168.01.1", "192.168.1.00" и "192.168@1.1" являются недопустимыми IPv4-адресами.

Допустимый IPv6-адрес — это IP в форме "x1:x2:x3:x4:x5:x6:x7
", где:
1 <= xi.length <= 4
xi — это шестнадцатеричная строка, которая может содержать цифры, строчные английские буквы ('a' до 'f') и прописные английские буквы ('A' до 'F').
Ведущие нули в xi допускаются.

Пример:

Input: queryIP = "172.16.254.1"
Output: "IPv4"
Explanation: This is a valid IPv4 address, return "IPv4".

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

1⃣Для проверки адреса IPv4:
Разделить IP на четыре части по разделителю ".".
Проверить каждую подстроку:
Является ли она целым числом между 0 и 255.
Не содержит ли она ведущих нулей (исключение — число "0").

2⃣Для проверки адреса IPv6:
Разделить IP на восемь частей по разделителю ":".
Проверить каждую подстроку:
Является ли она шестнадцатеричным числом длиной от 1 до 4 символов.

3⃣Если IP не соответствует ни одному из форматов, вернуть "Neither".

😎 Решение:

class Solution {
    fun validateIPv4(IP: String): String {
        val nums = IP.split(".")
        for (x in nums) {
            if (x.length == 0 || x.length > 3) return "Neither"
            if (x[0] == '0' && x.length != 1) return "Neither"
            for (ch in x) {
                if (!ch.isDigit()) return "Neither"
            }
            if (x.toInt() > 255) return "Neither"
        }
        return "IPv4"
    }

    fun validateIPv6(IP: String): String {
        val nums = IP.split(":")
        val hexdigits = "0123456789abcdefABCDEF"
        for (x in nums) {
            if (x.length == 0 || x.length > 4) return "Neither"
            for (ch in x) {
                if (hexdigits.indexOf(ch) == -1) return "Neither"
            }
        }
        return "IPv6"
    }

    fun validIPAddress(IP: String): String {
        return when {
            IP.count { it == '.' } == 3 -> validateIPv4(IP)
            IP.count { it == ':' } == 7 -> validateIPv6(IP)
            else -> "Neither"
        }
    }
}

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

#medium
Задача: 337. House Robber III

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

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

Пример:

Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

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

1⃣Инициализация и базовый случай:
Создайте вспомогательную функцию helper, которая принимает узел в качестве входных данных и возвращает массив из двух элементов, где первый элемент представляет максимальную сумму денег, которую можно украсть, если не грабить этот узел, а второй элемент - если грабить этот узел.
Базовый случай для вспомогательной функции - узел null, и в этом случае функция возвращает массив из двух нулей [0, 0].

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

3⃣Возврат результата:
В основной функции rob вызовите helper для корня дерева и верните максимальное значение из двух элементов массива, возвращенного функцией helper.

😎 Решение:

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

class Solution {
    fun rob(root: TreeNode?): Int {
        val answer = helper(root)
        return maxOf(answer[0], answer[1])
    }
    
    private fun helper(node: TreeNode?): IntArray {
        if (node == null) return intArrayOf(0, 0)
        
        val left = helper(node.left)
        val right = helper(node.right)
        
        val rob = node.`val` + left[1] + right[1]
        val notRob = maxOf(left[0], left[1]) + maxOf(right[0], right[1])
        
        return intArrayOf(rob, notRob)
    }
}

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

#medium
Задача: 465. Optimal Account Balancing

Дан массив транзакций transactions, где transactions[i] = [fromi, toi, amounti] указывает на то, что человек с ID = fromi дал сумму amounti долларов человеку с ID = toi.

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

Пример:

Input: transactions = [[0,1,10],[2,0,5]]
Output: 2

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

1⃣Создать хеш-таблицу для хранения чистого баланса каждого человека.

2⃣Собрать все ненулевые чистые балансы в массив balance_list.

3⃣Определить рекурсивную функцию dfs(cur) для очистки всех балансов в диапазоне balance_list[0 ~ cur]:
Игнорировать cur, если баланс уже равен 0. Пока balance_list[cur] = 0, переходить к следующему человеку, увеличивая cur на 1.
Если cur = n, вернуть 0.
В противном случае установить cost на большое значение, например, inf.
Пройтись по индексу nxt от cur + 1, если balance_list[nxt] * balance_list[cur] < 0,
Добавить баланс balance_list[cur] к balance_list[nxt]: balance_list[nxt] += balance_list[cur].
Рекурсивно вызвать dfs(cur + 1) как dfs(cur) = 1 + dfs(cur + 1).
Убрать ранее переданный баланс от cur: balance_list[nxt] -= balance_list[cur] (откат).
Повторить с шага 5 и отслеживать минимальное количество операций cost = min(cost, 1 + dfs(cur + 1)), найденных в итерации.
Вернуть cost, когда итерация завершена. Вернуть dfs(0).

😎 Решение:

class Solution {
    private val creditList = mutableListOf()
    
    fun minTransfers(transactions: Array): Int {
        val creditMap = mutableMapOf()
        for (t in transactions) {
            creditMap[t[0]] = creditMap.getOrDefault(t[0], 0) + t[2]
            creditMap[t[1]] = creditMap.getOrDefault(t[1], 0) - t[2]
        }
        
        for (amount in creditMap.values) {
            if (amount != 0) {
                creditList.add(amount)
            }
        }
        
        val n = creditList.size
        return dfs(0, n)
    }
    
    private fun dfs(cur: Int, n: Int): Int {
        var cur = cur
        while (cur < n && creditList[cur] == 0) {
            cur++
        }
        
        if (cur == n) {
            return 0
        }
        
        var cost = Int.MAX_VALUE
        for (nxt in (cur + 1) until n) {
            if (creditList[nxt] * creditList[cur] < 0) {
                creditList[nxt] += creditList[cur]
                cost = minOf(cost, 1 + dfs(cur + 1, n))
                creditList[nxt] -= creditList[cur]
            }
        }
        
        return cost
    }
}

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

#hard
Задача: 336. Palindrome Pairs

Вам дан массив уникальных строк words, индексируемый с 0.

Пара палиндромов — это пара целых чисел (i, j), таких что:
0 <= i, j < words.length,
i != j, и
words[i] + words[j] (конкатенация двух строк) является палиндромом.
Верните массив всех пар палиндромов из слов.

Вы должны написать алгоритм с временной сложностью O(сумма длин всех слов в words).

Пример:

Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]

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

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

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

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

😎 Решение:

class Solution {
    fun palindromePairs(words: Array): List> {
        val pairs = mutableListOf>()
        
        for (i in words.indices) {
            for (j in words.indices) {
                if (i == j) continue
                val combined = words[i] + words[j]
                if (combined == combined.reversed()) {
                    pairs.add(listOf(i, j))
                }
            }
        }
        
        return pairs
    }
}

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

#medium
Задача: 377. Combination Sum IV

Дан массив различных целых чисел nums и целое число target. Верните количество возможных комбинаций, которые в сумме дают target.

Тестовые случаи сгенерированы так, что ответ помещается в 32-битное целое число.

Пример:

Input: nums = [9], target = 3
Output: 0

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

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

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

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

😎 Решение:

class Solution {
    private val memo = mutableMapOf()

    fun combinationSum4(nums: IntArray, target: Int): Int {
        return combs(nums, target)
    }

    private fun combs(nums: IntArray, remain: Int): Int {
        if (remain == 0) return 1
        if (memo.containsKey(remain)) return memo[remain]!!

        var result = 0
        for (num in nums) {
            if (remain - num >= 0) {
                result += combs(nums, remain - num)
            }
        }
        memo[remain] = result
        return result
    }
}

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