Задача: 1672. Richest Customer Wealth
Сложность: easy

Вам дан целочисленный массив размером m x n под названием accounts, где accounts[i][j] — это сумма денег, которую i-й клиент имеет в j-м банке. Верните богатство самого богатого клиента.

Богатство клиента — это сумма денег, которую он имеет во всех своих банковских счетах. Самый богатый клиент — это клиент, который имеет максимальное богатство.

Пример:

Input: accounts = [[1,2,3],[3,2,1]]
Output: 6
Explanation:
1st customer has wealth = 1 + 2 + 3 = 6
2nd customer has wealth = 3 + 2 + 1 = 6
Both customers are considered the richest with a wealth of 6 each, so return 6.

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

1⃣Пройдите по всем клиентам в массиве accounts.

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

3⃣Если текущее богатство больше максимального, обновите максимальное значение. Верните максимальное богатство.

😎 Решение:

class Solution {
    fun maximumWealth(accounts: Array<IntArray>): Int {
        var maxWealthSoFar = 0
        
        for (account in accounts) {
            var currCustomerWealth = account.sum()
            maxWealthSoFar = maxOf(maxWealthSoFar, currCustomerWealth)
        }
        
        return maxWealthSoFar
    }
}

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

Задача: 1519. Number of Nodes in the Sub-Tree With the Same Label
Сложность: medium

Вам дано дерево (т.е. связный неориентированный граф без циклов), состоящее из n узлов, пронумерованных от 0 до n - 1, и ровно n - 1 ребра. Корнем дерева является узел 0, и каждый узел дерева имеет метку, которая является строчной буквой, указанной в строке labels (т.е. узел с номером i имеет метку labels[i]).

Массив edges дан в форме edges[i] = [ai, bi], что означает, что существует ребро между узлами ai и bi в дереве.

Верните массив размера n, где ans[i] — это количество узлов в поддереве узла i, которые имеют ту же метку, что и узел i.

Поддерево дерева T — это дерево, состоящее из узла в T и всех его дочерних узлов.

Пример:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
Output: [2,1,1,1,1,1,1]
Explanation: Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.
Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).

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

1⃣Создайте список смежности, где adj[X] содержит всех соседей узла X.

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

3⃣Начните обход в глубину (DFS).

😎 Решение:

class Solution {
    private fun dfs(node: Int, parent: Int, adj: Map<Int, List<Int>>, labels: CharArray, ans: IntArray): IntArray {
        val nodeCounts = IntArray(26)
        nodeCounts[labels[node] - 'a'] = 1

        adj[node]?.forEach { child ->
            if (child != parent) {
                val childCounts = dfs(child, node, adj, labels, ans)
                for (i in 0 until 26) {
                    nodeCounts[i] += childCounts[i]
                }
            }
        }

        ans[node] = nodeCounts[labels[node] - 'a']
        return nodeCounts
    }

    fun countSubTrees(n: Int, edges: Array<IntArray>, labels: String): IntArray {
        val adj = mutableMapOf<Int, MutableList<Int>>()
        edges.forEach { edge ->
            adj.computeIfAbsent(edge[0]) { mutableListOf() }.add(edge[1])
            adj.computeIfAbsent(edge[1]) { mutableListOf() }.add(edge[0])
        }

        val ans = IntArray(n)
        dfs(0, -1, adj, labels.toCharArray(), ans)
        return ans
    }
}

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

Задача: 435. Non-overlapping Intervals
Сложность: medium

Дан массив интервалов intervals, где intervals[i] = [starti, endi]. Верните минимальное количество интервалов, которые нужно удалить, чтобы остальные интервалы не пересекались.

Пример:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

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

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

2⃣Инициализируйте переменную ответа ans = 0 и целое число k для представления самого последнего времени окончания. k следует инициализировать небольшим значением, например, INT_MIN.

3⃣Итеративно пройдитесь по интервалам. Для каждого интервала: Если время начала больше или равно k, обновите k до времени окончания текущего интервала. В противном случае увеличьте ans. Верните ans.

😎 Решение:

class Solution {
    fun eraseOverlapIntervals(intervals: Array<IntArray>): Int {
        intervals.sortBy { it[1] }
        var ans = 0
        var k = Int.MIN_VALUE
        
        for (interval in intervals) {
            val x = interval[0]
            val y = interval[1]
            if (x >= k) {
                k = y
            } else {
                ans++
            }
        }
        
        return ans
    }
}

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

