Задача: 498. Diagonal Traverse
Сложность: medium

Дан массив m x n матрицы mat, верните массив всех элементов матрицы в диагональном порядке.

Пример:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]

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

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

2⃣Итерация по диагоналям
Внешний цикл для прохождения по всем диагоналям. Головы диагоналей находятся в первой строке и последнем столбце. Внутренний цикл для итерации по элементам каждой диагонали. Индексы элементов диагонали изменяются до выхода за пределы матрицы.

3⃣Обработка диагоналей
Для каждой диагонали сохраните её элементы в списке intermediate. Переверните элементы диагонали, если её номер чётный. Добавьте элементы диагонали в массив result.

😎 Решение:

class Solution {
    fun findDiagonalOrder(mat: Array<IntArray>): IntArray {
        if (mat.isEmpty()) return intArrayOf()
        val N = mat.size
        val M = mat[0].size
        val result = mutableListOf<Int>()
        
        for (d in 0 until N + M - 1) {
            val intermediate = mutableListOf<Int>()
            var r = if (d < M) 0 else d - M + 1
            var c = if (d < M) d else M - 1
            
            while (r < N && c >= 0) {
                intermediate.add(mat[r][c])
                r++
                c--
            }
            
            if (d % 2 == 0) {
                result.addAll(intermediate.reversed())
            } else {
                result.addAll(intermediate)
            }
        }
        
        return result.toIntArray()
    }
}

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

Задача: 506. Relative Ranks
Сложность: easy

Вам дан целочисленный массив score размером n, где score[i] — это результат i-го спортсмена на соревновании. Все результаты гарантированно уникальны.
Спортсмены размещаются на основе своих результатов: спортсмен, занявший 1-е место, имеет наивысший результат, спортсмен, занявший 2-е место, имеет второй по величине результат и так далее. Размещение каждого спортсмена определяет его ранг:
Ранг спортсмена, занявшего 1-е место, — "Gold Medal".
Ранг спортсмена, занявшего 2-е место, — "Silver Medal".
Ранг спортсмена, занявшего 3-е место, — "Bronze Medal".
Для спортсменов, занявших с 4-го по n-е место, их ранг соответствует их номеру в размещении (т.е. ранг спортсмена, занявшего x-е место, — "x").
Верните массив answer размером n, где answer[i] — это ранг i-го спортсмена.

Пример:

Input: score = [5,4,3,2,1]
Output: ["Gold Medal","Silver Medal","Bronze Medal","4","5"]
Explanation: The placements are [1st, 2nd, 3rd, 4th, 5th].

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

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

2⃣Создание вспомогательных структур
Инициализируйте массив scoreToIndex размером M + 1, где M — это максимальное значение в массиве score. Заполните scoreToIndex таким образом, чтобы для каждого score[i] его индекс сохранялся в scoreToIndex[score[i]].

3⃣Присваивание рангов и формирование ответа
Создайте массив rank для хранения рангов спортсменов. Используйте цикл для присваивания медалей и рангов в зависимости от значений в scoreToIndex, начиная с наибольшего.

😎 Решение:

class Solution {
    fun findRelativeRanks(score: IntArray): Array<String> {
        val N = score.size
        val maxScore = score.maxOrNull()!!
        val scoreToIndex = IntArray(maxScore + 1)
        
        for (i in score.indices) {
            scoreToIndex[score[i]] = i + 1
        }
        
        val MEDALS = arrayOf("Gold Medal", "Silver Medal", "Bronze Medal")
        val rank = Array(N) { "" }
        var place = 1
        
        for (i in maxScore downTo 0) {
            if (scoreToIndex[i] != 0) {
                val originalIndex = scoreToIndex[i] - 1
                rank[originalIndex] = if (place < 4) MEDALS[place - 1] else place.toString()
                place++
            }
        }
        
        return rank
    }
}

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

Задача: 906. Super Palindromes
Сложность: hard

Если задан целочисленный массив nums, переместите все четные числа в начало массива, а затем все нечетные. Верните любой массив, удовлетворяющий этому условию.

Пример:

Input: left = "4", right = "1000"
Output: 4

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

1⃣Найти все палиндромы до корня из right.

2⃣Проверить, являются ли квадраты этих палиндромов палиндромами и лежат ли в диапазоне [left, right].

3⃣Подсчитать количество таких суперпалиндромов.

😎 Решение:

class Solution {
    fun isPalindrome(x: Long): Boolean {
        val s = x.toString()
        return s == s.reversed()
    }

