Задача: 650. 2 Keys Keyboard
Сложность: medium

На экране блокнота есть только один символ 'A'. Для каждого шага можно выполнить одну из двух операций над этим блокнотом: Copy All: скопировать все символы, присутствующие на экране (частичное копирование не допускается). Paste: Вы можете вставить символы, которые были скопированы в прошлый раз. Учитывая целое число n, верните минимальное количество операций, чтобы символ 'A' появился на экране ровно n раз.

Пример:

Input: n = 3
Output: 3

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

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

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

3⃣Возвращайте значение из таблицы динамического программирования для n.

😎 Решение:

fun minSteps(n: Int): Int {
    if (n == 1) return 0
    val dp = IntArray(n + 1)
    for (i in 2..n) {
        dp[i] = i
        for (j in 1..(i / 2)) {
            if (i % j == 0) {
                dp[i] = kotlin.math.min(dp[i], dp[j] + i / j)
            }
        }
    }
    return dp[n]
}

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

Задача: 954. Array of Doubled Pairs
Сложность: medium

Если задан целочисленный массив четной длины arr, верните true, если можно переупорядочить arr так, чтобы arr[2 * i + 1] = 2 * arr[2 * i] для каждого 0 <= i < len(arr) / 2, или false в противном случае.

Пример:

Input: arr = [3,1,3,6]
Output: false

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

1⃣Подсчитать частоту каждого элемента в массиве.
Отсортировать массив по абсолютным значениям элементов.

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

3⃣Если для каждого элемента можно найти пару, вернуть true, иначе вернуть false.

😎 Решение:

class Solution {
    fun canReorderDoubled(arr: IntArray): Boolean {
        val count = mutableMapOf<Int, Int>()
        for (num in arr) {
            count[num] = count.getOrDefault(num, 0) + 1
        }
        arr.sortBy { Math.abs(it) }
        for (num in arr) {
            if (count[num] == 0) continue
            if (count.getOrDefault(2 * num, 0) == 0) return false
            count[num] = count[num]!! - 1
            count[2 * num] = count[2 * num]!! - 1
        }
        return true
    }
}

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

Задача: 785. Is Graph Bipartite?
Сложность: medium

Есть неориентированный граф с n узлами, где каждый узел пронумерован от 0 до n - 1. Вам дан двумерный массив graph, где graph[u] — это массив узлов, смежных с узлом u. Более формально, для каждого v в graph[u] существует неориентированное ребро между узлом u и узлом v. Граф обладает следующими свойствами:

Нет петель (graph[u] не содержит u).
Нет параллельных ребер (graph[u] не содержит дублирующихся значений).
Если v есть в graph[u], то u есть в graph[v] (граф неориентированный).
Граф может быть несвязным, то есть могут существовать два узла u и v, между которыми нет пути.
Граф является двудольным, если узлы можно разделить на два независимых множества A и B так, что каждое ребро в графе соединяет узел из множества A с узлом из множества B.

Верните true, если и только если граф является двудольным.

Пример:

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

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

1⃣Мы будем хранить массив (или hashmap) для поиска цвета каждого узла: color[node]. Цвета могут быть 0, 1 или неокрашенные (-1 или null).

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

3⃣Для выполнения поиска в глубину мы используем стек. Для каждого неокрашенного соседа в graph[node] мы будем его окрашивать и добавлять в наш стек, который действует как своего рода "список дел" для узлов, которые нужно посетить дальше. Наш внешний цикл для start... гарантирует, что мы окрасим каждый узел.

😎 Решение:

class Solution {
    fun isBipartite(graph: Array<IntArray>): Boolean {
        val color = mutableMapOf<Int, Int>()
        for (node in graph.indices) {
            if (node !in color) {
                val stack = mutableListOf(node)
                color[node] = 0
                while (stack.isNotEmpty()) {
                    val node = stack.removeAt(stack.size - 1)
                    for (nei in graph[node]) {
                        if (nei !in color) {
                            stack.add(nei)
                            color[nei] = color[node]!! xor 1
                        } else if (color[nei] == color[node]) {
                            return false
                        }
                    }
                }
            }
        }
        return true
    }
}

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

Задача: 67. Add Binary
Сложность: easy

