Задача: 1662. Check If Two String Arrays are Equivalent
Сложность: easy

Даны два массива строк word1 и word2. Верните true, если два массива представляют одну и ту же строку, и false в противном случае.

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

Пример:

Input: word1 = ["ab", "c"], word2 = ["a", "bc"]
Output: true
Explanation:
word1 represents string "ab" + "c" -> "abc"
word2 represents string "a" + "bc" -> "abc"
The strings are the same, so return true.

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

1⃣Построение списка символов для word2:
Создайте список list2 для хранения всех символов из массива строк word2.

2⃣Итерация по word1 и проверка соответствующих символов:
Итеративно пройдите по строкам в word1 и сравнивайте каждый символ с соответствующим символом из list2.

3⃣Возврат результата:
Верните true, если все символы совпадают, и false, если найдены несовпадения или длины строк не совпадают.

😎 Решение:

class Solution {
    fun arrayStringsAreEqual(word1: Array<String>, word2: Array<String>): Boolean {
        val list2 = word2.joinToString("")
        var index = 0

        for (word in word1) {
            for (char in word) {
                if (index >= list2.length || char != list2[index]) {
                    return false
                }
                index++
            }
        }

        return index == list2.length
    }
}

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

Задача: 338. Counting Bits
Сложность: easy

Дано целое число n, верните массив ans длиной n + 1, такой что для каждого i (0 <= i <= n), ans[i] будет равняться количеству единиц в двоичном представлении числа i.

Пример:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

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

1⃣Инициализация массива:
Создайте массив ans длиной n + 1, заполненный нулями. Этот массив будет содержать количество единиц в двоичном представлении каждого числа от 0 до n.

2⃣Итерация и вычисление:
Пройдите в цикле по всем числам от 1 до n. Для каждого числа x используйте битовую операцию x & (x - 1), чтобы убрать последнюю установленную биту, и добавьте 1 к значению ans для этого результата. Это количество единиц в двоичном представлении числа x.

3⃣Возврат результата:
Верните заполненный массив ans, который содержит количество единиц для каждого числа от 0 до n.

😎 Решение:

class Solution {
    fun countBits(num: Int): IntArray {
        val ans = IntArray(num + 1)
        for (x in 1..num) {
            ans[x] = ans[x and (x - 1)] + 1
        }
        return ans
    }
}

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

Задача: 591. Tag Validator
Сложность: hard

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

Фрагмент кода считается корректным, если соблюдаются все следующие правила:
Код должен быть заключен в корректный закрытый тег. В противном случае код некорректен.
Закрытый тег (не обязательно корректный) имеет точно следующий формат: <TAG_NAME>TAG_CONTENT</TAG_NAME>. Среди них <TAG_NAME> — это начальный тег, а </TAG_NAME> — конечный тег. TAG_NAME в начальном и конечном тегах должен быть одинаковым. Закрытый тег корректен, если и только если TAG_NAME и TAG_CONTENT корректны.
Корректное TAG_NAME содержит только заглавные буквы и имеет длину в диапазоне [1, 9]. В противном случае TAG_NAME некорректен.
Корректное TAG_CONTENT может содержать другие корректные закрытые теги, cdata и любые символы (см. примечание 1), КРОМЕ неподходящих <, неподходящих начальных и конечных тегов, и неподходящих или закрытых тегов с некорректным TAG_NAME. В противном случае TAG_CONTENT некорректен.
Начальный тег неподходящий, если нет конечного тега с тем же TAG_NAME, и наоборот. Однако нужно также учитывать проблему несбалансированных тегов, когда они вложены.
< неподходящий, если не удается найти последующий >. И когда вы находите < или </, все последующие символы до следующего > должны быть разобраны как TAG_NAME (не обязательно корректный).
cdata имеет следующий формат: <![CDATA[CDATA_CONTENT]]>. Диапазон CDATA_CONTENT определяется как символы между <![CDATA[ и первым последующим ]]>.
CDATA_CONTENT может содержать любые символы. Функция cdata заключается в том, чтобы запретить валидатору разбирать CDATA_CONTENT, поэтому даже если в нем есть символы, которые могут быть разобраны как тег (корректный или некорректный), вы должны рассматривать их как обычные символы.