    fun superpalindromesInRange(left: String, right: String): Int {
        val leftNum = left.toLong()
        val rightNum = right.toLong()
        var count = 0

        for (i in 1 until 100000) {
            val s = i.toString()
            val palin1 = (s + s.reversed()).toLong()
            val palin2 = (s + s.dropLast(1).reversed()).toLong()

            if (palin1 * palin1 > rightNum) {
                break
            }
            if (palin1 * palin1 >= leftNum && isPalindrome(palin1 * palin1)) {
                count++
            }
            if (palin2 * palin2 >= leftNum && palin2 * palin2 <= rightNum && isPalindrome(palin2 * palin2)) {
                count++
            }
        }

        return count
    }
}

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

Задача: 518. Coin Change II
Сложность: medium

Вам дан целочисленный массив coins, представляющий монеты разных номиналов, и целое число amount, представляющее общую сумму денег.

Верните количество комбинаций, которые составляют эту сумму. Если эту сумму нельзя составить никакой комбинацией монет, верните 0.

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

Ответ гарантированно вписывается в знаковое 32-битное целое число.

Пример:

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

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

1⃣Создайте двумерный массив memo с n строками и amount + 1 столбцами. Инициализируйте значения -1, чтобы указать, что подзадача еще не решена. Реализуйте рекурсивный метод numberOfWays, который принимает два параметра: индекс i текущей рассматриваемой монеты и оставшуюся сумму, которую нужно составить. Он возвращает количество способов составить сумму, используя монеты, начиная с индекса i до последней монеты.

2⃣Если amount == 0, верните 1. Мы можем выбрать один способ, не выбирая ни одной монеты, чтобы составить сумму 0. Если i == n, у нас не осталось монет для составления суммы, верните 0. Если эта подзадача уже решена, т.е. memo[i][amount] != -1, верните memo[i][amount]. Если значение текущей монеты превышает сумму, мы не можем её использовать. Рекурсивно вызовите numberOfWays(i + 1, amount), присвойте результат memo[i][amount] и верните его.

3⃣В противном случае, добавьте общее количество способов составить сумму, как выбирая текущую монету, так и игнорируя её. Сложите значения numberOfWays(i, amount - coins[i]) и numberOfWays(i + 1, amount), сохраните результат в memo[i][amount] и верните его. Верните numberOfWays(0, amount), ответ на исходную задачу.

😎 Решение:

class Solution {
    fun change(amount: Int, coins: IntArray): Int {
        val memo = Array(coins.size) { IntArray(amount + 1) { -1 } }
        
        fun numberOfWays(i: Int, amount: Int): Int {
            if (amount == 0) return 1
            if (i == coins.size) return 0
            if (memo[i][amount] != -1) return memo[i][amount]
            
            memo[i][amount] = if (coins[i] > amount) {
                numberOfWays(i + 1, amount)
            } else {
                numberOfWays(i, amount - coins[i]) + numberOfWays(i + 1, amount)
            }
            return memo[i][amount]
        }
        
        return numberOfWays(0, amount)
    }
}

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

Задача: 231. Power of Two
Сложность: easy

Дано целое число n, верните true, если оно является степенью двойки. В противном случае верните false.

Целое число n является степенью двойки, если существует целое число x, такое что n == 2^x.

Пример:

Input: n = 1
Output: true
Explanation: 2^0 = 1

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

1⃣Проверка на ноль: Если n равно нулю, верните false, так как ноль не является степенью двойки.

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

3⃣Побитовая проверка: Используйте побитовую операцию, чтобы проверить, является ли число степенью двойки. Число является степенью двойки, если результат выражения (x & (-x)) равен x.

😎 Решение:

class Solution {
    fun isPowerOfTwo(n: Int): Boolean {
        if (n == 0) return false
        val x = n.toLong()
        return (x and -x) == x
    }
}

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

Задача: 935. Knight Dialer
Сложность: medium

Шахматный конь обладает уникальным движением: он может перемещаться на две клетки по вертикали и одну клетку по горизонтали, или на две клетки по горизонтали и одну клетку по вертикали (при этом обе клетки образуют форму буквы L). Возможные движения шахматного коня показаны на этой диаграмме: Шахматный конь может двигаться так, как показано на шахматной диаграмме ниже: У нас есть шахматный конь и телефонная панель, как показано ниже, конь может стоять только на числовой клетке (то есть на синей клетке).


Учитывая целое число n, верните, сколько различных телефонных номеров длины n мы можем набрать. Вам разрешается сначала поставить коня на любую цифровую клетку, а затем выполнить n - 1 прыжков, чтобы набрать номер длины n. Все прыжки должны быть правильными прыжками коня. Поскольку ответ может быть очень большим, верните ответ по модулю 10^9 + 7.

Пример:

Input: n = 1
Output: 10

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

1⃣Определить возможные движения коня с каждой цифровой клетки.
Использовать динамическое программирование для хранения количества способов достижения каждой цифровой клетки на каждом шаге.