Задача: 1151. Minimum Swaps to Group All 1's Together
Сложность: medium

Дан бинарный массив data, необходимо вернуть минимальное количество перестановок, чтобы сгруппировать все 1, присутствующие в массиве, вместе в любом месте массива.

Пример:

Input: data = [1,0,1,0,1]
Output: 1
Explanation: There are 3 ways to group all 1's together:
[1,1,1,0,0] using 1 swap.
[0,1,1,1,0] using 2 swaps.
[0,0,1,1,1] using 1 swap.
The minimum is 1.

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

1⃣Используем два указателя, left и right, чтобы поддерживать скользящее окно длиной ones и проверяем каждый фрагмент массива data, подсчитывая количество единиц в нем (cnt_one) и запоминая максимальное значение max_one.

2⃣Пока окно скользит по массиву data, поддерживаем его длину равной ones.

3⃣Обновляем количество единиц в окне, добавляя новую границу data[right] и вычитая левую границу data[left].

😎 Решение:

class Solution {
    fun minSwaps(data: IntArray): Int {
        val ones = data.sum()
        var cnt_one = 0
        var max_one = 0
        var left = 0
        var right = 0

        while (right < data.size) {
            cnt_one += data[right]
            right += 1
            if (right - left > ones) {
                cnt_one -= data[left]
                left += 1
            }
            max_one = Math.max(max_one, cnt_one)
        }
        return ones - max_one
    }
}

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

Задача: 1278. Palindrome Partitioning III
Сложность: hard

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

Пример:

Input: s = "abc", k = 2
Output: 1

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

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

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

3⃣Верните минимальное количество изменений, найденное во втором шаге.

😎 Решение:

class Solution {
    fun minChangesToMakePalindrome(s: String, k: Int): Int {
        val n = s.length

        fun minChangeToPalindrome(i: Int, j: Int): Int {
            var changes = 0
            var i = i
            var j = j
            while (i < j) {
                if (s[i] != s[j]) {
                    changes++
                }
                i++
                j--
            }
            return changes
        }

        val dp1 = Array(n) { IntArray(n) }
        for (length in 1..n) {
            for (i in 0..n - length) {
                val j = i + length - 1
                dp1[i][j] = minChangeToPalindrome(i, j)
            }
        }

        val dp2 = Array(n + 1) { IntArray(k + 1) { Int.MAX_VALUE } }
        dp2[0][0] = 0

        for (i in 1..n) {
            for (kk in 1..k) {
                for (j in 0 until i) {
                    dp2[i][kk] = minOf(dp2[i][kk], dp2[j][kk - 1] + dp1[j][i - 1])
                }
            }
        }

        return dp2[n][k]
    }
}

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

Задача: 382. Linked List Random Node
Сложность: medium

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

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

Solution(ListNode head) Инициализирует объект с головой односвязного списка head.
int getRandom() Выбирает узел случайным образом из списка и возвращает его значение. Все узлы списка должны иметь равные шансы быть выбранными.

Пример:

Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]

Explanation
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // return 1
solution.getRandom(); // return 3
solution.getRandom(); // return 2
solution.getRandom(); // return 2
solution.getRandom(); // return 3
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.

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

1⃣Реализуйте интерфейс init(head), который будет вызываться при создании объекта. Преобразуйте связанный список в массив для дальнейшего использования.

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

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

😎 Решение:

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

class Solution(head: ListNode?) {
    private val range = mutableListOf<Int>()

    init {
        var current = head
        while (current != null) {
            range.add(current.`val`)
            current = current.next
        }
    }

    fun getRandom(): Int {
        val pick = (0 until range.size).random()
        return range[pick]
    }
}

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

Задача: 215. Kth Largest Element in an Array
Сложность: medium

Дан целочисленный массив nums и целое число k. Верните k-й наибольший элемент в массиве.

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

Пример:

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

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

1⃣Отсортируйте массив в порядке убывания:
Используйте стандартную функцию сортировки для сортировки элементов массива nums в порядке убывания. В этом случае самый большой элемент будет первым в массиве, второй по величине - вторым и так далее.