Пример:

Input: code = "<DIV>This is the first line <![CDATA[<div>]]></DIV>"
Output: true

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

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

2⃣Пройдитесь по строке, проверяя каждый символ. Если встретите <, определите тип тега (начальный, конечный или CDATA). Обновите стек и индексы в зависимости от найденного типа.

3⃣В конце проверьте, что стек пуст (все теги корректно закрыты) и верните результат.

😎 Решение:

import java.util.regex.Pattern

class Solution {
    private val stack = mutableListOf<String>()
    private var containsTag = false

    private fun isValidTagName(s: String, ending: Boolean): Boolean {
        return if (ending) {
            if (stack.isNotEmpty() && stack.last() == s) stack.removeAt(stack.size - 1) else false
        } else {
            containsTag = true
            stack.add(s)
            true
        }
    }

    fun isValid(code: String): Boolean {
        val regex = "<[A-Z]{0,9}>([^<]*(<((\\/?[A-Z]{1,9}>)|(!\\[CDATA\\[(.*?)]]>)))?)*"
        if (!Pattern.matches(regex, code)) return false

        var i = 0
        while (i < code.length) {
            var ending = false
            if (stack.isEmpty() && containsTag) return false
            if (code[i] == '<') {
                if (code[i + 1] == '!') {
                    i = code.indexOf("]]>", i + 1)
                    if (i == -1) return false
                    continue
                }
                if (code[i + 1] == '/') {
                    i++
                    ending = true
                }
                val closeIndex = code.indexOf('>', i + 1)
                if (closeIndex == -1 || !isValidTagName(code.substring(i + 1, closeIndex), ending)) return false
                i = closeIndex
            }
            i++
        }
        return stack.isEmpty()
    }
}

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

Задача: 1663. Smallest String With A Given Numeric Value4
Сложность: medium

Числовое значение строчной буквы определяется ее позицией (начиная с 1) в алфавите, поэтому числовое значение a равно 1, числовое значение b равно 2, числовое значение c равно 3 и так далее.

Числовое значение строки, состоящей из строчных букв, определяется как сумма числовых значений ее символов. Например, числовое значение строки "abe" равно 1 + 2 + 5 = 8.

Вам даны два целых числа n и k. Верните лексикографически наименьшую строку длиной n с числовым значением, равным k.

Обратите внимание, что строка x лексикографически меньше строки y, если x идет перед y в словарном порядке, то есть либо x является префиксом y, либо, если i - первая позиция, где x[i] != y[i], то x[i] идет перед y[i] в алфавитном порядке.

Пример:

Input: n = 3, k = 27
Output: "aay"
Explanation: The numeric value of the string is 1 + 1 + 25 = 27, and it is the smallest string with such a value and length equal to 3.

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

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

2⃣Итерация от позиции 1 до n и заполнение символом каждой позиции:
Найти позиции, которые нужно заполнить, исключая текущую позицию, задаваемую переменной positionsLeft как n - position - 1.
Если значение k больше, чем positionsLeft * 26, зарезервировать числовое значение 26 (символ z) для всех оставшихся позиций positionsLeft. Вычислить значение текущей позиции, заданное переменной add, как k - (positionsLeft * 26). Вычесть рассчитанное значение add из k, чтобы найти оставшееся значение k после заполнения текущей позиции.
Иначе, заполнить текущую позицию символом a, имеющим числовое значение 1. Вычесть 1 из k, чтобы найти оставшееся значение k после заполнения текущей позиции.

3⃣Повторять процесс, пока все позиции не будут заполнены.

😎 Решение:

class Solution {
    fun getSmallestString(n: Int, k: Int): String {
        val result = CharArray(n) { 'a' }
        var k = k
        
        for (position in 0 until n) {
            val positionsLeft = (n - position - 1)
            if (k > positionsLeft * 26) {
                val add = k - (positionsLeft * 26)
                result[position] = ('a'.code + add - 1).toChar()
                k -= add
            } else {
                k -= 1
            }
        }
        
        return String(result)
    }
}

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

Задача: 893. Groups of Special-Equivalent Strings
Сложность: medium

Вам дан массив строк одинаковой длины words. За один ход вы можете поменять местами любые два четных или любые два нечетных символа строки words[i]. Две строки words[i] и words[j] являются специально-эквивалентными, если после любого количества ходов words[i] == words[j].

Например, words[i] = "zzxy" и words[j] = "xyzz" являются специально-эквивалентными, потому что мы можем делать ходы "zzxy" -> "xzzy" -> "xyzz". Группа специально-эквивалентных строк из слов - это непустое подмножество слов, такое, что: каждая пара строк в группе специально-эквивалентна, и группа имеет максимально возможный размер (т.е, не существует строки words[i], не входящей в группу, такой, что words[i] является специально-эквивалентной каждой строке в группе). Верните количество групп специально-эквивалентных строк из слов.

Пример:

Input: words = ["abcd","cdab","cbad","xyzz","zzxy","zzyx"]
Output: 3

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

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

2⃣Использовать множество, чтобы хранить все уникальные канонические формы строк.

3⃣Размер множества будет равен количеству групп специально-эквивалентных строк.

😎 Решение:

fun numSpecialEquivGroups(words: Array<String>): Int {
    val uniqueForms = mutableSetOf<String>()
    
    for (word in words) {
        val evenChars = word.filterIndexed { index, _ -> index % 2 == 0 }.toCharArray().sorted()
        val oddChars = word.filterIndexed { index, _ -> index % 2 != 0 }.toCharArray().sorted()
        val canonicalForm = evenChars.joinToString("") + oddChars.joinToString("")
        uniqueForms.add(canonicalForm)
    }
    
    return uniqueForms.size

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

Задача: 606. Construct String from Binary Tree
Сложность: Medium

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

Представление узлов: Каждый узел в дереве должен быть представлен его целочисленным значением.

Скобки для дочерних узлов: Если у узла есть хотя бы один дочерний узел (левый или правый), его дочерние узлы должны быть представлены в скобках. Конкретно:

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

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

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

Пример:

Input: root = [1,2,3,4]
Output: "1(2(4))(3)"
Explanation: Originally, it needs to be "1(2(4)())(3()())", but you need to omit all the empty parenthesis pairs. And it will be "1(2(4))(3)".

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

1⃣Инициализация и рекурсия
Начинаем с корневого узла бинарного дерева и выполняем прямой обход (preorder traversal) с использованием рекурсии. Для каждого узла добавляем его значение к строке результата.

2⃣Обработка дочерних узлов
Случай 1: Если у узла есть оба дочерних узла (левый и правый), оборачиваем результаты прямого обхода для обоих дочерних узлов в скобки. Случай 2: Если у узла нет дочерних узлов, пропускаем скобки для них. Случай 3: Если у узла есть только левый дочерний узел, обходим его и добавляем результат в скобках, пропуская пустые скобки для правого дочернего узла. Случай 4: Если у узла есть только правый дочерний узел, добавляем пустые скобки для левого дочернего узла и обходим правый дочерний узел, добавляя его результат в скобках.

3⃣Объединение результатов
Собираем результаты для каждого узла, учитывая все упомянутые случаи, чтобы получить строковое представление дерева.

😎 Решение:

class Solution {
    fun tree2str(t: TreeNode?): String {
        val res = StringBuilder()
        dfs(t, res)
        return res.toString()
    }

    private fun dfs(t: TreeNode?, res: StringBuilder) {
        if (t == null) return
        res.append(t.`val`)
        if (t.left == null && t.right == null) return
        res.append('(')
        dfs(t.left, res)
        res.append(')')
        if (t.right != null) {
            res.append('(')
            dfs(t.right, res)
            res.append(')')
        }
    }
}

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

Задача: 784. Letter Case Permutation
Сложность: medium

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

Пример:

Input: s = "a1b2"
Output: ["a1b2","a1B2","A1b2","A1B2"]

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

1⃣Если следующий символ c является буквой, то мы удвоим все слова в нашем текущем ответе, и добавим lowercase(c) к каждому слову в первой половине, и uppercase(c) к каждому слову во второй половине.

2⃣Если c является цифрой, мы добавим его к каждому слову.

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

😎 Решение:

class Solution {
    fun letterCasePermutation(S: String): List<String> {
        val ans: MutableList<MutableList<Char>> = mutableListOf(mutableListOf())
        
        for (char in S) {
            val n = ans.size
            if (char.isLetter()) {
                for (i in 0 until n) {
                    ans.add(ans[i].toMutableList())
                    ans[i].add(char.lowercaseChar())
                    ans[n + i].add(char.uppercaseChar())
                }
            } else {
                for (i in 0 until n) {
                    ans[i].add(char)
                }
            }
        }
        
        return ans.map { it.joinToString("") }
    }
}

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

Задача: 1042. Flower Planting With No Adjacent
Сложность: medium

У вас есть n садов, помеченных от 1 до n, и массив paths, где paths[i] = [xi, yi] описывает двунаправленный путь между садом xi и садом yi. В каждом саду вы хотите посадить один из 4 типов цветов. Все сады имеют не более 3 путей, входящих и выходящих из него. Ваша задача - выбрать тип цветка для каждого сада так, чтобы для любых двух садов, соединенных путем, они имели разные типы цветов. Верните любой такой выбор в виде массива answer, где answer[i] - тип цветка, посаженного в (i+1)-м саду. Типы цветов обозначаются 1, 2, 3 или 4. Ответ гарантированно существует.

Пример:

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

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

1⃣Построение графа:
Создайте граф из садов и путей между ними.

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

3⃣Мы будем проходить по каждому саду и выбирать тип цветка, который не совпадает с типами цветов в соседних садах. Поскольку у каждого сада не более трех соседей, всегда будет возможность выбрать тип цветка из 4 возможных типов.

😎 Решение:

class Solution {
    fun gardenNoAdj(n: Int, paths: Array<IntArray>): IntArray {
        val graph = Array(n) { mutableListOf<Int>() }
        for (path in paths) {
            graph[path[0] - 1].add(path[1] - 1)
            graph[path[1] - 1].add(path[0] - 1)
        }
        
        val answer = IntArray(n)
        for (garden in 0 until n) {
            val used = mutableSetOf(answer[graph[garden]])
            for (flower in 1..4) {
                if (!used.contains(flower)) {
                    answer[garden] = flower
                    break
                }
            }
        }
        
        return answer
    }
}

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

Задача: 363. Max Sum of Rectangle No Larger Than K
Сложность: hard

Дана матрица размером m x n и целое число k, вернуть максимальную сумму прямоугольника в матрице, такая что его сумма не превышает k.

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

Пример:

Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2
Explanation: Because the sum of the blue rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).

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

1⃣Создать вспомогательную функцию updateResult, которая будет находить максимальную сумму подмассива в одномерном массиве, не превышающую k.

2⃣Преобразовать каждую подматрицу в одномерный массив и применить к ней функцию updateResult.

3⃣Вернуть максимальную найденную сумму.

😎 Решение:

class Solution {
    var result = Int.MIN_VALUE

    private fun updateResult(nums: IntArray, k: Int) {
        var sum = 0
        val sortedSum = TreeSet<Int>()
        sortedSum.add(0)

        for (num in nums) {
            sum += num
            val x = sortedSum.ceiling(sum - k)
            if (x != null) {
                result = maxOf(result, sum - x)
            }
            sortedSum.add(sum)
        }
    }