2⃣Инициализировать массив DP количеством способов набора телефонного номера длины 1 для каждой цифровой клетки (это просто 1).
На каждом шаге обновлять массив DP, переходя по всем возможным движениям коня.

3⃣Вернуть сумму всех значений в массиве DP на последнем шаге.

😎 Решение:

class Solution {
    fun knightDialer(n: Int): Int {
        val MOD = 1000000007
        val moves = arrayOf(
            intArrayOf(4, 6),
            intArrayOf(6, 8),
            intArrayOf(7, 9),
            intArrayOf(4, 8),
            intArrayOf(0, 3, 9),
            intArrayOf(),
            intArrayOf(0, 1, 7),
            intArrayOf(2, 6),
            intArrayOf(1, 3),
            intArrayOf(2, 4)
        )
        
        var dp = IntArray(10) { 1 }
        
        for (step in 1 until n) {
            val newDp = IntArray(10)
            for (i in 0 until 10) {
                for (move in moves[i]) {
                    newDp[move] = (newDp[move] + dp[i]) % MOD
                }
            }
            dp = newDp
        }
        
        return dp.fold(0) { acc, count -> (acc + count) % MOD }
    }
}

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

Задача: 157. Read N Characters Given Read4
Сложность: easy

У вас есть файл, который можно читать только через API read4(buf4).
Реализуйте метод read(buf, n), который прочитает не более n символов и запишет их в buf.

Пример:

Input: file = "abc", n = 4 Output: 3
buf после вызова должен содержать "abc".

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

1⃣Создайте вспомогательный буфер buf4 размером 4 и переменные copiedChars = 0 и readChars = 4.

2⃣Пока copiedChars < n и readChars == 4, вызывайте read4(buf4).
Копируйте символы из buf4 в buf, пока не достигнете n.

3⃣Когда достигнут EOF или прочитано n символов, остановитесь и верните copiedChars — общее количество успешно прочитанных символов.

😎 Решение:

class Solution {
    fun read(buf: Array<Char>, n: Int): Int {
        var copiedChars = 0
        var readChars = 4
        val buf4 = Array(4) { ' ' } 

        while (copiedChars < n && readChars == 4) {
            readChars = read4(buf4)

            for (i in 0 until readChars) {
                if (copiedChars == n) {
                    return copiedChars
                }
                buf[copiedChars] = buf4[i]
                copiedChars++
            }
        }
        return copiedChars
    }

    private fun read4(buf4: Array<Char>): Int {
        return 0
    }
}

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

Задача: 118. Pascal's Triangle
Сложность: easy

Дано целое число numRows. Верните первые numRows строк треугольника Паскаля.

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

Пример:

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

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

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

2⃣Проверяем особый случай, когда число строк равно 0, так как в противном случае мы бы вернули [1].

3⃣Поскольку numRows всегда больше 0, мы можем инициализировать треугольник первой строкой [1] и продолжить заполнять строки следующим образом:

😎 Решение:

class Solution {
    fun generate(numRows: Int): List<List<Int>> {
        val triangle = mutableListOf<List<Int>>()

        for (rowNum in 0 until numRows) {
            val row = MutableList(rowNum + 1) { 0 }
            row[0] = 1
            row[row.lastIndex] = 1

            for (j in 1 until row.size - 1) {
                row[j] = triangle[rowNum - 1][j - 1] + triangle[rowNum - 1][j]
            }

            triangle.add(row)
        }

        return triangle
    }
}

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

Задача: 932. Beautiful Array
Сложность: medium

Массив nums длины n красив, если: nums является перестановкой целых чисел в диапазоне [1, n]. Для каждого 0 <= i < j < n не существует индекса k с i < k < j, где 2 * nums[k] == nums[i] + nums[j]. Задано целое число n, верните любой красивый массив nums длины n. Для заданного n будет хотя бы один правильный ответ.

Пример:

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

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

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

2⃣Если длина массива равна 1, вернуть массив [1].
Разделить n на четные и нечетные индексы и создать массивы для них.

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

😎 Решение:

class Solution {
    fun beautifulArray(n: Int): IntArray {
        return construct(n).toIntArray()
    }
    
    private fun construct(n: Int): List<Int> {
        if (n == 1) return listOf(1)
        val odd = construct((n + 1) / 2).map { 2 * it - 1 }
        val even = construct(n / 2).map { 2 * it }
        return odd + even
    }
}

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

Задача: 737. Sentence Similarity II
Сложность: medium

Мы можем представить предложение в виде массива слов, например, предложение "I am happy with leetcode" можно представить как arr = ["I", "am",happy", "with", "leetcode"].

Даны два предложения sentence1 и sentence2, каждое из которых представлено в виде массива строк, и массив пар строк similarPairs, где similarPairs[i] = [xi, yi] указывает, что два слова xi и yi похожи. Возвращается true, если предложения sentence1 и sentence2 похожи, или false, если они не похожи. Два предложения похожи, если: у них одинаковая длина (т.е, Заметьте, что слово всегда похоже само на себя, также обратите внимание, что отношение сходства является транзитивным. Например, если слова a и b похожи, а слова b и c похожи, то a и c похожи.

Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","good"],["fine","good"],["drama","acting"],["skills","talent"]]
Output: true

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

1⃣Проверить, одинаковой ли длины предложения sentence1 и sentence2. Если нет, вернуть false.

2⃣Построить граф схожести слов с использованием словаря.

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

😎 Решение:

fun areSentencesSimilar(sentence1: Array<String>, sentence2: Array<String>, similarPairs: List<List<String>>): Boolean {
    if (sentence1.size != sentence2.size) {
        return false
    }
    
    val graph = mutableMapOf<String, MutableList<String>>()
    for (pair in similarPairs) {
        val (x, y) = pair
        graph.computeIfAbsent(x) { mutableListOf() }.add(y)
        graph.computeIfAbsent(y) { mutableListOf() }.add(x)
    }
    
    fun dfs(word1: String, word2: String, visited: MutableSet<String>): Boolean {
        if (word1 == word2) {
            return true
        }
        visited.add(word1)
        for (neighbor in graph[word1].orEmpty()) {
            if (neighbor !in visited && dfs(neighbor, word2, visited)) {
                return true
            }
        }
        return false
    }
    
    for (i in sentence1.indices) {
        if (sentence1[i] != sentence2[i]) {
            if (!dfs(sentence1[i], sentence2[i], mutableSetOf())) {
                return false
            }
        }
    }
    
    return true
}

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

Задача: 838. Push Dominoes
Сложность: medium

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

В рамках этой задачи мы будем считать, что падающее домино не передаёт дополнительную силу падающему или уже упавшему домино.
Вам дано строковое представление начального состояния домино:
dominoes[i] = 'L', если i-е домино толкнули влево,
dominoes[i] = 'R', если i-е домино толкнули вправо, и
dominoes[i] = '.', если i-е домино не было толкнуто.
Верните строку, представляющую конечное состояние.

Пример:

Input: dominoes = ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."

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

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

2⃣Добавьте фиктивные домино 'L' в начале и 'R' в конце для упрощения логики.

3⃣Обработайте промежутки между соседними домино, обновляя их состояния согласно правилам.

😎 Решение:

class Solution {
    fun pushDominoes(dominoes: String): String {
        val N = dominoes.length
        val indexes = mutableListOf(-1)
        val symbols = mutableListOf('L')
        
        for (i in dominoes.indices) {
            if (dominoes[i] != '.') {
                indexes.add(i)
                symbols.add(dominoes[i])
            }
        }
        
        indexes.add(N)
        symbols.add('R')
        
        val ans = dominoes.toCharArray()
        for (idx in 0 until indexes.size - 1) {
            val i = indexes[idx]
            val j = indexes[idx + 1]
            val x = symbols[idx]
            val y = symbols[idx + 1]
            if (x == y) {
                for (k in i + 1 until j) {
                    ans[k] = x
                }
            } else if (x == 'R' && y == 'L') {
                for (k in i + 1 until j) {
                    if (k - i == j - k) {
                        ans[k] = '.'
                    } else if (k - i < j - k) {
                        ans[k] = 'R'
                    } else {
                        ans[k] = 'L'
                    }
                }
            }
        }
        
        return String(ans)
    }

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

Задача: 1673. Find the Most Competitive Subsequence
Сложность: medium

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

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

Мы определяем, что подпоследовательность a более конкурентоспособна, чем подпоследовательность b (одинаковой длины), если в первой позиции, где они различаются, подпоследовательность a имеет число меньше, чем соответствующее число в b. Например, [1,3,4] более конкурентоспособна, чем [1,3,5], потому что первая позиция, где они различаются, это последнее число, и 4 меньше, чем 5.

Пример:

Input: nums = [3,5,2,6], k = 2
Output: [2,6]
Explanation: Among the set of every possible subsequence: {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]}, [2,6] is the most competitive.

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

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

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

3⃣В конце получите первые k элементов из очереди и создайте результирующий массив.

😎 Решение:

class Solution {
    fun mostCompetitive(nums: IntArray, k: Int): IntArray {
        val queue = ArrayDeque<Int>()
        var additionalCount = nums.size - k
        
        for (num in nums) {
            while (queue.isNotEmpty() && queue.last() > num && additionalCount > 0) {
                queue.removeLast()
                additionalCount--
            }
            queue.addLast(num)
        }
        
        return queue.take(k).toIntArray()
    }
}

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

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

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