#hard
Задача: 757. Set Intersection Size At Least Two

Вам дан двумерный целочисленный массив intervals, в котором intervals[i] = [starti, endi] представляет все целые числа от starti до endi включительно. Содержащее множество - это массив nums, в котором каждый интервал из intervals содержит не менее двух целых чисел в nums. Например, если intervals = [[1,3], [3,7], [8,9]], то [1,2,4,7,8,9] и [2,3,4,8,9] - содержащие множества. Верните минимально возможный размер содержащего множества.

Пример:

Input: intervals = [[1,3],[3,7],[8,9]]
Output: 5

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

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

2⃣Инициализируйте пустое множество для хранения чисел.

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

😎 Решение:

fun minSetSize(intervals: Array<IntArray>): Int {
    intervals.sortBy { it[1] }
    val nums = mutableListOf<Int>()
    for (interval in intervals) {
        val start = interval[0]
        val end = interval[1]
        if (nums.isEmpty() || nums.last() < start) {
            nums.add(end - 1)
            nums.add(end)
        } else if (nums.last() == end - 1) {
            nums.add(end)
        }
    }
    return nums.size
}

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

На easyoffer 2.0 появится:
🎯 Тренажер "Проработка вопросов"

✅ Метод интервальных повторений и флеш-карточки
✅ Персональный подход изучения на основе ваших ответов
✅ Упор на самые частые вопросы

📌 Интервальные повторения по карточкам это научно доказанный метод эффективного обучения. Каждая карточка – это вопрос, который задают на собеседовании, вы можете выбрать "Не знаю", "Знаю", "Не спрашивать". После ответа вам показывается правильный ответ и возможность изучить вопрос подробнее (примеры ответов других людей). От ваших ответов зависит то, как часто карточки будут показываться на следующей тренировке. Трудные вопросы показываются чаще, простые – реже. Это позволяет бить в слабые места. Кроме того, изначальный порядок карточек зависит от частотности (вероятности встретить вопрос).

🚀 Благодаря этому тренажеру вы сможете очень быстро подготовиться к собеседованию, т.к. фокусируетесь отвечать на самые частые вопросы. Именно так готовился я сам, когда искал первую работу программистом.

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

‼️ Очень важно, чтобы как можно больше людей поддержали проект в первые дни, по-этому те кто окажет поддержку первыми получат еще более выгодную стоимость на годовую подписку и существенный 💎 бонус о котором я позже расскажу в этом телеграм канале. Подписывайтесь, чтобы узнать о старте проекта раньше других и воспользоваться лимитированными вознаграждениями.

#medium
Задача: 758. Bold Words in String

При наличии массива ключевых слов и строки a выделите все ключевые слова [i] жирным шрифтом. Все буквы между тегами <b> и </b> выделяются жирным шрифтом.

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

Пример:

Input: words = ["ab","bc"], s = "aabcd"
Output: "a<b>abc</b>d"

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

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

2⃣Пройдите по каждому ключевому слову и отметьте соответствующие позиции в массиве флагов.

3⃣Постройте результирующую строку, добавляя теги <b> и </b> на основе массива флагов.

😎 Решение:

fun addBoldTags(keywords: Array<String>, s: String): String {
    val n = s.length
    val bold = BooleanArray(n)
    
    for (word in keywords) {
        var start = s.indexOf(word)
        while (start != -1) {
            for (i in start until start + word.length) {
                bold[i] = true
            }
            start = s.indexOf(word, start + 1)
        }
    }
    
    val result = StringBuilder()
    var i = 0
    while (i < n) {
        if (bold[i]) {
            result.append("<b>")
            while (i < n && bold[i]) {
                result.append(s[i])
                i++
            }
            result.append("</b>")
        } else {
            result.append(s[i])
            i++
        }
    }
    
    return result.toString()
}

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

#hard
Задача: 759. Employee Free Time