2⃣Найдите k-й по величине элемент:
После сортировки просто верните элемент, который стоит на позиции k-1 (учитывая, что индексация в массиве начинается с 0).

3⃣Верните результат:
Возвратите найденное значение как результат.

😎 Решение:

class Solution {
    fun shortestPalindrome(s: String): String {
        val n = s.length
        val rev = s.reversed()
        for (i in 0 until n) {
            if (s.substring(0, n - i) == rev.substring(i)) {
                return rev.substring(0, i) + s
            }
        }
        return ""
    }
}

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

Задача: 38. Count and Say
Сложность medium

Последовательность "считай и скажи" определяется рекурсивно:
- countAndSay(1) = "1"
- countAndSay(n) — это кодирование длин серий (RLE) из countAndSay(n - 1).

Пример:

Input: n = 4  
Output: "1211"  

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

1⃣Начинаем с "1" и итеративно строим последовательность до n.

2⃣Используем Regex для поиска повторяющихся символов ((.)\1*).

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

😎 Решение:

class Solution {
    fun countAndSay(n: Int): String {
        var s = "1"
        for (i in 2..n) {
            var t = ""
            val regex = Regex("(.)\\1*")
            regex.findAll(s).forEach { match ->
                t += "${match.value.length}${match.value[0]}"
            }
            s = t
        }
        return s
    }
}

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

Задача: 1514. Path with Maximum Probability
Сложность: medium

Вам дан неориентированный взвешенный граф из n узлов (индексация с нуля), представленный списком ребер, где edges[i] = [a, b] является неориентированным ребром, соединяющим узлы a и b с вероятностью успешного прохождения этого ребра succProb[i].

Даны два узла start и end, найдите путь с максимальной вероятностью успеха, чтобы перейти от start к end, и верните его вероятность успеха.

Если пути от start до end не существует, верните 0. Ваш ответ будет принят, если он отличается от правильного ответа не более чем на 1e-5.

Пример:

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
Output: 0.25000
Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.

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

1⃣Инициализируйте массив maxProb как максимальную вероятность достижения каждого узла из начального узла, установите maxProb[start] равным 1.

2⃣Расслабьте все ребра: для каждого ребра (u, v), если найдена более высокая вероятность достижения u через это ребро, обновите max_prob[u] как max_prob[u] = max_prob[v] * path_prob. Если найдена более высокая вероятность достижения v через это ребро, обновите max_prob[v].

3⃣Если нам не удается обновить какой-либо узел с более высокой вероятностью, мы можем остановить итерацию, перейдя к шагу 4. В противном случае повторяйте шаг 2, пока все ребра не будут расслаблены n - 1 раз.
Верните max_prob[end].

😎 Решение:

class Solution {
    fun maxProbability(n: Int, edges: Array<IntArray>, succProb: DoubleArray, start: Int, end: Int): Double {
        val maxProb = DoubleArray(n)
        maxProb[start] = 1.0

        for (i in 0 until n - 1) {
            var hasUpdate = false
            for (j in edges.indices) {
                val u = edges[j][0]
                val v = edges[j][1]
                val pathProb = succProb[j]
                if (maxProb[u] * pathProb > maxProb[v]) {
                    maxProb[v] = maxProb[u] * pathProb
                    hasUpdate = true
                }
                if (maxProb[v] * pathProb > maxProb[u]) {
                    maxProb[u] = maxProb[v] * pathProb
                    hasUpdate = true
                }
            }
            if (!hasUpdate) {
                break
            }
        }

        return maxProb[end]
    }
}

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

Задача: 344. Reverse String
Сложность: easy

Напишите функцию, которая переворачивает строку. Входная строка представлена в виде массива символов s.

Вы должны сделать это, изменяя входной массив на месте с использованием O(1) дополнительной памяти.

Пример:

Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

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

1⃣Инициализация указателей:
Установите два указателя: один на начало массива (left), другой на конец массива (right).

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

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

😎 Решение:

class Solution {
    fun reverseString(s: CharArray): Unit {
        var left = 0
        var right = s.size - 1
        while (left < right) {
            val temp = s[left]
            s[left] = s[right]
            s[right] = temp
            left++
            right--
        }
    }
}

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

Задача: 516. Longest Palindromic Subsequence
Сложность: medium