Даны две двоичные строки a и b. Верните их сумму в виде двоичной строки.

Пример:

Input: a = "11", b = "1"
Output: "100"

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

1⃣Начните с переноса carry = 0. Если в числе a наименьший бит равен 1, добавьте 1 к carry. То же самое относится к числу b: если в числе b наименьший бит равен 1, добавьте 1 к carry. В этот момент carry для наименьшего бита может быть равен 0 (00), 1 (01) или 2 (10).

2⃣Теперь добавьте наименьший бит carry к ответу и перенесите старший бит carry на следующий порядковый бит.

3⃣Повторяйте те же шаги снова и снова, пока не будут использованы все биты в a и b. Если остаётся ненулевой carry, добавьте его. Теперь переверните строку ответа, и задача выполнена.

😎 Решение:

class Solution {
    fun addBinary(a: String, b: String): String {
        val n = maxOf(a.length, b.length)
        val aPadded = a.padStart(n, '0')
        val bPadded = b.padStart(n, '0')

        var carry = 0
        val answer = StringBuilder()
        for (i in n - 1 downTo 0) {
            if (aPadded[i] == '1') {
                carry += 1
            }
            if (bPadded[i] == '1') {
                carry += 1
            }

            answer.append(if (carry % 2 == 1) "1" else "0")
            carry /= 2
        }

        if (carry == 1) {
            answer.append("1")
        }
        return answer.reverse().toString()
    }
}

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

Задача: 655. Print Binary Tree
Сложность: medium

Учитывая корень двоичного дерева, постройте строковую матрицу res с индексом 0 размером m x n, которая представляет собой форматированную раскладку дерева. Форматированная матрица должна быть построена по следующим правилам: высота дерева равна height, количество строк m должно быть равно height + 1. Количество столбцов n должно быть равно 2height+1 - 1. Поместите корневой узел в середину верхней строки (более формально, в позицию res[0][(n-1)/2]).
Для каждого узла, который был помещен в матрицу в позицию res[r][c], поместите его левого ребенка в res[r+1][c-2height-r-1], а правого - в res[r+1][c+2height-r-1]. Продолжайте этот процесс, пока не будут размещены все узлы дерева. Любые пустые ячейки должны содержать пустую строку "". Верните построенную матрицу res.

Пример:

Input: root = [1,2]
Output: 
[["","1",""],
 ["2","",""]]

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

1⃣Найдите высоту дерева и определите размер матрицы (m x n).

2⃣Рекурсивно разместите узлы в матрице, начиная с корневого узла.

3⃣Верните заполненную матрицу.

😎 Решение:

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

fun findHeight(root: TreeNode?): Int {
    if (root == null) return -1
    return 1 + maxOf(findHeight(root.left), findHeight(root.right))
}

fun fill(res: Array<Array<String>>, root: TreeNode?, r: Int, c: Int, height: Int) {
    if (root == null) return
    res[r][c] = root.`val`.toString()
    if (root.left != null) {
        fill(res, root.left, r + 1, c - (1 shl (height - r - 1)), height)
    }
    if (root.right != null) {
        fill(res, root.right, r + 1, c + (1 shl (height - r - 1)), height)
    }
}

fun printTree(root: TreeNode?): Array<Array<String>> {
    val height = findHeight(root)
    val m = height + 1
    val n = (1 shl (height + 1)) - 1
    val res = Array(m) { Array(n) { "" } }
    fill(res, root, 0, (n - 1) / 2, height)
    return res
}

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

Задача: 350. Intersection of Two Arrays II
Сложность: easy

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

Пример:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

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

1⃣Подсчет частоты элементов:
Используйте хеш-таблицу или словарь для подсчета количества вхождений каждого элемента в nums1.

2⃣Нахождение пересечения:
Пройдите по элементам nums2, и если элемент присутствует в хеш-таблице из шага 1 и его счетчик больше нуля, добавьте этот элемент в результат и уменьшите счетчик.

3⃣Возврат результата:
Верните массив пересечения.

😎 Решение:

class Solution {
    fun intersect(nums1: IntArray, nums2: IntArray): IntArray {
        val counts = mutableMapOf<Int, Int>()
        val result = mutableListOf<Int>()
        
        for (num in nums1) {
            counts[num] = counts.getOrDefault(num, 0) + 1
        }
        
        for (num in nums2) {
            if (counts.getOrDefault(num, 0) > 0) {
                result.add(num)
                counts[num] = counts[num]!! - 1
            }
        }
        
        return result.toIntArray()
    }
}

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

Задача: 257. Binary Tree Paths
Сложность: easy

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

Лист — это узел без детей.

Пример:

Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]

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

1⃣Если текущий узел не является null, добавьте его значение к текущему пути.
Если текущий узел является листом (не имеет дочерних узлов), добавьте текущий путь в список путей.
Если текущий узел не является листом, добавьте "->" к текущему пути и рекурсивно вызовите функцию для левого и правого дочерних узлов.

2⃣Начните с корневого узла, пустого пути и пустого списка путей.

3⃣Верните список всех путей от корня до листа.

😎 Решение:

class Solution {
    fun construct_paths(root: TreeNode?, path: String, paths: MutableList<String>) {
        if (root != null) {
            var path = path + root.`val`
            if (root.left == null && root.right == null) {
                paths.add(path)
            } else {
                path += "->"
                construct_paths(root.left, path, paths)
                construct_paths(root.right, path, paths)
            }
        }
    }

    fun binaryTreePaths(root: TreeNode?): List<String> {
        val paths = mutableListOf<String>()
        construct_paths(root, "", paths)
        return paths
    }
}

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

Задача: 303. Range Sum Query - Immutable
Сложность: easy

Дан целочисленный массив nums. Обработайте несколько запросов следующего типа:
Вычислите сумму элементов массива nums между индексами left и right включительно, где left <= right.
Реализуйте класс NumArray:
- NumArray(int[] nums) Инициализирует объект с целочисленным массивом nums.
- int sumRange(int left, int right) Возвращает сумму элементов массива nums между индексами left и right включительно (т.е. nums[left] + nums[left + 1] + ... + nums[right]).

Пример:

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

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

1⃣Инициализация:
Создайте массив sum длиной на один элемент больше, чем массив nums, и заполните его накопленными суммами элементов массива nums.

2⃣Предварительное вычисление сумм:
Заполните массив sum, где каждый элемент sum[i + 1] является суммой всех предыдущих элементов массива nums до индекса i включительно.

3⃣Вычисление диапазонной суммы:
Для каждого запроса суммы элементов между индексами left и right используйте разницу между sum[right + 1] и sum[left], чтобы быстро получить результат.

😎 Решение:

class NumArray(nums: IntArray) {
    private val sum: IntArray = IntArray(nums.size + 1)

    init {
        for (i in nums.indices) {
            sum[i + 1] = sum[i] + nums[i]
        }
    }

    fun sumRange(i: Int, j: Int): Int {
        return sum[j + 1] - sum[i]
    }
}

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

Задача: 869. Reordered Power of 2
Сложность: medium

Дано целое число n. Мы можем переставить цифры числа в любом порядке (включая исходный порядок), при этом ведущая цифра не должна быть нулем.

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

Пример:

Input: n = 1
Output: true

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

1⃣Сгенерируйте все перестановки цифр числа, размещая любую цифру на первой позиции (start = 0), затем любую из оставшихся цифр на второй позиции (start = 1) и так далее. В Python можно использовать встроенную функцию itertools.permutations.

2⃣Проверьте, что перестановка представляет собой степень двойки, убедившись, что в перестановке нет ведущего нуля, и удаляя все множители 2. Если результат равен 1 (то есть, он не содержал других множителей, кроме 2), то это была степень двойки. В Python можно использовать проверку bin(N).count('1') == 1.

3⃣Верните true, если хотя бы одна перестановка является степенью двойки, иначе верните false.

😎 Решение:

class Solution {
    fun reorderedPowerOf2(N: Int): Boolean {
        val A = N.toString().map { it - '0' }.toIntArray()
        return permutations(A, 0)
    }

    private fun isPowerOfTwo(A: IntArray): Boolean {
        if (A[0] == 0) return false
        var N = A.joinToString("").toInt()
        while (N > 0 && (N and 1) == 0) N = N shr 1
        return N == 1
    }