    fun maxSumSubmatrix(matrix: Array<IntArray>, k: Int): Int {
        val rows = matrix.size
        val cols = matrix[0].size

        for (i in 0 until rows) {
            val rowSum = IntArray(cols)
            for (row in i until rows) {
                for (col in 0 until cols) {
                    rowSum[col] += matrix[row][col]
                }
                updateResult(rowSum, k)
                if (result == k) {
                    return result
                }
            }
        }
        return result
    }
}

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

Задача: 1003. Check If Word Is Valid After Substitutions
Сложность: medium

Дана строка s, определите, является ли она допустимой. Строка s допустима, если, начиная с пустой строки t = "", вы можете преобразовать t в s, выполнив следующую операцию любое количество раз: вставить строку "abc" в любую позицию в t. Более формально, t становится tleft + "abc" + tright, где t == tleft + tright. Обратите внимание, что tleft и tright могут быть пустыми. Верните true, если s - допустимая строка, иначе верните false.

Пример:

Input: s = "aabcbc"
Output: true

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

1⃣Проверка допустимости длины строки:
Проверьте, что длина строки s кратна 3. Если нет, верните false.

2⃣Использование стека для проверки:
Инициализируйте пустой стек. Проходите по каждому символу строки s.
Если текущий символ является 'c', проверьте, что два предыдущих символа в стеке - это 'b' и 'a' соответственно. Если это так, удалите 'b' и 'a' из стека. Если нет, верните false.
Если текущий символ не 'c', добавьте его в стек.

3⃣Проверка остатка стека:
В конце, если стек пуст, верните true. Иначе верните false.

😎 Решение:

class Solution {
    fun isValid(s: String): Boolean {
        if (s.length % 3 != 0) return false

        val stack = mutableListOf<Char>()
        for (char in s) {
            if (char == 'c') {
                if (stack.size < 2 || stack[stack.size - 1] != 'b' || stack[stack.size - 2] != 'a') {
                    return false
                }
                stack.removeAt(stack.size - 1)
                stack.removeAt(stack.size - 1)
            } else {
                stack.add(char)
            }
        }

        return stack.isEmpty()
    }
}

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

Задача: 217. Contains Duplicate
Сложность: easy

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

Пример:

Input: nums = [1,2,3,4]
Output: false

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

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

2⃣Итерируйте по отсортированному массиву и сравнивайте каждое число с следующим.

3⃣Если любое число совпадает с следующим, верните true. Если цикл завершится без совпадений, верните false.

😎 Решение:

fun containsDuplicate(nums: IntArray): Boolean {
    nums.sort()
    for (i in 0 until nums.size - 1) {
        if (nums[i] == nums[i + 1]) {
            return true
        }
    }
    return false
}

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

Задача: 275. H-Index II
Сложность: medium

Дан массив целых чисел citations, где citations[i] — количество цитирований, которое исследователь получил за свою i-ю статью, и массив отсортирован в порядке возрастания. Верните h-индекс исследователя.
Согласно определению h-индекса на Википедии: h-индекс определяется как максимальное значение h, такое что данный исследователь опубликовал по крайней мере h статей, каждая из которых была процитирована как минимум h раз.
Вы должны написать алгоритм, который работает за логарифмическое время.

Пример:

Input: citations = [0,1,3,5,6]
Output: 3
Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.

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

1⃣Найти середину массива:
Определить средний элемент массива, чтобы разделить его на две подмножества: citations[0: mid - 1] и citations[mid + 1: n].

2⃣Сравнить количество статей с цитированиями больше или равными citations[mid]:
Если citations[mid] == n - mid, то найден h-индекс и его можно вернуть.
Если citations[mid] < n - mid, то необходимо искать в правой подмножности citations[mid + 1: n].
Если citations[mid] > n - mid, то необходимо искать в левой подмножности citations[0: mid - 1].