Дана строка s, найдите длину самой длинной палиндромной подпоследовательности в s.

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

Пример:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

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

1⃣Создайте целочисленную переменную n и инициализируйте её размером строки s. Создайте двумерный массив memo размером n на n, где memo[i][j] содержит длину самой длинной палиндромной подпоследовательности подстроки, сформированной от индекса i до j в s.

2⃣Верните lps(s, 0, n - 1, memo), где lps — это рекурсивный метод с четырьмя параметрами: s, начальный индекс подстроки как i, конечный индекс подстроки как j и memo. Если memo[i][j] != 0, это означает, что мы уже решили эту подзадачу, поэтому возвращаем memo[i][j]. Если i > j, строка пуста, возвращаем 0. Если i == j, это подстрока, содержащая один символ, возвращаем 1.

3⃣Если первый и последний символы совпадают, т.е. s[i] == s[j], включаем эти два символа в палиндромную подпоследовательность и добавляем её к самой длинной палиндромной подпоследовательности, сформированной с использованием подстроки от индекса i + 1 до j - 1. Выполняем memo[i][j] = lps(s, i + 1, j - 1, memo) + 2. Если первый и последний символы не совпадают, рекурсивно ищем самую длинную палиндромную подпоследовательность в обеих подстроках, сформированных после игнорирования первого и последнего символов. Выбираем максимум из этих двух и выполняем memo[i][j] = max(lps(s, i + 1, j, memo), lps(s, i, j - 1, memo)). Возвращаем memo[i][j].

😎 Решение:

class Solution {
    fun longestPalindromeSubseq(s: String): Int {
        val n = s.length
        val memo = mutableMapOf<Pair<Int, Int>, Int>()
        
        fun lps(l: Int, r: Int): Int {
            if (memo.containsKey(l to r)) return memo[l to r]!!
            if (l > r) return 0
            if (l == r) return 1
            
            val res = if (s[l] == s[r]) {
                lps(l + 1, r - 1) + 2
            } else {
                maxOf(lps(l, r - 1), lps(l + 1, r))
            }
            memo[l to r] = res
            return res
        }
        
        return lps(0, n - 1)
    }
}

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

Задача: 409. Longest Palindrome
Сложность: easy

Если задана строка s, состоящая из строчных или прописных букв, верните длину самого длинного палиндрома, который можно построить из этих букв. Буквы чувствительны к регистру, например, "Aa" не считается палиндромом.

Пример:

Input: s = "abccccdd"
Output: 7

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

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

2⃣Пройдитесь по словарю и добавьте четное количество каждого символа к длине палиндрома. Если встречается нечетное количество символа, добавьте (count - 1) к длине палиндрома.

3⃣Если есть хотя бы один символ с нечетным количеством, добавьте 1 к длине палиндрома для центрального символа.

😎 Решение:

fun longestPalindrome(s: String): Int {
    val charCount = mutableMapOf<Char, Int>()
    for (char in s) {
        charCount[char] = charCount.getOrDefault(char, 0) + 1
    }
    var length = 0
    var oddFound = false
    for (count in charCount.values) {
        if (count % 2 == 0) {
            length += count
        } else {
            length += count - 1
            oddFound = true
        }
    }
    return if (oddFound) length + 1 else length
}

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

Задача: 679. 24 Game
Сложность: hard

Дан массив целых чисел cards длиной 4. У вас есть четыре карты, каждая из которых содержит число в диапазоне от 1 до 9. Вам нужно расположить числа на этих картах в математическом выражении, используя операторы ['+', '-', '*', '/'] и скобки '(' и ')' так, чтобы получить значение 24.

Вы ограничены следующими правилами:

Оператор деления '/' представляет собой реальное деление, а не целочисленное деление.
Например, 4 / (1 - 2 / 3) = 4 / (1 / 3) = 12.
Каждая операция выполняется между двумя числами. В частности, мы не можем использовать '-' как унарный оператор.
Например, если cards = [1, 1, 1, 1], выражение "-1 - 1 - 1 - 1" не допускается.
Вы не можете объединять числа вместе.
Например, если cards = [1, 2, 1, 2], выражение "12 + 12" недопустимо.
Вернуть true, если вы можете получить такое выражение, которое оценивается в 24, и false в противном случае.

Пример:

Input: cards = [4,1,8,7]
Output: true
Explanation: (8-4) * (7-1) = 24

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

1⃣Создайте функцию generatePossibleResults(a, b), которая возвращает массив результатов всех возможных математических операций над двумя числами.

2⃣ Создайте функцию checkIfResultReached(list), чтобы проверить, можем ли мы достичь результата 24, используя текущий массив list. Сначала проверьте базовые условия: если размер массива равен 1, верните true, если результат равен 24, иначе верните false.

3⃣Если размер массива больше 1, выберите любые два числа из списка, выполните все математические операции над ними, создайте новый список с обновленными элементами и снова вызовите рекурсивную функцию с этим новым списком. Если ни одна комбинация не приводит к результату 24, верните false. Вызовите checkIfResultReached с исходным списком карт.

😎 Решение:

class Solution {
    fun generatePossibleResults(a: Double, b: Double): List<Double> {
        val res = mutableListOf(a + b, a - b, b - a, a * b)
        if (a != 0.0) res.add(b / a)
        if (b != 0.0) res.add(a / b)
        return res
    }

    fun checkIfResultReached(list: MutableList<Double>): Boolean {
        if (list.size == 1) return Math.abs(list[0] - 24) <= 0.1

        for (i in list.indices) {
            for (j in i + 1 until list.size) {
                val newList = mutableListOf<Double>()
                for (k in list.indices) {
                    if (k != i && k != j) newList.add(list[k])
                }
                for (res in generatePossibleResults(list[i], list[j])) {
                    newList.add(res)
                    if (checkIfResultReached(newList)) return true
                    newList.removeAt(newList.size - 1)
                }
            }
        }
        return false
    }

    fun judgePoint24(cards: IntArray): Boolean {
        val list = cards.map { it.toDouble() }.toMutableList()
        return checkIfResultReached(list)
    }
}

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

Задача: 95. Unique Binary Search Trees II
Сложность: medium

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

Пример:

Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

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

1⃣Создайте хеш-карту memo, где memo[(start, end)] содержит список корневых узлов всех возможных BST (деревьев бинарного поиска) с диапазоном значений узлов от start до end. Реализуем рекурсивную функцию allPossibleBST, которая принимает начальный диапазон значений узлов start, конечный диапазон end и memo в качестве параметров. Она возвращает список TreeNode, соответствующих всем BST, которые могут быть сформированы с этим диапазоном значений узлов. Вызываем allPossibleBST(1, n, memo) и выполняем следующее:

2⃣Объявляем список TreeNode под названием res для хранения списка корневых узлов всех возможных BST. Если start > end, мы добавляем null в res и возвращаем его. Если мы уже решили эту подзадачу, т.е. memo содержит пару (start, end), мы возвращаем memo[(start, end)].

3⃣Выбираем значение корневого узла от i = start до end, увеличивая i на 1 после каждой итерации. Рекурсивно вызываем leftSubtrees = allPossibleBST(start, i - 1, memo) и rightSubTrees = allPossibleBST(i + 1, end, memo). Перебираем все пары между leftSubtrees и rightSubTrees и создаем новый корень со значением i для каждой пары. Добавляем корень новообразованного BST в res. Устанавливаем memo[(start, end)] = res и возвращаем res.

😎 Решение:

class TreeNode(val value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

class Solution {
    fun allPossibleBST(start: Int, end: Int, memo: MutableMap<Pair<Int, Int>, List<TreeNode?>>): List<TreeNode?> {
        if (start > end) return listOf(null)
        val key = Pair(start, end)
        memo[key]?.let { return it }

        val res = mutableListOf<TreeNode?>()
        for (i in start..end) {
            val leftSubTrees = allPossibleBST(start, i - 1, memo)
            val rightSubTrees = allPossibleBST(i + 1, end, memo)
            for (left in leftSubTrees) {
                for (right in rightSubTrees) {
                    res.add(TreeNode(i, left, right))
                }
            }
        }
        memo[key] = res
        return res
    }

    fun generateTrees(n: Int): List<TreeNode?> {
        val memo = mutableMapOf<Pair<Int, Int>, List<TreeNode?>>()
        return allPossibleBST(1, n, memo)
    }
}

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

Задача: 834. Sum of Distances in Tree
Сложность: hard

Есть неориентированное связное дерево с n узлами, пронумерованными от 0 до n - 1, и n - 1 ребрами.

Вам даны целое число n и массив edges, где edges[i] = [ai, bi] указывает, что существует ребро между узлами ai и bi в дереве.

Верните массив answer длиной n, где answer[i] — это сумма расстояний между i-м узлом в дереве и всеми другими узлами.

Пример:

Input: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Output: [8,12,6,10,10,10]
Explanation: The tree is shown above.
We can see that dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)
equals 1 + 1 + 2 + 2 + 2 = 8.
Hence, answer[0] = 8, and so on.

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

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

