Задача: 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
        }
    }
}

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

Задача: 556. Next Greater Element III
Сложность: medium

Мы можем перемешать строку s, чтобы получить строку t, используя следующий алгоритм:

Дано положительное целое число n. Найдите наименьшее целое число, которое имеет точно такие же цифры, как и число n, и больше самого числа n по значению. Если такого положительного целого числа не существует, верните -1.

Учтите, что возвращенное число должно помещаться в 32-битное целое число. Если существует допустимый ответ, но он не помещается в 32-битное целое число, верните -1.

Пример:

Input: n = 12
Output: 21

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

1⃣Нахождение и перестановка цифр
Преобразуйте число n в массив цифр. Найдите первую цифру, которая нарушает убывающий порядок (с конца массива). Назовем её индексом i. Найдите первую цифру, которая больше digits[i-1] (с конца массива). Назовем её индексом j. Поменяйте местами цифры на позициях i-1 и j.

2⃣Обратный порядок оставшихся цифр
Обратный порядок части массива от индекса i до конца, чтобы получить наименьшую перестановку, которая больше исходной.

3⃣Проверка результата и преобразование обратно в число
Преобразуйте массив цифр обратно в число. Если число превышает 32-битный предел, верните -1. В противном случае верните полученное число.

😎 Решение:

class Solution {
    private fun swap(s: String, i0: Int, i1: Int): String {
        if (i0 == i1) return s
        val chars = s.toCharArray()
        val temp = chars[i0]
        chars[i0] = chars[i1]
        chars[i1] = temp
        return String(chars)
    }
    
    private val list = mutableListOf<String>()
    
    private fun permute(a: String, l: Int, r: Int) {
        if (l == r) {
            list.add(a)
        } else {
            var a = a
            for (i in l..r) {
                a = swap(a, l, i)
                permute(a, l + 1, r)
                a = swap(a, l, i)
            }
        }
    }
    
    fun nextGreaterElement(n: Int): Int {
        val s = n.toString()
        permute(s, 0, s.length - 1)
        list.sort()
        val index = list.indexOf(s)
        if (index != -1 && index < list.size - 1) {
            val result = list[index + 1].toInt()
            if (result <= Int.MAX_VALUE) return result
        }
        return -1
    }
}

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

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

Даны две строки text1 и text2. Верните длину их наибольшей общей подпоследовательности. Если общей подпоследовательности нет, верните 0.

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

Пример:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

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

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

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

3⃣Возвращайте значение memoSolve(0, 0), чтобы получить результат для всей строки.

😎 Решение:

class Solution {
    private lateinit var memo: Array<IntArray>
    private lateinit var text1: String
    private lateinit var text2: String

    fun longestCommonSubsequence(text1: String, text2: String): Int {
        this.text1 = text1
        this.text2 = text2
        memo = Array(text1.length + 1) { IntArray(text2.length + 1) { -1 } }
        return memoSolve(0, 0)
    }

    private fun memoSolve(p1: Int, p2: Int): Int {
        if (p1 == text1.length || p2 == text2.length) return 0
        if (memo[p1][p2] != -1) return memo[p1][p2]
        val answer: Int
        if (text1[p1] == text2[p2]) {
            answer = 1 + memoSolve(p1 + 1, p2 + 1)
        } else {
            answer = maxOf(memoSolve(p1, p2 + 1), memoSolve(p1 + 1, p2))
        }
        memo[p1][p2] = answer
        return answer
    }
}

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