Нам дан список schedule of employees, который представляет собой рабочее время каждого сотрудника. У каждого сотрудника есть список непересекающихся интервалов, и эти интервалы расположены в отсортированном порядке. Верните список конечных интервалов, представляющих общее свободное время положительной длины для всех сотрудников, также в отсортированном порядке. (Хотя мы представляем интервалы в форме [x, y], объекты внутри них являются интервалами, а не списками или массивами. Например, schedule[0][0].start = 1, schedule[0][0].end = 2, а schedule[0][0][0] не определено).Также мы не будем включать в наш ответ интервалы типа [5, 5], так как они имеют нулевую длину.

Пример:

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

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

1⃣Объедините все интервалы всех сотрудников в один список и отсортируйте его по начальным временам.

2⃣Объедините пересекающиеся интервалы в один.

3⃣Найдите промежутки между объединенными интервалами, представляющие свободное время.

😎 Решение:

class Interval(var start: Int, var end: Int)

fun employeeFreeTime(schedule: List<List<Interval>>): List<Interval> {
    val intervals = mutableListOf<Interval>()
    for (employee in schedule) {
        intervals.addAll(employee)
    }
    
    intervals.sortBy { it.start }
    
    val merged = mutableListOf<Interval>()
    for (interval in intervals) {
        if (merged.isEmpty() || merged.last().end < interval.start) {
            merged.add(interval)
        } else {
            merged.last().end = maxOf(merged.last().end, interval.end)
        }
    }
    
    val freeTime = mutableListOf<Interval>()
    for (i in 1 until merged.size) {
        if (merged[i].start > merged[i - 1].end) {
            freeTime.add(Interval(merged[i - 1].end, merged[i].start))
        }
    }
    
    return freeTime
}

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

#easy
Задача: 760. Find Anagram Mappings

Вам даны два целочисленных массива nums1 и nums2, где nums2 - анаграмма nums1. Оба массива могут содержать дубликаты. Верните индексное отображение массива mapping из nums1 в nums2, где mapping[i] = j означает, что i-й элемент в nums1 появляется в nums2 по индексу j. Если ответов несколько, верните любой из них. Массив a является анаграммой массива b означает, что b создается путем случайного изменения порядка элементов в a.

Пример:

Input: nums1 = [12,28,46,32,50], nums2 = [50,12,32,46,28]
Output: [1,4,3,2,0]

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

1⃣Создайте словарь для хранения индексов элементов в nums2.

2⃣Пройдите по элементам массива nums1 и для каждого элемента найдите соответствующий индекс в nums2, используя словарь.

3⃣Верните массив индексов.

😎 Решение:

fun anagramMapping(nums1: IntArray, nums2: IntArray): IntArray {
    val indexMap = mutableMapOf<Int, MutableList<Int>>()
    for (i in nums2.indices) {
        indexMap.computeIfAbsent(nums2[i]) { mutableListOf() }.add(i)
    }
    
    val mapping = IntArray(nums1.size)
    for (i in nums1.indices) {
        mapping[i] = indexMap[nums1[i]]!!.removeAt(indexMap[nums1[i]]!!.size - 1)
    }
    
    return mapping
}

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

#hard
Задача: 761. Special Binary String

Специальные двоичные строки - это двоичные строки, обладающие следующими двумя свойствами: количество 0 равно количеству 1. Каждый префикс двоичной строки имеет не меньше 1, чем 0. Вам дана специальная двоичная строка s. Ход состоит в выборе двух последовательных, непустых специальных подстрок s и их обмене. Две строки являются последовательными, если последний символ первой строки находится ровно на один индекс раньше первого символа второй строки. Верните лексикографически наибольшую результирующую строку, возможную после применения указанных операций над строкой.

Пример:

Input: s = "11011000"
Output: "11100100"

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

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

2⃣Рекурсивно примените к каждой подстроке этот алгоритм, чтобы найти лексикографически наибольшую строку.

3⃣Сортируйте полученные подстроки в лексикографическом порядке по убыванию и объединяйте их.

😎 Решение:

fun makeLargestSpecial(s: String): String {
    var count = 0
    var i = 0
    val substrs = mutableListOf<String>()
    for (j in s.indices) {
        count += if (s[j] == '1') 1 else -1
        if (count == 0) {
            substrs.add("1" + makeLargestSpecial(s.substring(i + 1, j)) + "0")
            i = j + 1
        }
    }
    return substrs.sortedDescending().joinToString("")
}

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

#hard
Задача: 762. Prime Number of Set Bits in Binary Representation

Если даны два целых числа left и right, верните количество чисел в диапазоне [left, right], имеющих простое число битов в двоичном представлении. Напомним, что число битов в двоичном представлении - это количество единиц, присутствующих в числе 1. Например, 21 в двоичном представлении - это 10101, которое имеет 3 бита.

Пример:

Input: left = 10, right = 15
Output: 5

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

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

2⃣Создайте функцию для проверки, является ли число простым.

3⃣Пройдите через все числа в диапазоне [left, right] и подсчитайте числа, у которых количество битов в двоичном представлении является простым числом.

😎 Решение:

fun countPrimeSetBits(left: Int, right: Int): Int {
    fun countBits(x: Int): Int {
        return x.toString(2).count { it == '1' }
    }
    
    fun isPrime(x: Int): Boolean {
        if (x < 2) return false
        for (i in 2..Math.sqrt(x.toDouble()).toInt()) {
            if (x % i == 0) return false
        }
        return true
    }
    
    var count = 0
    for (num in left..right) {
        if (isPrime(countBits(num))) {
            count++
        }
    }
    return count
}

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

#medium
Задача: 763. Partition Labels

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

Пример:

Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]

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

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

2⃣Пройдите по строке, отслеживая максимальную позицию текущей части.

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

😎 Решение:

fun partitionLabels(s: String): List<Int> {
    val lastPos = IntArray(26)
    for (i in s.indices) {
        lastPos[s[i] - 'a'] = i
    }
    
    val partitions = mutableListOf<Int>()
    var j = 0
    var anchor = 0
    for (i in s.indices) {
        j = maxOf(j, lastPos[s[i] - 'a'])
        if (i == j) {
            partitions.add(i - anchor + 1)
            anchor = i + 1
        }
    }
    return partitions
}

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

На easyoffer 2.0 появится новый раздел:
Задачи с собеседований

🟠Задачи на Алгоритмические, Live-coding и System Design из реальных собеседований
🟠Вероятность встретить ту или иную задачу
🟠Возможность подготовиться к задачам конкретной компании

Есть много сайтов, на которых можно тренироваться решать задачи, но у них у всех одна проблема – сами задачи люди просто выдумывают. На easyoffer 2.0 вы сможете готовиться к live-coding и system design секциям на основе задач из реальных собеседований. Вы можете найдете самые частые задачи и сделаете упор на их решение.

Считаные дни остались до старта краудфандинговой кампании, чтобы ускорить разработку easyoffer 2.0. Все кто, поддержал проект на этом этапе смогу получить 1 год доступа к сайту по цене месячной подписки, а те кто поддержат проект раньше других ито дешевле + получат существенный бонус. Следите за стартом 👉 в этом телеграм канале.

Задача: 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree
Сложность: easy

Даны два бинарных дерева: original и cloned, а также ссылка на узел target в оригинальном дереве.

Дерево cloned является копией оригинального дерева.

Верните ссылку на тот же узел в дереве cloned.

Обратите внимание, что вам не разрешается изменять какое-либо из двух деревьев или узел target, и ответ должен быть ссылкой на узел в дереве cloned.

Пример:

Input: tree = [7,4,3,null,null,6,19], target = 3
Output: 3
Explanation: In all examples the original and cloned trees are shown. The target node is a green node from the original tree. The answer is the yellow node from the cloned tree.

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

1⃣Добавьте корень в очередь.

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

3⃣Верните ссылку на найденный целевой узел.

😎 Решение:

class Solution {
    fun getTargetCopy(original: TreeNode?, cloned: TreeNode?, target: TreeNode?): TreeNode? {
        val queue_o: Queue<TreeNode?> = LinkedList()
        val queue_c: Queue<TreeNode?> = LinkedList()
        
        queue_o.add(original)
        queue_c.add(cloned)
        
        while (queue_o.isNotEmpty()) {
            val node_o = queue_o.poll()
            val node_c = queue_c.poll()
            
            if (node_o == target) {
                return node_c
            }
            
            if (node_o?.left != null) {
                queue_o.add(node_o.left)
                queue_c.add(node_c?.left)
            }
            if (node_o?.right != null) {
                queue_o.add(node_o.right)
                queue_c.add(node_c?.right)
            }
        }
        return null
    }
}

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

Задача: 1036. Escape a Large Maze
Сложность: hard

Имеется сетка размером 1 миллион на 1 миллион на плоскости XY, координаты каждого квадрата сетки - (x, y). Мы начинаем с исходного квадрата = [sx, sy] и хотим достичь цели = [tx, ty]. Существует также массив заблокированных квадратов, где каждый заблокированный[i] = [xi, yi] представляет собой заблокированный квадрат с координатами (xi, yi). Каждый ход мы можем пройти один квадрат на север, восток, юг или запад, если квадрат не находится в массиве заблокированных квадратов. Нам также не разрешается выходить за пределы сетки. Возвращается true тогда и только тогда, когда можно достичь целевого квадрата из исходного квадрата с помощью последовательности правильных ходов.

Пример:

Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false

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

1⃣Обработка входных данных:
Загрузите координаты исходного квадрата sx, sy, целевого квадрата tx, ty и список заблокированных квадратов blocked.

2⃣Проверка простого случая:
Если список blocked пуст, верните true, так как путь не будет заблокирован.
Проверка начальной или целевой клетки:
Если исходная или целевая клетка заблокированы, верните false.

3⃣Поиск пути с использованием BFS или DFS:
Используйте алгоритм поиска в ширину (BFS) или поиска в глубину (DFS) для поиска пути от sx, sy до tx, ty, избегая заблокированных клеток.
Если обнаружен путь, верните true, в противном случае верните false.

😎 Решение:

class Solution {
    fun isEscapePossible(blocked: Array<IntArray>, source: IntArray, target: IntArray): Boolean {
        val blockedSet = blocked.map { it[0] to it[1] }.toSet()
        val source = source[0] to source[1]
        val target = target[0] to target[1]

        if (source in blockedSet || target in blockedSet) return false

        fun bfs(start: Pair<Int, Int>, end: Pair<Int, Int>): Boolean {
            val queue = ArrayDeque<Pair<Int, Int>>()
            queue.add(start)
            val visited = mutableSetOf(start)
            val directions = listOf(0 to 1, 1 to 0, 0 to -1, -1 to 0)
            val maxArea = blocked.size * (blocked.size - 1) / 2

            while (queue.isNotEmpty()) {
                if (visited.size > maxArea) return true
                val (x, y) = queue.removeFirst()
                for ((dx, dy) in directions) {
                    val nx = x + dx
                    val ny = y + dy
                    if (nx in 0 until 1_000_000 && ny in 0 until 1_000_000 && nx to ny !in visited && nx to ny !in blockedSet) {
                        if (nx to ny == end) return true
                        queue.add(nx to ny)
                        visited.add(nx to ny)
                    }
                }
            }
            return false
        }

        return bfs(source, target) && bfs(target, source)
    }
}

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

На easyoffer 2.0 появится:
Тренажер "Реальное собеседование"

🟠 Сценарии вопросов из реального собеседования
🟠Возможность подготовиться к собеседованию в конкретную компанию
🟠Итоговая статистика (прошёл/не прошёл)

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