2⃣На основе полученных данных рассчитайте сумму расстояний для корня дерева.

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

😎 Решение:

class Solution {
    private lateinit var ans: IntArray
    private lateinit var count: IntArray
    private lateinit var graph: Array<MutableSet<Int>>
    private var N: Int = 0

    fun sumOfDistancesInTree(N: Int, edges: Array<IntArray>): IntArray {
        this.N = N
        graph = Array(N) { mutableSetOf<Int>() }
        ans = IntArray(N)
        count = IntArray(N) { 1 }

        for (edge in edges) {
            graph[edge[0]].add(edge[1])
            graph[edge[1]].add(edge[0])
        }

        dfs(0, -1)
        dfs2(0, -1)
        return ans
    }

    private fun dfs(node: Int, parent: Int) {
        for (child in graph[node]) {
            if (child != parent) {
                dfs(child, node)
                count[node] += count[child]
                ans[node] += ans[child] + count[child]
            }
        }
    }

    private fun dfs2(node: Int, parent: Int) {
        for (child in graph[node]) {
            if (child != parent) {
                ans[child] = ans[node] - count[child] + N - count[child]
                dfs2(child, node)
            }
        }
    }

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

Задача: 1192. Critical Connections in a Network
Сложность: hard

Существует n серверов, пронумерованных от 0 до n - 1, соединенных неориентированными соединениями "сервер-сервер", образуя сеть, где connections[i] = [ai, bi] представляет собой соединение между серверами ai и bi. Любой сервер может достичь других серверов напрямую или косвенно через сеть.

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

Пример:

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.

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

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

2⃣Поиск в глубину (DFS):
Реализуйте функцию dfs для обхода графа.
Обновите ранги узлов и определите минимальный ранг для текущего узла.
Проверьте, можно ли удалить текущее соединение, и обновите минимальный ранг.

3⃣Поиск критических соединений:
После завершения обхода DFS преобразуйте оставшиеся соединения в список и верните его.

😎 Решение:

class Solution {
    private val graph = mutableMapOf<Int, MutableList<Int>>()
    private val rank = mutableMapOf<Int, Int?>()
    private val connDict = mutableMapOf<Pair<Int, Int>, Boolean>()
    
    fun criticalConnections(n: Int, connections: List<List<Int>>): List<List<Int>> {
        formGraph(n, connections)
        dfs(0, 0)
        val result = mutableListOf<List<Int>>()
        for (conn in connDict.keys) {
            result.add(listOf(conn.first, conn.second))
        }
        return result
    }
    
    private fun dfs(node: Int, discoveryRank: Int): Int {
        if (rank[node] != null) {
            return rank[node]!!
        }
        
        rank[node] = discoveryRank
        var minRank = discoveryRank + 1
        
        for (neighbor in graph[node]!!) {
            val neighRank = rank[neighbor]
            if (neighRank != null && neighRank == discoveryRank - 1) {
                continue
            }
            
            val recursiveRank = dfs(neighbor, discoveryRank + 1)
            
            if (recursiveRank <= discoveryRank) {
                connDict.remove(Pair(min(node, neighbor), max(node, neighbor)))
            }
            
            minRank = minOf(minRank, recursiveRank)
        }
        
        return minRank
    }
    
    private fun formGraph(n: Int, connections: List<List<Int>>) {
        for (i in 0 until n) {
            graph[i] = mutableListOf()
            rank[i] = null
        }
        
        for (edge in connections) {
            val u = edge[0]
            val v = edge[1]
            graph[u]!!.add(v)
            graph[v]!!.add(u)
            connDict[Pair(min(u, v), max(u, v))] = true
        }
    }
}

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