3⃣Возвращение результата:
Продолжать процесс, пока не будет найден h-индекс.
Возвратить n - mid, что является количеством статей с цитированиями больше или равными citations[mid].

😎 Решение:

class Solution {
    fun hIndex(citations: IntArray): Int {
        val n = citations.size
        var left = 0
        var right = n - 1
        
        while (left <= right) {
            val mid = left + (right - left) / 2
            if (citations[mid] == n - mid) {
                return n - mid
            } else if (citations[mid] < n - mid) {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        return n - left
    }
}

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

Задача: 933. Number of Recent Calls
Сложность: easy

У вас есть класс RecentCounter, который подсчитывает количество последних запросов за определенный промежуток времени. Реализуйте класс RecentCounter: RecentCounter() Инициализирует счетчик нулем последних запросов. int ping(int t) Добавляет новый запрос в момент времени t, где t представляет собой некоторое время в миллисекундах, и возвращает количество запросов, произошедших за последние 3000 миллисекунд (включая новый запрос). Точнее, возвращается количество запросов, произошедших в диапазоне [t - 3000, t]. Гарантируется, что каждый вызов ping использует строго большее значение t, чем предыдущий вызов.

Пример:

Input
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
Output
[null, 1, 2, 3, 3]

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

1⃣Создать класс RecentCounter с конструктором для инициализации пустой очереди.

2⃣Реализовать метод ping, который принимает время запроса t:
Добавить t в очередь.
Удалить из очереди все запросы, которые не попадают в диапазон [t - 3000, t].

3⃣Вернуть размер очереди.

😎 Решение:

class RecentCounter {
    private val q: ArrayDeque<Int> = ArrayDeque()
    
    fun ping(t: Int): Int {
        q.addLast(t)
        while (q.first() < t - 3000) {
            q.removeFirst()
        }
        return q.size
    }
}

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

🔥 Записал видос "Как за 3 минуты настроить Автоотклики на вакансии HeadHunter" больше не придется заниматься этой унылой рутиной

📺 Видео: https://youtu.be/G_FOwEGPwlw

Задача: 93. Restore IP Addresses
Сложность: medium

Дана строка s, содержащая только цифры. Верните все возможные корректные IP-адреса, которые можно получить из s, вставляя три точки. IP-адрес состоит из четырёх чисел (от 0 до 255), разделённых точками. Нельзя использовать ведущие нули (например, "01" — недопустимо).

Пример:

Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

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

1⃣Входим в рекурсию с данной строкой, начиная с индекса 0.

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

3⃣Мемоизация помогает снизить сложность, которая иначе была бы экспоненциальной. Мы проверяем словарь memo, чтобы увидеть, существует ли уже результат для данной подстроки. Если результат уже находится в memo, мы возвращаем этот результат. В противном случае количество способов для данной строки определяется путем рекурсивного вызова функции с индексом +1 для следующей подстроки и индексом +2 после проверки на валидность двузначного декодирования. Результат также сохраняется в memo с ключом как текущий индекс, чтобы сохранить его для будущих пересекающихся подзадач.

😎 Решение:

class Solution {
    private fun isValid(s: String, start: Int, length: Int): Boolean {
        if (length == 1) return true
        if (s[start] == '0') return false
        if (length > 3) return false
        val num = s.substring(start, start + length).toInt()
        return num <= 255
    }

    private fun helper(s: String, startIndex: Int, dots: MutableList<Int>, ans: MutableList<String>) {
        val remainingLength = s.length - startIndex
        val remainingNumberOfIntegers = 4 - dots.size
        if (remainingLength > remainingNumberOfIntegers * 3 || remainingLength < remainingNumberOfIntegers) {
            return
        }
        if (dots.size == 3) {
            if (isValid(s, startIndex, remainingLength)) {
                var temp = ""
                var last = 0
                for (dot in dots) {
                    temp += s.substring(last, last + dot) + "."
                    last += dot
                }
                temp += s.substring(startIndex)
                ans.add(temp)
            }
            return
        }
        for (curPos in 1..minOf(3, remainingLength)) {
            dots.add(curPos)
            if (isValid(s, startIndex, curPos)) {
                helper(s, startIndex + curPos, dots, ans)
            }
            dots.removeAt(dots.size - 1)
        }
    }

    fun restoreIpAddresses(s: String): List<String> {
        val answer = mutableListOf<String>()
        helper(s, 0, mutableListOf(), answer)
        return answer
    }
}

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

Задача: 780. Reaching Points
Сложность: hard

Даны четыре целых числа sx, sy, tx и ty, верните true, если возможно преобразовать точку (sx, sy) в точку (tx, ty) с помощью некоторых операций, иначе верните false.

Допустимая операция для некоторой точки (x, y) заключается в преобразовании её либо в (x, x + y), либо в (x + y, y).

Пример:

Input: sx = 1, sy = 1, tx = 3, ty = 5
Output: true
Explanation:
One series of moves that transforms the starting point to the target is:
(1, 1) -> (1, 2)
(1, 2) -> (3, 2)
(3, 2) -> (3, 5)

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

1⃣Повторно вычитайте меньшее из {tx, ty} из большего из {tx, ty}.

2⃣Продолжайте вычитание, пока tx и ty больше или равны sx и sy соответственно.

3⃣Ответ будет true, если и только если в конечном итоге мы достигнем точки sx, sy.

😎 Решение:

class Solution {
    fun reachingPoints(sx: Int, sy: Int, tx: Int, ty: Int): Boolean {
        var tx = tx
        var ty = ty
        while (tx >= sx && ty >= sy) {
            if (sx == tx && sy == ty) return true
            if (tx > ty) {
                tx -= ty
            } else {
                ty -= tx
            }
        }
        return false
    }
}

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

Задача: 1189. Maximum Number of Balloons
Сложность: easy

Дана строка text. Вы хотите использовать символы строки text, чтобы сформировать как можно больше экземпляров слова "balloon".

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

Пример:

Input: text = "nlaebolko"
Output: 1

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

1⃣Подсчитайте количество появлений каждого символа 'b', 'a', 'l', 'o', 'n' в строке text.

2⃣Вычислите потенциал для каждого символа: для 'b' и 'a' потенциал равен количеству их появлений, для 'l' и 'o' потенциал равен количеству их появлений, деленному на 2, а для 'n' потенциал равен количеству его появлений.

3⃣Найдите символ с наименьшим потенциалом среди 'b', 'a', 'l', 'o', 'n', который ограничивает количество возможных слов "balloon", и верните это значение.

😎 Решение:

class Solution {
    fun maxNumberOfBalloons(text: String): Int {
        var bCount = 0
        var aCount = 0
        var lCount = 0
        var oCount = 0
        var nCount = 0

        for (char in text) {
            when (char) {
                'b' -> bCount++
                'a' -> aCount++
                'l' -> lCount++
                'o' -> oCount++
                'n' -> nCount++
            }
        }

        lCount /= 2
        oCount /= 2

        return minOf(bCount, aCount, lCount, oCount, nCount)
    }
}

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

Задача: 1240. Tiling a Rectangle with the Fewest Squares
Сложность: hard

Если задан прямоугольник размером n x m, верните минимальное количество квадратов с целочисленными сторонами, которые покрывают этот прямоугольник.

Пример:

Input: n = 2, m = 3
Output: 3

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

1⃣Инициализация рекурсивной функции:
Функция принимает размеры прямоугольника n x m.

2⃣Базовый случай:
Если n = 0 или m = 0, возвращаем 0, так как не осталось пространства для покрытия.

3⃣Рекурсивный случай:
Находим наибольший возможный квадрат, который может быть размещен в текущем прямоугольнике. Это квадрат со стороной min(n, m).
Размещаем этот квадрат в левом верхнем углу и рекурсивно покрываем оставшиеся три части:
Прямоугольник слева от квадрата.
Прямоугольник сверху от квадрата.
Прямоугольник справа и снизу от квадрата.

😎 Решение:

class Solution {
    fun tilingRectangle(n: Int, m: Int): Int {
        val dp = Array(n + 1) { IntArray(m + 1) { Int.MAX_VALUE } }
        
        for (i in 1..minOf(n, m)) {
            dp[i][i] = 1
        }
        
        for (h in 1..n) {
            for (w in 1..m) {
                if (h == w) continue
                for (i in 1..h / 2) {
                    dp[h][w] = minOf(dp[h][w], dp[i][w] + dp[h - i][w])
                }
                for (j in 1..w / 2) {
                    dp[h][w] = minOf(dp[h][w], dp[h][j] + dp[h][w - j])
                }
            }
        }
        return dp[n][m]
    }
}

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

Задача: 895. Maximum Frequency Stack
Сложность: hard

Разработайте структуру данных, похожую на стек, чтобы заталкивать элементы в стек и вытаскивать из него самый частый элемент. Реализуйте класс FreqStack: FreqStack() строит пустой стек частот. void push(int val) заталкивает целое число val на вершину стека. int pop() удаляет и возвращает самый частый элемент в стеке. Если есть равенство в выборе самого частого элемента, то удаляется и возвращается элемент, который ближе всего к вершине стека.

Пример:

Input
["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"]
[[], [5], [7], [5], [7], [4], [5], [], [], [], []]
Output
[null, null, null, null, null, null, null, 5, 7, 5, 4]

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

1⃣Создать два словаря: freq для хранения частоты каждого элемента и group для хранения стека элементов для каждой частоты.

2⃣При добавлении элемента увеличивать его частоту в freq и добавлять его в стек соответствующей частоты в group.

3⃣При извлечении элемента найти максимальную частоту, удалить элемент из стека соответствующей частоты и уменьшить его частоту в freq. Если стек для данной частоты становится пустым, удалить его.

😎 Решение:

class FreqStack() {
    private val freq = mutableMapOf<Int, Int>()
    private val group = mutableMapOf<Int, MutableList<Int>>()
    private var maxfreq = 0

    fun push(`val`: Int) {
        val f = (freq[`val`] ?: 0) + 1
        freq[`val`] = f
        if (f > maxfreq) {
            maxfreq = f
            group[f] = mutableListOf()
        }
        group[f]?.add(`val`)
    }

    fun pop(): Int {
        val val = group[maxfreq]?.removeAt(group[maxfreq]?.lastIndex ?: 0) ?: -1
        freq[val] = freq[val]!! - 1
        if (group[maxfreq]?.isEmpty() == true) {
            maxfreq--
        }
        return val
    }

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

Задача: 42. Trapping Rain Water
Сложность: hard

Дан массив height, представляющий карту высот.
Каждый столбец имеет ширину 1. Вычислите, сколько воды можно удержать после дождя.

Пример:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]  
Output: 6  

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

1⃣Создаем массивы left_max и right_max, хранящие максимальные высоты слева и справа для каждого индекса.

2⃣Проходим массив, вычисляя минимальную границу воды min(left_max[i], right_max[i]) и добавляем разницу с height[i] в ans.

3⃣Возвращаем ans, содержащий общий объем воды.

😎 Решение:

class Solution {
    fun trap(height: IntArray): Int {
        if (height.isEmpty()) return 0
        val size = height.size
        var ans = 0
        val leftMax = IntArray(size)
        val rightMax = IntArray(size)

        leftMax[0] = height[0]
        for (i in 1 until size) {
            leftMax[i] = maxOf(height[i], leftMax[i - 1])
        }

        rightMax[size - 1] = height[size - 1]
        for (i in size - 2 downTo 0) {
            rightMax[i] = maxOf(height[i], rightMax[i + 1])
        }

        for (i in 1 until size - 1) {
            ans += minOf(leftMax[i], rightMax[i]) - height[i]
        }

        return ans
    }
}

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