Уже в начале следующей недели стартует краудфандинг кампания, чтобы ускорить разработку easyoffer 2.0. Все кто, поддержал проект на этом этапе смогу получить 1 год доступа к сайту по цене месячной подписки. Первые 150 донатеров получать особо-выгодную цену и бонус. Следите за стартом 👉 в этом телеграм канале, в нем информация о старте будет опубликована за 6 часов до официального начала.

Задача: 897. Increasing Order Search Tree
Сложность: easy

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

Пример:

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

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

1⃣Выполнить обход дерева в порядке in-order, чтобы получить список узлов.

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

3⃣Вернуть новый корень дерева (первый элемент списка).

😎 Решение:

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

fun increasingBST(root: TreeNode?): TreeNode? {
    val nodes = mutableListOf<TreeNode>()
    
    fun inorder(node: TreeNode?) {
        if (node == null) return
        inorder(node.left)
        nodes.add(node)
        inorder(node.right)
    }
    
    inorder(root)
    
    for (i in 0 until nodes.size - 1) {
        nodes[i].left = null
        nodes[i].right = nodes[i + 1]
    }
    
    nodes.last().left = null
    nodes.last().right = null
    return nodes.first()

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

Задача: 918. Maximum Sum Circular Subarray
Сложность: medium

Если задан круговой целочисленный массив nums длины n, верните максимально возможную сумму непустого подмассива nums. Круговой массив означает, что конец массива соединяется с его началом. Формально, следующий элемент nums[i] равен nums[(i + 1) % n], а предыдущий элемент nums[i] равен nums[(i - 1 + n) % n]. Подмассив может включать каждый элемент фиксированного буфера nums не более одного раза. Формально, для подмассива nums[i], nums[i + 1], ..., nums[j] не существует i <= k1, k2 <= j, при этом k1 % n == k2 % n.

Пример:

Input: nums = [1,-2,3,-2]
Output: 3

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

1⃣Найти стандартную максимальную сумму подмассива с помощью алгоритма Кадане.

2⃣Найти минимальную сумму подмассива с помощью алгоритма Кадане и вычесть ее из общей суммы массива.

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

😎 Решение:

class Solution {
    fun maxSubarraySumCircular(nums: IntArray): Int {
        fun kadane(arr: IntArray): Int {
            var currentSum = arr[0]
            var maxSum = arr[0]
            for (i in 1 until arr.size) {
                currentSum = maxOf(arr[i], currentSum + arr[i])
                maxSum = maxOf(maxSum, currentSum)
            }
            return maxSum
        }

        val maxKadane = kadane(nums)
        val totalSum = nums.sum()
        val minKadane = kadane(nums.map { -it }.toIntArray())

        return maxOf(maxKadane, if (totalSum + minKadane == 0) maxKadane else totalSum + minKadane)
    }
}

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

Задача: 1012. Numbers With Repeated Digits
Сложность: hard

Задав целое число n, верните количество положительных целых чисел в диапазоне [1, n], у которых хотя бы одна цифра повторяется.

Пример:

Input: n = 20
Output: 1

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

1⃣Вычисление всех чисел с уникальными цифрами:
Найдите количество чисел в диапазоне [1, n], у которых все цифры уникальны. Для этого используйте перебор всех чисел и проверку уникальности цифр.

2⃣Вычисление всех чисел в диапазоне [1, n]:
Это значение равно n, поскольку это количество всех чисел от 1 до n включительно.

3⃣Вычисление результата:
Вычтите количество чисел с уникальными цифрами из общего количества чисел, чтобы получить количество чисел с повторяющимися цифрами.

😎 Решение:

class Solution {
    fun numDupDigitsAtMostN(n: Int): Int {
        fun countUniqueDigitNumbers(x: Int): Int {
            val s = x.toString()
            val n = s.length
            var res = (1 until n).sumBy { 9 * permutation(9, it - 1) }
            val used = mutableSetOf<Int>()
            for (i in s.indices) {
                for (j in (if (i == 0) 1 else 0) until (s[i] - '0')) {
                    if (!used.contains(j)) {
                        res += permutation(9 - i, n - i - 1)
                    }
                }
                if (used.contains(s[i] - '0' - '0')) {
                    break
                }
                used.add(s[i] - '0' - '0')
            }
            if (used.size == n) res += 1
            return res
        }

        fun permutation(m: Int, n: Int): Int {
            return if (n == 0) 1 else permutation(m, n - 1) * (m - n + 1)
        }

        return n - countUniqueDigitNumbers(n)
    }
}

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

Задача: 422. Valid Word Square
Сложность: easy

Дан массив строк words, верните true, если он образует правильный квадрат слов.

Последовательность строк образует правильный квадрат слов, если k-я строка и k-й столбец читаются одинаково, где 0 <= k < max(numRows, numColumns).

Пример:

Input: words = ["abcd","bnrt","crmy","dtye"]
Output: true
Explanation:
The 1st row and 1st column both read "abcd".
The 2nd row and 2nd column both read "bnrt".
The 3rd row and 3rd column both read "crmy".
The 4th row and 4th column both read "dtye".
Therefore, it is a valid word square.

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

1⃣Инициализируйте переменные: cols для максимальной длины слов в массиве, rows для количества строк в массиве words, и пустой массив newWords для хранения новых слов, представленных каждым столбцом.

2⃣Итерация по массиву words, определение максимальной длины слова для cols, проверка, что количество строк равно количеству столбцов. Если условие не выполняется, возвращаем false.

3⃣Для каждого столбца col от 0 до cols - 1, формируем строку newWord из символов на позиции (row, col) для каждой строки. Сохраняем newWord в массиве newWords. В конце, если newWords и words равны, возвращаем true, иначе false.

😎 Решение:

class Solution {
    fun validWordSquare(words: List<String>): Boolean {
        var cols = 0
        val rows = words.size
        val newWords = mutableListOf<String>()
        
        for (word in words) {
            cols = maxOf(cols, word.length)
        }

        if (cols != words[0].length || rows != cols) {
            return false
        }

        for (col in 0 until cols) {
            var newWord = ""
            for (row in 0 until rows) {
                if (col < words[row].length) {
                    newWord += words[row][col]
                }
            }
            newWords.add(newWord)
        }

        return words == newWords
    }
}

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

На easyoffer 2.0 появится:
База тестовых заданий

🟠Тестовые задания для разных грейдов
🟠Фильтрация тестовых заданий по технологиям и компаниям

Когда я только начинал учиться на программиста, я постоянно выдумывал себе задачи для практики и тратил на это много времени. Но только в момент поиска работы я столкнулся с тестовыми заданиями, и понял насколько круто они прокачивают навыки. Нужно было еще на этапе обучения пробовать их делать. Все компании стараются составить тестовое задание "под себя", это дает большой выбор в тематике задач и технологий. На easyoffer 2.0 вы сможете отфильтровать тестовые задания по навыкам/грейдам и найти те, что подходят лично вам для практики.

В течение 1-2 дней я объявлю о краудфандинг кампании, чтобы ускорить разработку easyoffer 2.0. Все кто, поддержал проект на этом этапе смогу получить 1 год доступа к сайту по цене месячной подписки и смогут попасть на закрытое бета-тестирование. А первые 150 донатеров получать особо-выгодную цену и бонус.

🚀 Следите за стартом 👉 в этом телеграм канале, в нем информация о старте будет опубликована за 6 часов до официального начала.

Задача: 856. Score of Parentheses
Сложность: medium

Дана строка s, состоящая из сбалансированных скобок, верните счёт строки.

Счёт сбалансированной строки скобок основывается на следующих правилах:

"()" имеет счёт 1.
AB имеет счёт A + B, где A и B — сбалансированные строки скобок.
(A) имеет счёт 2 * A, где A — сбалансированная строка скобок.

Пример:

Input: s = "()"
Output: 1

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

1⃣Назовём сбалансированную строку примитивной, если её нельзя разделить на две непустые сбалансированные строки.

2⃣Отслеживая баланс (количество открывающих скобок минус количество закрывающих скобок), мы можем разделить строку S на примитивные подстроки S = P_1 + P_2 + ... + P_n. Тогда, по определению, score(S) = score(P_1) + score(P_2) + ... + score(P_n).

3⃣Для каждой примитивной подстроки (S[i], S[i+1], ..., S[k]), если длина строки равна 2, то её счёт равен 1. В противном случае, счёт равен удвоенному счёту подстроки (S[i+1], S[i+2], ..., S[k-1]).

😎 Решение:

class Solution {
    fun scoreOfParentheses(S: String): Int {
        return F(S, 0, S.length)
    }

    private fun F(S: String, i: Int, j: Int): Int {
        var ans = 0
        var bal = 0

        for (k in i until j) {
            bal += if (S[k] == '(') 1 else -1
            if (bal == 0) {
                ans += if (k - i == 1) 1 else 2 * F(S, i + 1, k)
                i = k + 1
            }
        }

        return ans
    }
}

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

Задача: 1100. Find K-Length Substrings With No Repeated Characters
Сложность: medium

Дана строка s и целое число k. Верните количество подстрок в s длиной k, которые не содержат повторяющихся символов.

Пример:

Input: s = "havefunonleetcode", k = 5
Output: 6
Explanation: There are 6 substrings they are: 'havef','avefu','vefun','efuno','etcod','tcode'.

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

1⃣Если k > 26, верните 0, так как не может быть строки длиной более 26 символов с уникальными символами. Для остальных случаев, где k <= 26, проверьте каждую подстроку длиной k на наличие повторяющихся символов.

2⃣Итерация по строке s от индекса 0 до n - k (включительно), где n - длина строки s:
Для каждого индекса i:
Инициализируйте флаг isUnique как true и массив частот размером 26 для подсчета частот каждого символа.
Итерируйте следующие k символов и увеличивайте частоту каждого встреченного символа в массиве частот.
Если частота любого символа становится больше 1, установите isUnique в false и прекратите итерацию.
Если после итерации по k символам флаг isUnique все еще равен true, увеличьте счетчик ответов на 1.

3⃣Верните количество подстрок без повторяющихся символов после итерации по всем индексам от 0 до n - k.

😎 Решение:

class Solution {
    fun numKLenSubstrNoRepeats(s: String, k: Int): Int {
        if (k > 26) return 0
        
        val n = s.length
        var answer = 0
        
        for (i in 0..n - k) {
            val freq = IntArray(26)
            var isUnique = true
            
            for (j in i until i + k) {
                freq[s[j] - 'a']++
                
                if (freq[s[j] - 'a'] > 1) {
                    isUnique = false
                    break
                }
            }
            
            if (isUnique) answer++
        }
        
        return answer
    }
}

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

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

Дан корень бинарного дерева. Верните то же дерево, в котором удалены все поддеревья (данного дерева), не содержащие 1.

Поддерево узла node - это сам узел node и все узлы, являющиеся потомками node.

Пример:

Input: root = [1,null,0,0,1]
Output: [1,null,0,null,1]
Explanation: 
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.

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

1⃣Используем функцию containsOne(node), которая сообщает, содержит ли поддерево в данном узле единицу, и обрезает все поддеревья, не содержащие единицу.

2⃣Например, если поддерево node.left не содержит единицу, то мы должны обрезать его через node.left = null.

3⃣Также нужно проверить родительский узел. Например, если дерево состоит из одного узла 0, то ответом будет пустое дерево.

😎 Решение:

class Solution {
    fun pruneTree(root: TreeNode?): TreeNode? {
        return if (containsOne(root)) root else null
    }

    private fun containsOne(node: TreeNode?): Boolean {
        if (node == null) return false

        val leftContainsOne = containsOne(node.left)
        val rightContainsOne = containsOne(node.right)

        if (!leftContainsOne) node.left = null
        if (!rightContainsOne) node.right = null

        return node.`val` == 1 || leftContainsOne || rightContainsOne
    }
}

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