#medium
Задача: 259. 3Sum Smaller

Дан массив из n целых чисел nums и целое число target. Найдите количество троек индексов i, j, k, удовлетворяющих условию 0 <= i < j < k < n и nums[i] + nums[j] + nums[k] < target.

Пример:

Input: nums = [-2,0,1,3], target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2:
[-2,0,1]
[-2,0,3]

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

1️⃣Отсортируйте массив nums.

2️⃣Для каждого элемента nums[i] от 0 до n-3 найдите количество пар индексов j и k (где i < j < k), таких что nums[i] + nums[j] + nums[k] < target. Используйте функцию twoSumSmaller, которая ищет количество пар с суммой меньше заданного значения.

3️⃣В функции twoSumSmaller используйте бинарный поиск для поиска верхней границы индекса k и подсчета количества подходящих пар.

😎 Решение:

class Solution {
    fun threeSumSmaller(nums: IntArray, target: Int): Int {
        nums.sort()
        var sum = 0
        for (i in 0 until nums.size - 2) {
            sum += twoSumSmaller(nums, i + 1, target - nums[i])
        }
        return sum
    }

    private fun twoSumSmaller(nums: IntArray, startIndex: Int, target: Int): Int {
        var sum = 0
        for (i in startIndex until nums.size - 1) {
            val j = binarySearch(nums, i, target - nums[i])
            sum += j - i
        }
        return sum
    }