    private fun permutations(A: IntArray, start: Int): Boolean {
        if (start == A.size) return isPowerOfTwo(A)
        for (i in start until A.size) {
            A.swap(start, i)
            if (permutations(A, start + 1)) return true
            A.swap(start, i)
        }
        return false
    }

    private fun IntArray.swap(i: Int, j: Int) {
        val temp = this[i]
        this[i] = this[j]
        this[j] = temp
    }
}

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

Задача: 719. Find K-th Smallest Pair Distance
Сложность: hard

Расстояние между парой целых чисел a и b определяется как абсолютная разность между a и b. Учитывая целочисленный массив nums и целое число k, верните k-е наименьшее расстояние среди всех пар nums[i] и nums[j], где 0 <= i < j < nums.length.

Пример:

Input: nums = [1,3,1], k = 1
Output: 0

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

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

2⃣Определите минимальное и максимальное возможные расстояния.

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

😎 Решение:

fun countPairs(nums: IntArray, mid: Int): Int {
    var count = 0
    var j = 0
    for (i in nums.indices) {
        while (j < nums.size && nums[j] - nums[i] <= mid) {
            j++
        }
        count += j - i - 1
    }
    return count
}

fun smallestDistancePair(nums: IntArray, k: Int): Int {
    nums.sort()
    var left = 0
    var right = nums.last() - nums.first()
    while (left < right) {
        val mid = (left + right) / 2
        if (countPairs(nums, mid) < k) {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

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

Задача: 1531. String Compression II
Сложность: hard

Дана строка s и целое число k. Необходимо удалить не более k символов из s так, чтобы длина сжатой версии строки s с использованием RLE была минимальной.

Найдите минимальную длину сжатой версии строки s после удаления не более k символов.

Пример:

Input: s = "aaabcccd", k = 2
Output: 4
Explanation: Compressing s without deleting anything will give us "a3bc3d" of length 6. Deleting any of the characters 'a' or 'c' would at most decrease the length of the compressed string to 5, for instance delete 2 'a' then we will have s = "abcccd" which compressed is abc3d. Therefore, the optimal way is to delete 'b' and 'd', then the compressed version of s will be "a3c3" of length 4.

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

1⃣Обходим символы строки слева направо, решая для каждого символа, включать его в сжатую строку или нет. Это создает состояния (строка, оставшиеся для включения символы), которые можно представить в виде бинарного дерева, где левые потомки означают включение символов, а правые — их пропуск. Многочисленные повторяющиеся подзадачи указывают на необходимость использования динамического программирования.

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

3⃣Связываем состояния друг с другом: удаление нового символа увеличивает i на один и уменьшает k на один; включение нового символа оставляет длину сжатия неизменной (кроме случаев, когда частота последнего символа 1, 9 или 99) или увеличивает длину на один, если новый символ не равен последнему символу сжатия.

😎 Решение:

class Solution {
    private val memo = mutableMapOf<Int, Int>()
    private val add = setOf(1, 9, 99)

    fun getLengthOfOptimalCompression(s: String, k: Int): Int {
        return dp(s, 0, ('a' + 26), 0, k)
    }

    private fun dp(s: String, idx: Int, lastChar: Char, lastCharCount: Int, k: Int): Int {
        if (k < 0) return Int.MAX_VALUE / 2

        if (idx == s.length) return 0

        val key = idx * 101 * 27 * 101 + (lastChar - 'a') * 101 * 101 + lastCharCount * 101 + k

        if (memo.containsKey(key)) return memo[key]!!

        val deleteChar = dp(s, idx + 1, lastChar, lastCharCount, k - 1)
        val keepChar = if (s[idx] == lastChar) {
            dp(s, idx + 1, lastChar, lastCharCount + 1, k) + if (add.contains(lastCharCount)) 1 else 0
        } else {
            dp(s, idx + 1, s[idx], 1, k) + 1
        }

        val res = minOf(keepChar, deleteChar)
        memo[key] = res

        return res
    }
}

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

Задача: 937. Reorder Data in Log Files
Сложность: medium

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

Пример:

Input: logs = ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"]
Output: ["let1 art can","let3 art zero","let2 own kit dig","dig1 8 1 5 1","dig2 3 6"]

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

1⃣Разделить журналы на буквенные и цифровые.

2⃣Отсортировать буквенные журналы:
Лексикографически по содержимому.
Если содержимое одинаково, отсортировать по идентификатору.
Объединить отсортированные буквенные журналы и цифровые журналы в исходном порядке.

3⃣Вернуть окончательный результат.

😎 Решение:

class Solution {
    fun reorderLogFiles(logs: Array<String>): Array<String> {
        return logs.sortedWith { log1, log2 ->
            val split1 = log1.split(" ", limit = 2)
            val split2 = log2.split(" ", limit = 2)
            val isDigit1 = split1[1][0].isDigit()
            val isDigit2 = split2[1][0].isDigit()
            
            if (!isDigit1 && !isDigit2) {
                val cmp = split1[1].compareTo(split2[1])
                if (cmp != 0) cmp else split1[0].compareTo(split2[0])
            } else if (isDigit1 && isDigit2) {
                0
            } else if (isDigit1) {
                1
            } else {
                -1
            }
        }.toTypedArray()
    }
}

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

Задача: 904. Fruit Into Baskets
Сложность: medium

Вы посещаете ферму, где в один ряд слева направо расположены фруктовые деревья. Деревья представлены целочисленным массивом fruits, где fruits[i] - это тип фрукта, который производит i-е дерево. Вы хотите собрать как можно больше фруктов. Однако у владельца есть строгие правила, которым вы должны следовать: у вас есть только две корзины, и каждая корзина может содержать только один тип фруктов. Количество фруктов в каждой корзине не ограничено. Начиная с любого дерева по вашему выбору, вы должны собрать ровно один фрукт с каждого дерева (включая начальное), двигаясь при этом вправо. Собранные фрукты должны поместиться в одну из ваших корзин. Как только вы достигнете дерева с фруктами, которые не могут поместиться в ваши корзины, вы должны остановиться. Учитывая целочисленный массив fruits, верните максимальное количество фруктов, которое вы можете собрать.

Пример:

Input: fruits = [1,2,1]
Output: 3

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

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

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

3⃣Подсчитывать максимальное количество фруктов, собранных на каждом шаге.

😎 Решение:

class Solution {
    fun totalFruit(fruits: IntArray): Int {
        val basket = mutableMapOf<Int, Int>()
        var left = 0
        var maxFruits = 0

        for (right in fruits.indices) {
            basket[fruits[right]] = basket.getOrDefault(fruits[right], 0) + 1
            while (basket.size > 2) {
                basket[fruits[left]] = basket[fruits[left]]!! - 1
                if (basket[fruits[left]] == 0) {
                    basket.remove(fruits[left])
                }
                left++
            }
            maxFruits = maxOf(maxFruits, right - left + 1)
        }

        return maxFruits
    }
}

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

Задача: 477. Total Hamming Distance
Сложность: Medium

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

Дан целочисленный массив nums, верните сумму Хэмминговых расстояний между всеми парами чисел в nums.

Пример:

Input: nums = [4,14,2]
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

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

1⃣Для каждой уникальной пары элементов из массива вычисляем битовое XOR, чтобы найти позиции, где биты различаются. Бит, равный 1 в результате, указывает на различие.
2⃣Для каждой пары элементов используем XOR, чтобы получить битовую разницу, и подсчитываем количество битов, равных 1, чтобы определить Хэммингово расстояние между парой.
3⃣Суммируем все Хэмминговы расстояния для всех пар, чтобы получить общую сумму Хэмминговых расстояний.

😎 Решение:

class Solution {
    fun totalHammingDistance(nums: IntArray): Int {
        var ans = 0
        
        if (nums.isEmpty()) {
            return ans
        }
        
        for (i in 0 until nums.size - 1) {
            for (j in i + 1 until nums.size) {
                ans += Integer.bitCount(nums[i] xor nums[j])
            }
        }
        
        return ans
    }
}

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

Задача: 34. Find First and Last Position of Element in Sorted Array
Сложность: medium

Дан массив nums, отсортированный в неубывающем порядке. Найдите начальную и конечную позицию заданного target.
Если target не найден, верните [-1, -1]. Алгоритм должен работать за O(log n).

Пример:

Input: nums = [5,7,7,8,8,10], target = 8  
Output: [3,4]  

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

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

2⃣Если target не найден, возвращаем [-1, -1].

3⃣Снова выполняем бинарный поиск, чтобы найти последнее вхождение target.

😎 Решение:

class Solution {
    fun searchRange(nums: IntArray, target: Int): IntArray {
        val firstOccurrence = findBound(nums, target, true)
        if (firstOccurrence == -1) {
            return intArrayOf(-1, -1)
        }
        val lastOccurrence = findBound(nums, target, false)
        return intArrayOf(firstOccurrence, lastOccurrence)
    }

    private fun findBound(nums: IntArray, target: Int, isFirst: Boolean): Int {
        var left = 0
        var right = nums.size - 1

        while (left <= right) {
            val mid = (left + right) / 2
            if (nums[mid] == target) {
                if (isFirst) {
                    if (mid == left || nums[mid - 1] != target) return mid
                    right = mid - 1
                } else {
                    if (mid == right || nums[mid + 1] != target) return mid
                    left = mid + 1
                }
            } else if (nums[mid] > target) {
                right = mid - 1
            } else {
                left = mid + 1
            }
        }
        return -1
    }
}

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

Задача: 819. Most Common Word
Сложность: easy

Дана строка paragraph и массив строк banned, представляющий запрещенные слова. Верните наиболее часто встречающееся слово, которое не запрещено. Гарантируется, что существует хотя бы одно слово, которое не запрещено, и что ответ является уникальным.

Слова в paragraph нечувствительны к регистру, и ответ должен быть возвращен в нижнем регистре.

Пример:

Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"]
Output: "ball"
Explanation: 
"hit" occurs 3 times, but it is a banned word.
"ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. 
Note that words in the paragraph are not case sensitive,
that punctuation is ignored (even if adjacent to words, such as "ball,"), 
and that "hit" isn't the answer even though it occurs more because it is banned.

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

1⃣Заменяем всю пунктуацию пробелами и одновременно переводим каждую букву в нижний регистр. Это можно сделать и в два этапа, но здесь мы объединяем их в один этап.

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

3⃣Затем итерируемся по словам, чтобы подсчитать количество появлений каждого уникального слова, исключая слова из списка запрещенных. С помощью хеш-таблицы {слово->количество} проходим по всем элементам, чтобы найти слово с наивысшей частотой.

😎 Решение:

class Solution {
    fun mostCommonWord(paragraph: String, banned: List<String>): String {
        val normalizedStr = paragraph.map { if (it.isLetterOrDigit()) it.lowercaseChar() else ' ' }.joinToString("")
        val words = normalizedStr.split("\\s+".toRegex()).filter { it.isNotEmpty() }
        val wordCount = mutableMapOf<String, Int>()
        val bannedWords = banned.toSet()

        for (word in words) {
            if (word !in bannedWords) {
                wordCount[word] = wordCount.getOrDefault(word, 0) + 1
            }
        }

        return wordCount.maxByOrNull { it.value }!!.key
    }

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

Задача: 713. Subarray Product Less Than K
Сложность: medium

Если задан массив целых чисел nums и целое число k, верните количество смежных подмассивов, в которых произведение всех элементов в подмассиве строго меньше k.

Пример:

Input: nums = [10,5,2,6], k = 100
Output: 8

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

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

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

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

😎 Решение:

fun numSubarrayProductLessThanK(nums: IntArray, k: Int): Int {
    if (k <= 1) return 0
    var product = 1
    var count = 0
    var left = 0
    for (right in nums.indices) {
        product *= nums[right]
        while (product >= k) {
            product /= nums[left]
            left++
        }
        count += right - left + 1
    }
    return count
}

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

Задача: 82. Remove Duplicates from Sorted List II
Сложность: medium

Дана голова отсортированного связного списка. Удалите все узлы, содержащие повторяющиеся числа, оставив только уникальные числа из исходного списка. Верните отсортированный связный список.

Пример:

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

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

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

2⃣Проход по списку с проверкой на дубликаты:
Итерируемся по списку начиная с головы head. На каждом шаге проверяем, есть ли дублирующиеся узлы, сравнивая текущий узел head.val с следующим head.next.val.
Если узлы дублируются, то пропускаем все последующие дубликаты, перемещая указатель head до последнего дублированного узла. После этого предшественник pred соединяется с первым узлом после всех дубликатов pred.next = head.next, тем самым пропуская весь блок дублированных узлов.

3⃣Переход к следующему узлу и возврат результата:
Если текущий узел не имел дубликатов, просто переводим предшественника pred на следующий узел.
Двигаем указатель head на следующий узел в списке.
После завершения цикла возвращаем список, начиная с узла, на который указывает sentinel.next, что позволяет исключить все дублирующиеся узлы и вернуть начало нового списка без дубликатов.

😎 Решение:

class Solution {
    fun deleteDuplicates(head: ListNode?): ListNode? {
        val sentinel = ListNode(0)
        sentinel.next = head
        var pred = sentinel
        var current = head

        while (current != null) {
            if (current.next != null && current.`val` == current.next!!.`val`) {
                while (current.next != null && current.`val` == current.next!!.`val`) {
                    current = current.next
                }
                pred.next = current.next
            } else {
                pred = pred.next!!
            }
            current = current.next
        }

        return sentinel.next
    }

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

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

Задача: 162. Find Peak Element
Сложность: medium

Пиковый элемент — это такой элемент массива, который строго больше своих соседей.
Нужно найти любой пик и вернуть его индекс.
Допустим, что nums[-1] = nums[n] = -∞.
Решение должно работать за O(log n).

Пример:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

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

1⃣Инициализируем low = 0 и high = nums.lastIndex. На каждом шаге находим mid = (low + high) / 2.

2⃣Если nums[mid] > nums[mid + 1], это значит, что слева есть пик — сдвигаем high = mid.

3⃣Иначе пик находится справа — сдвигаем low = mid + 1. Завершаем, когда low == high — это и есть индекс пика.

😎 Решение:

class Solution {
    fun findPeakElement(nums: IntArray): Int {
        return search(nums, 0, nums.size - 1)
    }

    private fun search(nums: IntArray, l: Int, r: Int): Int {
        if (l == r) return l
        val mid = (l + r) / 2
        return if (nums[mid] > nums[mid + 1]) search(nums, l, mid)
        else search(nums, mid + 1, r)
    }
}

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

Задача: 393. UTF-8 Validation
Сложность: medium

Символ вДан целочисленный массив данных, представляющий возвращаемые данные, является ли это допустимой кодировкой UTF-8 (т.е. переводится в последовательность допустимых закодированных символов UTF-8).
Символ в UTF-8 может иметь длину от 1 до 4 байтов, с соблюдением таких правил:

1 байт: начинается с 0, далее 7 бит кода

n байтов: n битовединиц, за ними 0, затем (n - 1) байтов с префиксом10

Пример:

Input: data = [197,130,1]
Output: true
Explanation: data represents the octet sequence: 11000101 10000010 00000001.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.

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

1⃣Преобразовать каждый элемент массива в 8-битную бинарную форму ( padStart(8, '0')).

2⃣Если nBytes == 0, определите количество ведущих единиц — это размер текущего символа UTF-8. Если 1 или больше 4 — ошибка.

3⃣Если nBytes > 0вы уверены, что настоящий байт начинается с 10. Уменьшить nBytes. В конце nBytesдолжно быть 0.

😎 Решение:

fun main() {
    val solution = Solution()
    println(solution.validUtf8(intArrayOf(197, 130, 1))) // true
    println(solution.validUtf8(intArrayOf(235, 140, 4))) // false
}

class Solution {
    fun validUtf8(data: IntArray): Boolean {
        var nBytes = 0

        for (num in data) {
            val binRep = num.toString(2).padStart(8, '0').takeLast(8)

            if (nBytes == 0) {
                for (bit in binRep) {
                    if (bit == '0') break
                    nBytes++
                }

                if (nBytes == 0) {
                    continue
                }

                if (nBytes == 1 || nBytes > 4) {
                    return false
                }
            } else {
                if (!(binRep[0] == '1' && binRep[1] == '0')) {
                    return false
                }
            }

            nBytes--
        }

        return nBytes == 0
    }
}

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