    private fun binarySearch(nums: IntArray, startIndex: Int, target: Int): Int {
        var left = startIndex
        var right = nums.size - 1
        while (left < right) {
            val mid = (left

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 260. Single Number III

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

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

Пример:

Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation:  [5, 3] is also a valid answer.

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

1️⃣Выполните XOR для всех элементов массива nums. Это даст результат, который является XOR двух уникальных чисел.

2️⃣Найдите бит, который отличается в этих двух числах, чтобы разделить все числа в массиве на две группы.

3️⃣Выполните XOR для каждой группы, чтобы найти два уникальных числа.

😎 Решение:

class Solution {
    fun singleNumber(nums: IntArray): IntArray {
        val xor = nums.reduce { acc, num -> acc xor num }
        val diff = xor and -xor
        val res = intArrayOf(0, 0)
        for (num in nums) {
            if (num and diff == 0) {
                res[0] = res[0] xor num
            } else {
                res[1] = res[1] xor num
            }
        }
        return res
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 261. Graph Valid Tree

У вас есть граф из n узлов, помеченных от 0 до n - 1. Вам даны целое число n и список рёбер, где edges[i] = [ai, bi] указывает на то, что существует неориентированное ребро между узлами ai и bi в графе.

Верните true, если рёбра данного графа образуют допустимое дерево, и false в противном случае.

Пример:

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true

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

1️⃣Проверьте, что количество рёбер равно n - 1. Если нет, верните false.

2️⃣Используйте итеративный обход в глубину (DFS) для проверки связности графа и отсутствия циклов. Создайте стек для хранения узлов для посещения и множество для отслеживания посещённых узлов. Начните с узла 0.

3️⃣Если все узлы посещены и циклы не обнаружены, верните true. В противном случае, верните false.

😎 Решение:

class Solution {
    fun validTree(n: Int, edges: Array<IntArray>): Boolean {
        if (edges.size != n - 1) {
            return false
        }
        
        val adjList = Array(n) { mutableListOf<Int>() }
        for (edge in edges) {
            adjList[edge[0]].add(edge[1])
            adjList[edge[1]].add(edge[0])
        }
        
        val parent = mutableMapOf(0 to -1)
        val queue = ArrayDeque<Int>()
        queue.add(0)
        
        while (queue.isNotEmpty()) {
            val node = queue.removeFirst()
            for (neighbor in adjList[node]) {
                if (neighbor == parent[node]) {
                    continue
                }
                if (neighbor in parent) {
                    return false
                }
                parent[neighbor] = node
                queue.add(neighbor)
            }
        }
        
        return parent.size == n
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 263. Ugly Number

Уродливое число — это положительное целое число, простые множители которого ограничены числами 2, 3 и 5.

Дано целое число n, верните true, если n является уродливым числом.

Пример:

Input: n = 6
Output: true
Explanation: 6 = 2 × 3

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

1️⃣Если данное целое число n неположительное, верните false, так как неположительное число не может быть уродливым.

2️⃣Определите функцию keepDividingWhenDivisible, которая принимает два аргумента: делимое и делитель. Эта функция будет делить делимое на делитель до тех пор, пока оно делится без остатка. Функция возвращает измененное делимое. Последовательно примените эту функцию к n с делителями 2, 3 и 5.

3️⃣Если после всех делений n равно 1, верните true, иначе верните false.

😎 Решение:

class Solution {
    fun isUgly(n: Int): Boolean {
        if (n <= 0) return false
        var n = n
        for (factor in listOf(2, 3, 5)) {
            n = keepDividingWhenDivisible(n, factor)
        }
        return n == 1
    }

    private fun keepDividingWhenDivisible(dividend: Int, divisor: Int): Int {
        var dividend = dividend
        while (dividend % divisor == 0) {
            dividend /= divisor
        }
        return dividend
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 240. Search a 2D Matrix II

Напишите эффективный алгоритм, который ищет значение target в матрице целых чисел размером m на n. У этой матрицы есть следующие свойства:

Целые числа в каждой строке отсортированы по возрастанию слева направо.
Целые числа в каждом столбце отсортированы по возрастанию сверху вниз.

Пример:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true

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

1️⃣Проверка матрицы: Перед началом поиска убедитесь, что матрица не пуста и не содержит null.

2️⃣Итерация по диагоналям: Итерируйте по диагоналям матрицы, используя инвариант отсортированности срезов строк и столбцов, начиная с текущей позиции (строка, столбец). Для каждого такого среза используйте бинарный поиск для нахождения целевого значения.

3️⃣Бинарный поиск и завершение: Продолжайте бинарный поиск до тех пор, пока не исчерпаете все диагонали (в этом случае возвращается False) или пока не найдете целевое значение (в этом случае возвращается True). Функция бинарного поиска должна уметь работать как с рядами, так и с колонками матрицы.

😎 Решение:

class Solution {
    private fun binarySearch(matrix: Array<IntArray>, target: Int, start: Int, vertical: Boolean): Boolean {
        var lo = start
        var hi = if (vertical) matrix[0].size - 1 else matrix.size - 1

        while (hi >= lo) {
            val mid = (lo + hi) / 2
            if (vertical) {
                if (matrix[start][mid] < target) {
                    lo = mid + 1
                } else if (matrix[start][mid] > target) {
                    hi = mid - 1
                } else {
                    return true
                }
            } else {
                if (matrix[mid][start] < target) {
                    lo = mid + 1
                } else if (matrix[mid][start] > target) {
                    hi = mid - 1
                } else {
                    return true
                }
            }
        }
        return false
    }

    fun searchMatrix(matrix: Array<IntArray>, target: Int): Boolean {
        if (matrix.isEmpty() || matrix[0].isEmpty()) return false

        val shorterDim = minOf(matrix.size, matrix[0].size)
        for (i in 0 until shorterDim) {
            if (binarySearch(matrix, target, i, true) || binarySearch(matrix, target, i, false)) {
                return true
            }
        }
        return false
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 242. Valid Anagram

Даны две строки s и t, верните true, если t является анаграммой s, и false в противном случае.

Анаграмма — это слово или фраза, сформированная путём перестановки букв другого слова или фразы, обычно используя все исходные буквы ровно один раз.

Пример:

Input: s = "anagram", t = "nagaram"
Output: true

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

1️⃣Создайте массив размером 26 для подсчета частот каждой буквы (поскольку s и t содержат только буквы от 'a' до 'z').

2️⃣Пройдитесь по строке s, увеличивая счетчик соответствующей буквы. Затем пройдитесь по строке t, уменьшая счетчик для каждой буквы.

3️⃣Проверьте, не опустился ли счетчик ниже нуля во время обхода строки t. Если это произошло, значит в t есть лишняя буква, которой нет в s, и следует вернуть false. Если после проверки всех букв все счетчики равны нулю, возвращайте true, указывая на то, что t является анаграммой s.

😎 Решение:

fun isAnagram(s: String, t: String): Boolean {
    if (s.length != t.length) return false
    val table = IntArray(26)
    s.forEach { table[it - 'a']++ }
    t.forEach { 
        table[it - 'a']--
        if (table[it - 'a'] < 0) return false
    }
    return true
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 243. Shortest Word Distance

Дан массив строк wordsDict и две разные строки, которые уже существуют в массиве: word1 и word2. Верните кратчайшее расстояние между этими двумя словами в списке.

Пример:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", word2 = "practice"
Output: 3

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

1️⃣Начните с перебора всего массива для поиска первого слова. Каждый раз, когда вы находите встречу первого слова, запомните его позицию.

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

3️⃣Сохраняйте минимальное найденное расстояние между двумя словами и возвращайте его в качестве результата.

😎 Решение:

class Solution {
    fun shortestDistance(words: Array<String>, word1: String, word2: String): Int {
        var minDistance = words.size
        for (i in words.indices) {
            if (words[i] == word1) {
                for (j in words.indices) {
                    if (words[j] == word2) {
                        minDistance = kotlin.math.min(minDistance, kotlin.math.abs(i - j))
                    }
                }
            }
        }
        return minDistance
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 244. Shortest Word Distance II

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

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

WordDistance(String[] wordsDict) инициализирует объект с массивом строк wordsDict.
int shortest(String word1, String word2) возвращает наименьшее расстояние между word1 и word2 в массиве wordsDict.

Пример:

Input
["WordDistance", "shortest", "shortest"]
[[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]]
Output
[null, 3, 1]
Explanation
WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]);
wordDistance.shortest("coding", "practice"); // return 3
wordDistance.shortest("makes", "coding");    // return 1

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

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

2️⃣Для данной пары слов получите список индексов (вхождений в исходный массив слов). Назовём эти два массива loc1 и loc2. Инициализируйте две переменные-указателя l1 = 0 и l2 = 0.

3️⃣Для данных l1 и l2 обновите (если возможно) минимальную разницу (расстояние) до текущего момента, т.е. dist = min(dist, abs(loc1[l1] - loc2[l2])). Затем проверьте, если loc1[l1] < loc2[l2], и если это так, переместите l1 на один шаг вперёд, т.е. l1 = l1 + 1. В противном случае, переместите l2 на один шаг вперёд, т.е. l2 = l2 + 1. Продолжайте это делать, пока все элементы в меньшем из двух массивов позиций не будут обработаны. Верните глобальное минимальное расстояние между словами.

😎 Решение:

class WordDistance(words: Array<String>) {

    private val locations: MutableMap<String, MutableList<Int>> = HashMap()

    init {
        for (i in words.indices) {
            if (!locations.containsKey(words[i])) {
                locations[words[i]] = ArrayList()
            }
            locations[words[i]]!!.add(i)
        }
    }

    fun shortest(word1: String, word2: String): Int {
        val loc1 = locations[word1]!!
        val loc2 = locations[word2]!!
        var l1 = 0
        var l2 = 0
        var minDiff = Int.MAX_VALUE

        while (l1 < loc1.size && l2 < loc2.size) {
            minDiff = Math.min(minDiff, Math.abs(loc1[l1] - loc2[l2]))
            if (loc1[l1] < loc2[l2]) {
                l1++
            } else {
                l2++
            }
        }
        return minDiff
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 245. Shortest Word Distance II

Дан массив строк wordsDict и две строки word1 и word2, которые уже существуют в массиве. Верните наименьшее расстояние между вхождениями этих двух слов в списке.

Обратите внимание, что word1 и word2 могут быть одинаковыми. Гарантируется, что они представляют собой два отдельных слова в списке.

Пример:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
Output: 1

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

1️⃣Переберите список wordsDict и сохраните индексы слова word1 в список indices1 и индексы слова word2 в список indices2. Инициализируйте переменную shortestDistance = INT_MAX.

2️⃣Переберите индексы в списке indices1 и для каждого индекса найдите верхнюю границу в списке indices2, используя бинарный поиск, и сохраните этот индекс в переменную x. Рассмотрите индексы indices2[x] и indices2[x - 1], обновляя shortestDistance, если индексы не совпадают.

3️⃣Верните значение переменной shortestDistance.

😎 Решение:

class Solution {
    fun shortestWordDistance(wordsDict: Array<String>, word1: String, word2: String): Int {
        val indices1 = mutableListOf<Int>()
        val indices2 = mutableListOf<Int>()
        for (i in wordsDict.indices) {
            if (wordsDict[i] == word1) {
                indices1.add(i)
            }
            if (wordsDict[i] == word2) {
                indices2.add(i)
            }
        }

        var shortestDistance = Int.MAX_VALUE
        for (index in indices1) {
            val x = indices2.binarySearch(index).let { if (it < 0) -it-1 else it }
            if (x < indices2.size) {
                shortestDistance = minOf(shortestDistance, indices2[x] - index)
            }
            if (x > 0 && indices2[x - 1] != index) {
                shortestDistance = minOf(shortestDistance, index - indices2[x - 1])
            }
        }
        return shortestDistance
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 246. Strobogrammatic Number

Дана строка num, представляющая собой целое число. Верните true, если num является стробограмматическим числом.

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

Пример:

Input: num = "69"
Output: true

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

1️⃣Создайте новую строку, перебирая оригинальную строку num в обратном порядке. Для каждого символа проверьте, является ли он допустимым для поворота (0, 1, 6, 8, 9). Если символ недопустим (2, 3, 4, 5, 7), немедленно верните false.

2️⃣Для каждого допустимого символа добавьте его соответствующее значение после поворота (0 ⟶ 0, 1 ⟶ 1, 6 ⟶ 9, 8 ⟶ 8, 9 ⟶ 6) в новую строку.

3️⃣Сравните полученную строку с исходной строкой num. Если они равны, верните true, в противном случае верните false.

😎 Решение:

class Solution {
    fun isStrobogrammatic(num: String): Boolean {
        val rotated = StringBuilder()
        for (i in num.length - 1 downTo 0) {
            when (num[i]) {
                '0', '1', '8' -> rotated.append(num[i])
                '6' -> rotated.append('9')
                '9' -> rotated.append('6')
                else -> return false
            }
        }
        return num == rotated.toString()
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 247. Strobogrammatic Number II

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

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

Пример:

Input: n = 2
Output: ["11","69","88","96"]

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

1️⃣Инициализируйте структуру данных reversiblePairs, которая содержит все пары обратимых цифр. Вызовите и верните результат рекурсивной функции generateStroboNumbers(n, finalLength), где первый аргумент указывает, что текущий вызов создаст все стробограмматические числа длиной n, а второй аргумент указывает длину конечных стробограмматических чисел, которые мы будем генерировать, и будет использоваться для проверки возможности добавления '0' в начало и конец числа.

2️⃣Создайте функцию generateStroboNumbers(n, finalLength), которая вернет все стробограмматические числа длиной n:
Проверьте базовые случаи: если n == 0, верните массив с пустой строкой [""]; если n == 1, верните ["0", "1", "8"].
Вызовите generateStroboNumbers(n - 2, finalLength), чтобы получить все стробограмматические числа длиной (n-2), и сохраните их в subAns.
Инициализируйте пустой массив currStroboNums для хранения стробограмматических чисел длиной n.

3️⃣Для каждого числа в subAns добавьте все reversiblePairs в начало и конец, за исключением случая, когда текущая пара '00' и n == finalLength (потому что нельзя добавить '0' в начало числа), и добавьте это новое число в currStroboNums. В конце функции верните все стробограмматические числа, т.е. currStroboNums.

😎 Решение:

class Solution {
    private val reversiblePairs = listOf(
        listOf('0', '0'), listOf('1', '1'), 
        listOf('6', '9'), listOf('8', '8'), listOf('9', '6')
    )
    
    private fun generateStroboNumbers(n: Int, finalLength: Int): List<String> {
        if (n == 0) {
            return listOf("")
        }
        
        if (n == 1) {
            return listOf("0", "1", "8")
        }
        
        val prevStroboNums = generateStroboNumbers(n - 2, finalLength)
        val currStroboNums = mutableListOf<String>()
        
        for (prevStroboNum in prevStroboNums) {
            for (pair in reversiblePairs) {
                if (pair[0] != '0' || n != finalLength) {
                    currStroboNums.add("${pair[0]}$prevStroboNum${pair[1]}")
                }
            }
        }
        
        return currStroboNums
    }
    
    fun findStrobogrammatic(n: Int): List<String> {
        return generateStroboNumbers(n, n)
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 249. Group Shifted Strings

Выполните следующие операции сдвига на строке:

Правый сдвиг: замените каждую букву следующей буквой английского алфавита, где 'z' заменяется на 'a'. Например, "abc" можно сдвинуть вправо на "bcd" или "xyz" можно сдвинуть вправо на "yza".
Левый сдвиг: замените каждую букву предыдущей буквой английского алфавита, где 'a' заменяется на 'z'. Например, "bcd" можно сдвинуть влево на "abc" или "yza" можно сдвинуть влево на "xyz".
Мы можем продолжать сдвигать строку в обоих направлениях, чтобы сформировать бесконечную последовательность сдвигов.

Например, сдвиньте "abc", чтобы сформировать последовательность: ... <-> "abc" <-> "bcd" <-> ... <-> "xyz" <-> "yza" <-> .... <-> "zab" <-> "abc" <-> ...
Вам дан массив строк strings, сгруппируйте все strings[i], которые принадлежат одной и той же последовательности сдвигов. Ответ можно вернуть в любом порядке.

Пример:

Input: strings = ["abc","bcd","acef","xyz","az","ba","a","z"]

Output: [["acef"],["a","z"],["abc","bcd","xyz"],["az","ba"]]

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

1️⃣Переберите строки, и для каждой строки найдите ее хэш-значение, сдвигая все символы так, чтобы строка начиналась с 'a'. Значение сдвига равно позиции первого символа строки, и каждый символ сдвигается на это значение с учетом модуля 26.

2️⃣Сопоставьте оригинальную строку с найденным хэш-значением в карте mapHashToList, добавляя оригинальную строку в список, соответствующий ее хэш-значению.

3️⃣Переберите mapHashToList и сохраните список для каждого ключа в карте в массив ответа groups.

😎 Решение:

class Solution {
    private fun shiftLetter(letter: Char, shift: Int): Char {
        return ((letter - 'a' - shift + 26) % 26 + 'a'.toInt()).toChar()
    }
    
    private fun getHash(s: String): String {
        val shift = s[0] - 'a'
        val hashKey = StringBuilder()
        
        for (letter in s) {
            hashKey.append(shiftLetter(letter, shift))
        }
        
        return hashKey.toString()
    }
    
    fun groupStrings(strings: List<String>): List<List<String>> {
        val mapHashToList = mutableMapOf<String, MutableList<String>>()
        
        for (str in strings) {
            val hashKey = getHash(str)
            mapHashToList.computeIfAbsent(hashKey) { mutableListOf() }.add(str)
        }
        
        return mapHashToList.values.toList()
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 250. Count Univalue Subtrees

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

Поддерево с одинаковыми значениями означает, что все узлы поддерева имеют одно и то же значение.

Пример:

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

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

1️⃣Создайте целочисленную переменную count для подсчета количества поддеревьев с одинаковыми значениями. Инициализируйте её значением 0.

2️⃣Выполните обход в глубину (DFS) для данного бинарного дерева. Выполните dfs(root), где dfs — это рекурсивный метод, который принимает узел TreeNode в качестве параметра, от которого начинается обход. Метод возвращает логическое значение, указывающее, является ли поддерево, укоренённое в этом узле, поддеревом с одинаковыми значениями. Выполните следующие действия в этом методе:
Если узел равен null, верните true.
Рекурсивно проверьте, образует ли левый потомок поддерево с одинаковыми значениями. Выполните isLeftUniValue = dfs(node.left).
Рекурсивно проверьте, образует ли правый потомок поддерево с одинаковыми значениями. Выполните isRightUniValue = dfs(node.right).
Если оба потомка образуют поддеревья с одинаковыми значениями, т.е. isLeftUniValue && isRightUniValue равно true, сравните значения потомков узла со значением самого узла. Если левый потомок существует и node.left.val != node.val, верните false, так как значения не совпадают и мы не имеем поддерева с одинаковыми значениями. Аналогично, если правый потомок существует и node.right.val != node.val, верните false. В противном случае, увеличьте count на 1 и верните true.
В противном случае, одно или оба поддерева потомков не образуют поддеревья с одинаковыми значениями, поэтому дерево, укоренённое в node, также не может быть таким поддеревом. Верните false.

3️⃣Верните count.

😎 Решение:

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

class Solution {
    private var count = 0

    private fun dfs(node: TreeNode?): Boolean {
        if (node == null) {
            return true
        }

        val isLeftUniValue = dfs(node.left)
        val isRightUniValue = dfs(node.right)

        if (isLeftUniValue && isRightUniValue) {
            if (node.left != null && node.left!!.`val` != node.`val`) {
                return false
            }
            if (node.right != null && node.right!!.`val` != node.`val`) {
                return false
            }
            count++
            return true
        }
        return false
    }

    fun countUnivalSubtrees(root: TreeNode?): Int {
        dfs(root)
        return count
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 267. Palindrome Permutation II

Дана строка s, верните все палиндромные перестановки (без дубликатов) этой строки.

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

Пример:

Input: s = "aabb"
Output: ["abba","baab"]

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

1️⃣Проверка на возможность палиндромной перестановки:
Создаем хеш-таблицу, которая хранит количество вхождений каждого символа строки s.
Если количество символов с нечетным количеством вхождений превышает 1, то палиндромная перестановка
невозможна, и мы возвращаем пустой список.

2️⃣Генерация первой половины палиндромной строки:
Создаем строку st, которая содержит все символы строки s с количеством вхождений, уменьшенным до половины от их первоначального количества.
Если длина строки s нечетная, сохраняем символ, который встречается нечетное количество раз, отдельно.

3️⃣Генерация всех перестановок первой половины и создание палиндромов:
Генерируем все перестановки строки st.
Для каждой перестановки добавляем её обратную строку к самой себе, создавая тем самым полную палиндромную строку.
Если длина строки s нечетная, добавляем сохраненный символ в середину каждого палиндрома.
Чтобы избежать дубликатов, проверяем, равны ли элементы перед свапом. Если да, то пропускаем данную перестановку.

😎 Решение:

using System;
using System.Collections.Generic;
using System.Text;

public class Solution {
    private HashSet<string> set;

    public Solution() {
        set = new HashSet<string>();
    }

    public IList<string> GeneratePalindromes(string s) {
        int[] map = new int[128];
        char[] st = new char[s.Length / 2];
        if (!CanPermutePalindrome(s, map)) {
            return new List<string>();
        }

        char ch = '\0';
        int k = 0;
        for (int i = 0; i < map.Length; i++) {
            if (map[i] % 2 == 1) {
                ch = (char)i;
            }
            for (int j = 0; j < map[i] / 2; j++) {
                st[k++] = (char)i;
            }
        }
        Permute(st, 0, ch);
        return new List<string>(set);
    }

    private bool CanPermutePalindrome(string s, int[] map) {
        int count = 0;
        foreach (char c in s) {
            int index = (int)c;
            map[index]++;
            if (map[index] % 2 == 0) {
                count--;
            } else {
                count++;
            }
        }
        return count <= 1;
    }

    private void Swap(ref char[] s, int i, int j) {
        char temp = s[i];
        s[i] = s[j];
        s[j] = temp;
    }

    private void Permute(char[] s, int l, char ch) {
        if (l == s.Length) {
            StringBuilder sb = new StringBuilder();
            sb.Append(s);
            if (ch != '\0') {
                sb.Append(ch);
            }
            Array.Reverse(s);
            sb.Append(s);
            set.Add(sb.ToString());
            Array.Reverse(s);
        } else {
            for (int i = l; i < s.Length; i++) {
                if (s[l] != s[i] || l == i) {
                    Swap(ref s, l, i);
                    Permute(s, l + 1, ch);
                    Swap(ref s, l, i);
                }
            }
        }
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 267. Palindrome Permutation II

Дана строка s, верните все палиндромные перестановки (без дубликатов) этой строки.

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

Пример:

Input: s = "aabb"
Output: ["abba","baab"]

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

1️⃣Проверка на возможность палиндромной перестановки:
Создаем хеш-таблицу для хранения количества вхождений каждого символа строки s.
Если количество символов с нечетным количеством вхождений превышает 1, возвращаем пустой список, так как палиндромная перестановка невозможна.

2️⃣Генерация палиндромных перестановок:
Создаем строку st, содержащую все символы строки s, но с количеством вхождений, уменьшенным до половины от их первоначального количества.
Если строка s имеет нечетную длину, один из символов должен встречаться нечетное количество раз. Этот символ ch сохраняем отдельно.

3️⃣Генерация всех перестановок строки st:
Для каждой перестановки строки st добавляем ее обратную строку, чтобы создать полную палиндромную строку.
Если строка s имеет нечетную длину, добавляем символ ch в середину каждой палиндромной перестановки.

4️⃣Исключение дубликатов:
Чтобы избежать создания дубликатов, перед выполнением свапа проверяем, равны ли элементы, которые будут поменяны местами. Если да, пропускаем эту перестановку.

😎 Решение:

class Solution {
    private val set = HashSet<String>()

    fun generatePalindromes(s: String): List<String> {
        val map = IntArray(128)
        val st = CharArray(s.length / 2)
        if (!canPermutePalindrome(s, map)) {
            return emptyList()
        }

        var ch = '\u0000'
        var k = 0
        for (i in map.indices) {
            if (map[i] % 2 == 1) {
                ch = i.toChar()
            }
            repeat(map[i] / 2) {
                st[k++] = i.toChar()
            }
        }
        permute(st, 0, ch)
        return set.toList()
    }

    private fun canPermutePalindrome(s: String, map: IntArray): Boolean {
        var count = 0
        for (char in s) {
            val index = char.toInt()
            map[index]++
            if (map[index] % 2 == 0) {
                count--
            } else {
                count++
            }
        }
        return count <= 1
    }

    private fun swap(s: CharArray, i: Int, j: Int) {
        val temp = s[i]
        s[i] = s[j]
        s[j] = temp
    }

    private fun permute(s: CharArray, l: Int, ch: Char) {
        if (l == s.size) {
            val sb = StringBuilder()
            sb.append(s)
            if (ch != '\u0000') {
                sb.append(ch)
            }
            sb.append(s.reversedArray())
            set.add(sb.toString())
        } else {
            for (i in l until s.size) {
                if (s[l] != s[i] || l == i) {
                    swap(s, l, i)
                    permute(s, l + 1, ch)
                    swap(s, l, i)
                }
            }
        }
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 251. Flatten 2D Vector

Разработайте итератор для разворачивания двумерного вектора. Он должен поддерживать операции next и hasNext.

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

Vector2D(int[][] vec) инициализирует объект двумерным вектором vec.
next() возвращает следующий элемент из двумерного вектора и перемещает указатель на один шаг вперед. Вы можете предположить, что все вызовы next допустимы.
hasNext() возвращает true, если в векторе еще остались элементы, и false в противном случае.

Пример:

Input
["Vector2D", "next", "next", "next", "hasNext", "hasNext", "next", "hasNext"]
[[[[1, 2], [3], [4]]], [], [], [], [], [], [], []]
Output
[null, 1, 2, 3, true, true, 4, false]

Explanation
Vector2D vector2D = new Vector2D([[1, 2], [3], [4]]);
vector2D.next();    // return 1
vector2D.next();    // return 2
vector2D.next();    // return 3
vector2D.hasNext(); // return True
vector2D.hasNext(); // return True
vector2D.next();    // return 4
vector2D.hasNext(); // return False

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

1️⃣Инициализация: Установите указатель position так, чтобы он указывал на следующий элемент массива, который должен быть возвращен методом next(). Это обеспечивает, что position всегда готов к получению следующего действительного элемента.

2️⃣Проверка доступности: Реализуйте метод hasNext(), который просто проверяет, находится ли индекс position в пределах допустимых индексов массива nums. Этот метод вернет true, если position указывает на действительный индекс, и false в противном случае.

3️⃣Получение следующего элемента: Метод next() возвращает элемент в текущей позиции position и продвигает указатель position на следующий индекс. Эта операция обеспечивает, что после вызова next(), position обновляется и указывает на следующий элемент, готовый к следующему вызову next().

😎 Решение:

class Vector2D(v: List<List<Int>>) {
    private val nums: List<Int> = v.flatten()
    private var position = -1

    fun next(): Int {
        position += 1
        return nums[position]
    }

    fun hasNext(): Boolean {
        return position + 1 < nums.size
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 268. Missing Number

Дан массив nums, содержащий n различных чисел в диапазоне [0, n]. Верните единственное число в этом диапазоне, которого нет в массиве.

Пример:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

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

1️⃣Сначала отсортируйте массив nums.

2️⃣Проверьте особые случаи: убедитесь, что число 0 находится в начале массива, а число n — в конце.

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

😎 Решение:

class Solution {
    fun missingNumber(nums: IntArray): Int {
        nums.sort()
        if (nums.last() != nums.size) {
            return nums.size
        } else if (nums.first() != 0) {
            return 0
        }
        for (i in 1 until nums.size) {
            val expectedNum = nums[i - 1] + 1
            if (nums[i] != expectedNum) {
                return expectedNum
            }
        }
        return -1
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 269. Alien Dictionary

Есть новый инопланетный язык, который использует английский алфавит. Однако порядок букв в нем неизвестен.

Вам дан список строк words из словаря инопланетного языка. Утверждается, что строки в words отсортированы лексикографически по правилам этого нового языка.

Если это утверждение неверно и данное расположение строк в words не может соответствовать никакому порядку букв, верните "".

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

Пример:

Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"

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

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

2️⃣Подсчет числа входящих ребер:
Подсчитать количество входящих ребер (in-degree) для каждой буквы.
Построить исходящий список смежности и одновременно считать входящие ребра для каждой буквы.

3️⃣Обход в ширину (BFS):
Инициализировать очередь буквами с нулевым in-degree.
Выполнять BFS, добавляя буквы в результат, когда их in-degree становится нулевым.
Продолжать до тех пор, пока очередь не станет пустой.
Проверить наличие циклов и вернуть результат.

😎 Решение:

import java.util.*

class Solution {
    fun alienOrder(words: Array<String>): String {
        val adjList = mutableMapOf<Char, MutableSet<Char>>()
        val inDegree = mutableMapOf<Char, Int>()

        for (word in words) {
            for (char in word) {
                inDegree[char] = 0
            }
        }

        for ((firstWord, secondWord) in words.zip(words.drop(1))) {
            for ((c, d) in firstWord.zip(secondWord)) {
                if (c != d) {
                    if (d !in adjList.getOrDefault(c, mutableSetOf())) {
                        adjList.getOrPut(c) { mutableSetOf() }.add(d)
                        inDegree[d] = inDegree.getOrDefault(d, 0) + 1
                    }
                    break
                }
            }
            if (secondWord.length < firstWord.length && firstWord.startsWith(secondWord)) {
                return ""
            }
        }

        val output = mutableListOf<Char>()
        val queue: Queue<Char> = LinkedList()

        for ((char, degree) in inDegree) {
            if (degree == 0) {
                queue.add(char)
            }
        }

        while (queue.isNotEmpty()) {
            val c = queue.poll()
            output.add(c)
            for (d in adjList.getOrDefault(c, emptySet())) {
                inDegree[d] = inDegree[d]!! - 1
                if (inDegree[d] == 0) {
                    queue.add(d)
                }
            }
        }

        if (output.size < inDegree.size) {
            return ""
        }

        return output.joinToString("")
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 270. Closest Binary Search Tree Value

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

Пример:

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

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

1️⃣Построить массив с помощью inorder обхода:
Выполнить inorder обход дерева и собрать элементы в отсортированный массив.

2️⃣Найти ближайший элемент:
Пройти по массиву и определить элемент, наиболее близкий к целевому значению.

3️⃣Выбрать наименьший из ближайших элементов:
Если несколько элементов одинаково близки к целевому значению, выбрать наименьший из них.

😎 Решение:

class Solution {
    fun closestValue(root: TreeNode?, target: Double): Int {
        var closest = root?.`val` ?: 0
        var node = root
        while (node != null) {
            if (Math.abs(node.`val` - target) < Math.abs(closest - target)) {
                closest = node.`val`
            } else if (Math.abs(node.`val` - target) == Math.abs(closest - target)) {
                closest = minOf(node.`val`, closest)
            }
            node = if (target < node.`val`) node.left else node.right
        }
        return closest
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 272. Closest Binary Search Tree Value II

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 214. Shortest Palindrome

Дана строка s. Вы можете преобразовать s в палиндром, добавив символы в начало строки.

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

Пример:

Input: s = "aacecaaa"
Output: "aaacecaaa"

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

1️⃣ Создание обратной строки:
Создайте обратную строку rev от исходной строки s, чтобы использовать её для сравнения.

2️⃣ Итерация для поиска наибольшего палиндрома:
Перемещайтесь по индексу i от 0 до n - 1.
Для каждой итерации проверяйте, является ли подстрока s от начала до n - i равной подстроке rev от i до конца строки.
Если условие выполняется, это означает, что подстрока s от начала до n - i является палиндромом.
Возвращайте строку, состоящую из обратной подстроки rev от начала до i + исходная строка s.

3️⃣ Возврат результата:
Если не найдено совпадений, возвращайте пустую строку (хотя этот случай практически невозможен для непустой строки s).

😎 Решение:

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 ""
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых