Задача: 200. Number of Islands
Сложность: medium

Дана двумерная бинарная сетка размером m x n, представляющая карту из '1' (земля) и '0' (вода). Верните количество островов.

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

Пример:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

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

1️⃣Линейно просканируйте двумерную карту, если узел содержит '1', то это корневой узел, который запускает поиск в глубину (DFS).

2️⃣Во время выполнения DFS каждый посещённый узел следует установить в '0', чтобы пометить его как посещённый.

3️⃣Подсчитайте количество корневых узлов, запускающих DFS. Это количество будет равно количеству островов, так как каждый DFS, начинающийся с какого-либо корня, идентифицирует остров.

😎 Решение:

class Solution:
    def numIslands(self, grid):
        if not grid:
            return 0

        num_islands = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == "1":
                    self.dfs(grid, i, j)
                    num_islands += 1

        return num_islands

    def dfs(self, grid, r, c):
        if (
            r < 0
            or c < 0
            or r >= len(grid)
            or c >= len(grid[0])
            or grid[r][c] != "1"
        ):
            return
        grid[r][c] = "0"

        self.dfs(grid, r - 1, c)
        self.dfs(grid, r + 1, c)
        self.dfs(grid, r, c - 1)
        self.dfs(grid, r, c + 1)

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

Задача: 567. Permutation in String
Сложность: medium

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

Другими словами, верните true, если одна из перестановок s1 является подстрокой s2.

Пример:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

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

1⃣Создать массив для подсчета символов в строке s1. Затем создать аналогичный массив для первых len(s1) символов строки s2.

2⃣Использовать скользящее окно для перемещения по строке s2. Для каждой позиции окна обновлять массив подсчета символов и сравнивать его с массивом для строки s1.

3⃣Если массивы совпадают на любом этапе, вернуть true. Если окно достигает конца строки s2 и совпадений не найдено, вернуть false.

😎 Решение:

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        from collections import Counter
        
        s1Count = Counter(s1)
        s2Count = Counter(s2[:len(s1)])
        
        if s1Count == s2Count:
            return True
        
        for i in range(len(s1), len(s2)):
            s2Count[s2[i]] += 1
            s2Count[s2[i - len(s1)]] -= 1
            if s2Count[s2[i - len(s1)]] == 0:
                del s2Count[s2[i - len(s1)]]
            if s1Count == s2Count:
                return True
        
        return False

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

Задача: 1051. Height Checker
Сложность: easy

Школа пытается сделать ежегодную фотографию всех учеников. Учеников просят встать в одну шеренгу в неубывающем порядке по росту. Пусть этот порядок представлен целочисленным массивом expected, где expected[i] - ожидаемый рост i-го студента в очереди. Вам дан целочисленный массив heights, представляющий текущий порядок, в котором стоят студенты. Каждый heights[i] - это высота i-го студента в очереди (с индексом 0). Верните количество индексов, в которых heights[i] != expected[i].

Пример:

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

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

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

2⃣Пройди по обоим массивам и сравни элементы.

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

😎 Решение:

def heightChecker(heights):
    expected = sorted(heights)
    count = 0
    for i in range(len(heights)):
        if heights[i] != expected[i]:
            count += 1
    return count

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

Задача: 397. Integer Replacement
Сложность: medium

К положительному целому числу n можно применить одну из следующих операций: если n четное, замените n на n / 2. если n нечетное, замените n на n + 1 или n - 1. верните минимальное количество операций, необходимых для того, чтобы n стало 1.

Пример:

Input: n = 8
Output: 3
Explanation: 8 -> 4 -> 2 -> 1

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

1⃣Начните с данного числа n и выполните одну из следующих операций:
Если n четное, замените n на n / 2.
Если n нечетное, замените n на n + 1 или n - 1.

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

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

😎 Решение:

class Solution:
    def integerReplacement(self, n: int) -> int:
        def helper(n, memo):
            if n == 1:
                return 0
            if n in memo:
                return memo[n]
            
            if n % 2 == 0:
                memo[n] = 1 + helper(n // 2, memo)
            else:
                memo[n] = 1 + min(helper(n + 1, memo), helper(n - 1, memo))
                
            return memo[n]
        
        return helper(n, {})

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

Задача: 979. Distribute Coins in Binary Tree
Сложность: medium

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

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

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

Пример:

Input: root = [3,0,0]
Output: 2
Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.

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

1⃣Инициализация и определение рекурсивной функции. Инициализируйте переменную moves = 0. Определите рекурсивную функцию dfs, которая считает количество перемещений монет. Базовый случай: если текущий узел равен null, верните 0.

2⃣Рекурсивный обход дерева. Внутри dfs вызовите dfs для левого и правого поддеревьев, чтобы получить количество монет, которые нужно переместить в каждом поддереве. Вычислите количество перемещений для текущего узла: добавьте абсолютные значения перемещаемых монет в moves.

3⃣Возвращение результата. Верните количество монет, которые текущий узел может передать своему родителю: значение узла плюс количество монет в левом и правом поддеревьях минус 1. Вызовите dfs от корня дерева и верните moves.

😎 Решение:

class Solution:
    def distributeCoins(self, root: Optional[TreeNode]) -> int:
        self.moves = 0
        self.dfs(root)
        return self.moves

    def dfs(self, current: Optional[TreeNode]) -> int:
        if not current:
            return 0
        leftCoins = self.dfs(current.left)
        rightCoins = self.dfs(current.right)
        self.moves += abs(leftCoins) + abs(rightCoins)
        return current.val - 1 + leftCoins + rightCoins

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

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

Дано целое число num. Повторно складывайте все его цифры, пока результат не станет однозначным, и верните его.

Пример:

Input: num = 38
Output: 2
Explanation: The process is
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2 
Since 2 has only one digit, return it.

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

1️⃣Инициализируйте переменную digital_root значением 0.

2️⃣В цикле, пока num больше 0:
Добавьте к digital_root последнюю цифру num.
Уменьшите num, удалив последнюю цифру.
Если num равно 0 и digital_root больше 9, присвойте num значение digital_root и сбросьте digital_root в 0.

3️⃣Верните значение digital_root.

😎 Решение:

class Solution:
    def addDigits(self, num: int) -> int:
        digital_root = 0
        while num > 0:
            digital_root += num % 10
            num //= 10
            if num == 0 and digital_root > 9:
                num = digital_root
                digital_root = 0
        return digital_root

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

Задача: 1663. Smallest String With A Given Numeric Value
Сложность: 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:
    def getSmallestString(self, n: int, k: int) -> str:
        result = ['a'] * n
        
        for position in range(n):
            positionsLeft = (n - position - 1)
            if k > positionsLeft * 26:
                add = k - (positionsLeft * 26)
                result[position] = chr(ord('a') + add - 1)
                k -= add
            else:
                k -= 1
        
        return ''.join(result

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

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

Сообщение, содержащее буквы от A до Z, можно закодировать в числа с использованием следующего соответствия:
- 'A' -> "1"
- 'B' -> "2"
- ...
- 'Z' -> "26"
Для декодирования закодированного сообщения все цифры должны быть сгруппированы и затем отображены обратно в буквы с использованием обратного соответствия (существует несколько способов). Например, "11106" можно представить как:
- "AAJF" с группировкой (1 1 10 6)
- "KJF" с группировкой (11 10 6)
Обратите внимание, что группировка (1 11 06) недопустима, потому что "06" не может быть преобразовано в 'F', так как "6" отличается от "06". Для данной строки s, содержащей только цифры, верните количество способов декодирования. Тестовые случаи сформированы таким образом, что ответ укладывается в 32-битное целое число.

Пример:

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(object):
    def valid(self, s, start, length):
        return length == 1 or (
            s[start] != "0"
            and (length < 3 or s[start : start + length] <= "255")
        )

    def helper(self, s, startIndex, dots, ans):
        remainingLength = len(s) - startIndex
        remainingNumberOfIntegers = 4 - len(dots)
        if (
            remainingLength > remainingNumberOfIntegers * 3
            or remainingLength < remainingNumberOfIntegers
        ):
            return
        if len(dots) == 3:
            if self.valid(s, startIndex, remainingLength):
                temp = ""
                last = 0
                for dot in dots:
                    temp += s[last : last + dot] + "."
                    last += dot
                temp += s[startIndex:]
                ans.append(temp)
            return
        for curPos in range(1, min(4, remainingLength + 1)):
            dots.append(curPos)
            if self.valid(s, startIndex, curPos):
                self.helper(s, startIndex + curPos, dots, ans)
            dots.pop()

    def restoreIpAddresses(self, s):
        answer = []
        self.helper(s, 0, [], answer)
        return answer

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

Задача: 846. Hand of Straights
Сложность: medium

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

Дан целочисленный массив hand, где hand[i] — это значение, написанное на i-й карте, и целое число groupSize. Верните true, если она может переставить карты, или false в противном случае.

Пример:

Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output: true
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]

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

1⃣Проверьте, делится ли длина массива hand на groupSize. Если нет, верните false.

2⃣Создайте карту cardCount для хранения количества каждой карты в массиве hand.

3⃣Итерируйте по массиву hand и обновляйте карту cardCount. Затем итерируйте снова для создания групп:
Найдите начальную карту startCard для потенциальной последовательности, уменьшая startCard, пока не найдёте карту, которая отсутствует в карте cardCount.
Попробуйте сформировать последовательность из groupSize карт, начиная с startCard. Если какая-либо карта в потенциальной последовательности отсутствует в карте cardCount, верните false.
Если последовательность можно сформировать, уменьшите количество каждой карты в последовательности в карте cardCount.

😎 Решение:

from collections import Counter

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        if len(hand) % groupSize != 0:
            return False

        cardCount = Counter(hand)
        for card in sorted(hand):
            if cardCount[card] == 0:
                continue

            for nextCard in range(card, card + groupSize):
                if cardCount[nextCard] == 0:
                    return False
                cardCount[nextCard] -= 1

        return True

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

Задача: 1166. Design File System
Сложность: medium

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

Формат пути - это одна или несколько конкатенированных строк в форме: /, за которой следует одна или несколько строчных английских букв. Например, "/leetcode" и "/leetcode/problems" - допустимые пути, в то время как пустая строка "" и "/" не допустимы.

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

- bool createPath(string path, int value) создает новый путь и связывает с ним значение, если это возможно, и возвращает true. Возвращает false, если путь уже существует или его родительский путь не существует.
- int get(string path) возвращает значение, связанное с путем, или возвращает -1, если путь не существует.

Пример:

Input: 
["FileSystem","createPath","get"]
[[],["/a",1],["/a"]]
Output: 
[null,true,1]
Explanation: 
FileSystem fileSystem = new FileSystem();

fileSystem.createPath("/a", 1); // return true
fileSystem.get("/a"); // return 1

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

1⃣Инициализируйте словарь или HashMap под названием paths, который будет использовать ключ в виде пути, переданного в нашу функцию create, и значение, переданное этой функции.

2⃣Для функции create выполняем три шага. Сначала выполняем базовую проверку валидности пути. Проверяем, является ли путь пустым, "/" или если путь уже существует в нашем словаре. Если любое из этих условий выполнено, просто возвращаем false. Затем получаем родительский путь предоставленного пути и проверяем его наличие в словаре. Если родительский путь не существует, возвращаем false, иначе продолжаем.

3⃣Наконец, вставляем предоставленный путь и значение в словарь и возвращаем true. Для функции get просто возвращаем значение по умолчанию -1, если путь не существует в словаре. В противном случае возвращаем фактическое значение.

😎 Решение:

class FileSystem:

    def __init__(self):
        self.paths = {}

    def createPath(self, path: str, value: int) -> bool:
        if not path or (len(path) == 1 and path == "/") or path in self.paths:
            return False
        
        delim_index = path.rfind("/")
        parent = path[:delim_index]
        
        if len(parent) > 1 and parent not in self.paths:
            return False
        
        self.paths[path] = value
        return True

    def get(self, path: str) -> int:
        return self.paths.get(path, -1)

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

Задача: 594. Longest Harmonious Subsequence
Сложность: easy

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

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

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

Пример:

Input: nums = [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

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

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

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

3⃣Верните максимальную длину гармоничной подпоследовательности.

😎 Решение:

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        count = {}
        res = 0
        
        for num in nums:
            count[num] = count.get(num, 0) + 1
            if num + 1 in count:
                res = max(res, count[num] + count[num + 1])
            if num - 1 in count:
                res = max(res, count[num] + count[num - 1])
        
        return res

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

Задача: 892. Surface Area of 3D Shapes
Сложность: easy

Вам дана сетка n x n, на которой вы разместили несколько кубиков 1 x 1 x 1. Каждое значение v = grid[i][j] представляет собой башню из v кубиков, размещенных на вершине ячейки (i, j). После размещения кубиков вы решили склеить все непосредственно прилегающие кубики друг с другом, образовав несколько неправильных 3D-фигур. Верните общую площадь поверхности получившихся фигур. Примечание: нижняя грань каждой фигуры учитывается в площади ее поверхности.

Пример:

Input: grid = [[1,2],[3,4]]
Output: 34

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

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

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

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

😎 Решение:

def surfaceArea(grid):
    n = len(grid)
    area = 0
    for i in range(n):
        for j in range(n):
            if grid[i][j] > 0:
                area += (grid[i][j] * 4) + 2
            if i > 0:
                area -= min(grid[i][j], grid[i-1][j]) * 2
            if j > 0:
                area -= min(gri

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

Задача: 215. Kth Largest Element in an Array
Сложность: medium

Дан целочисленный массив nums и целое число k. Верните k-й наибольший элемент в массиве.

Обратите внимание, что это k-й наибольший элемент в отсортированном порядке, а не k-й уникальный элемент.

Пример:

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

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

1️⃣ Отсортируйте массив в порядке убывания:
Используйте стандартную функцию сортировки для сортировки элементов массива nums в порядке убывания. В этом случае самый большой элемент будет первым в массиве, второй по величине - вторым и так далее.

2️⃣ Найдите k-й по величине элемент:
После сортировки просто верните элемент, который стоит на позиции k-1 (учитывая, что индексация в массиве начинается с 0).

3️⃣ Верните результат:
Возвратите найденное значение как результат.

😎 Решение:

class Solution:
    def findKthLargest(self, nums, k):
        nums.sort(reverse=True)
        return nums[k - 1]

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

Задача: 951. Flip Equivalent Binary Trees
Сложность: medium

Для бинарного дерева T мы можем определить операцию переворота следующим образом: выбираем любой узел и меняем местами левое и правое дочерние поддеревья. Бинарное дерево X эквивалентно бинарному дереву Y тогда и только тогда, когда мы можем сделать X равным Y после некоторого количества операций переворота. Учитывая корни двух бинарных деревьев root1 и root2, верните true, если эти два дерева эквивалентны перевороту, или false в противном случае.

Пример:

Input: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
Output: true

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

1⃣Если оба дерева пусты, они эквивалентны, вернуть true. Если одно дерево пустое, а другое нет, они не эквивалентны, вернуть false.

2⃣Если значения корней деревьев не совпадают, вернуть false.
Проверить два условия:
Левое поддерево первого дерева эквивалентно левому поддереву второго дерева и правое поддерево первого дерева эквивалентно правому поддереву второго дерева.
Левое поддерево первого дерева эквивалентно правому поддереву второго дерева и правое поддерево первого дерева эквивалентно левому поддереву второго дерева.

3⃣Вернуть true, если выполняется хотя бы одно из этих условий.

😎 Решение:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def flipEquiv(root1, root2):
    if not root1 and not root2:
        return True
    if not root1 or not root2 or root1.val != root2.val:
        return False
    
    return (flipEquiv(root1.left, root2.left) and flipEquiv(root1.right, root2.right)) or \
           (flipEquiv(root1.left, root2.right) and flipEquiv(root1.right, root2.left))

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

Задача: 436. Find Right Interval
Сложность: medium

Дан массив интервалов, где intervals[i] = [starti, endi] и каждый starti уникален.

Правый интервал для интервала i - это интервал j, такой что startj >= endi и startj минимален. Обратите внимание, что i может быть равен j.

Верните массив индексов правых интервалов для каждого интервала i. Если правого интервала для интервала i не существует, то поставьте -1 в индекс i.

Пример:

Input: intervals = [[1,2]]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.

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

1⃣Интуиция за этим подходом такова: если мы будем поддерживать два массива - intervals, который отсортирован по начальным точкам, и endIntervals, который отсортирован по конечным точкам. Когда мы выбираем первый интервал (или, скажем, i-ый интервал) из массива endIntervals, мы можем определить подходящий интервал, удовлетворяющий критериям правого интервала, просматривая интервалы в массиве intervals слева направо, так как массив intervals отсортирован по начальным точкам. Допустим, индекс выбранного элемента из массива intervals окажется j.

2⃣Теперь, когда мы выбираем следующий интервал (скажем, (i+1)-ый интервал) из массива endIntervals, нам не нужно начинать сканирование массива intervals с первого индекса. Вместо этого мы можем начать прямо с индекса j, где мы остановились в последний раз в массиве intervals. Это потому, что конечная точка, соответствующая endIntervals[i+1], больше, чем та, которая соответствует endIntervals[i], и ни один из интервалов из intervals[k], таких что 0 < k < j, не удовлетворяет критериям правого соседа с endIntervals[i], а значит, и с endIntervals[i+1] тоже.

3⃣Если в какой-то момент мы достигнем конца массива, т.е. j = intervals.length, и ни один элемент, удовлетворяющий критериям правого интервала, не будет доступен в массиве intervals, мы ставим -1 в соответствующую запись res. То же самое касается всех оставшихся элементов массива endIntervals, конечные точки которых даже больше, чем у предыдущего интервала. Также мы используем хеш-таблицу hash изначально, чтобы сохранить индексы, соответствующие интервалам, даже после сортировки.

😎 Решение:

class Solution:
    def findRightInterval(self, intervals):
        endIntervals = intervals[:]
        hash = {tuple(interval): i for i, interval in enumerate(intervals)}
        intervals.sort(key=lambda x: x[0])
        endIntervals.sort(key=lambda x: x[1])
        j = 0
        res = [-1] * len(intervals)
        for i in range(len(endIntervals)):
            while j < len(intervals) and intervals[j][0] < endIntervals[i][1]:
                j += 1
            res[hash[tuple(endIntervals[i])]] = -1 if j == len(intervals) else hash[tuple(intervals[j])]
        return res

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

Задача: 320. Generalized Abbreviation
Сложность: medium

Обобщенная аббревиатура слова может быть построена путем замены любых неперекрывающихся и несмежных подстрок на их соответствующие длины.

Например, "abcde" можно сократить следующим образом:

"a3e" ("bcd" заменено на "3")
"1bcd1" ("a" и "e" заменены на "1")
"5" ("abcde" заменено на "5")
"abcde" (без замены подстрок)
Однако следующие аббревиатуры недействительны:

"23" ("ab" заменено на "2" и "cde" заменено на "3") недействительно, так как выбранные подстроки смежные.
"22de" ("ab" заменено на "2" и "bc" заменено на "2") недействительно, так как выбранные подстроки перекрываются.
Дано слово word, верните список всех возможных обобщенных аббревиатур слова. Верните ответ в любом порядке.

Пример:

Input: word = "a"
Output: ["1","a"]

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

1⃣Создание битовых масок
Каждая аббревиатура имеет одно к одному соответствие с n-битным двоичным числом x, где n - длина слова. Используйте эти числа в качестве чертежей для построения соответствующих аббревиатур.

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

3⃣Перебор всех комбинаций
Для каждого числа от 0 до 2^n - 1 используйте его битовое представление для создания соответствующей аббревиатуры. Сканируйте число x побитово, извлекая его последний бит с помощью b = x & 1 и сдвигая x вправо на один бит x >>= 1.

😎 Решение:

class Solution:
    def generateAbbreviations(self, word: str):
        def abbr(word, x):
            builder = []
            k = 0
            for i in range(len(word)):
                if x & 1 == 0:
                    if k != 0:
                        builder.append(str(k))
                        k = 0
                    builder.append(word[i])
                else:
                    k += 1
                x >>= 1
            if k != 0:
                builder.append(str(k))
            return ''.join(builder)
        
        ans = []
        for x in range(1 << len(word)):
            ans.append(abbr(word, x))
        return ans

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

Завтра последний день!

Успей купить пожизненный easyoffer PRO - по цене 1 года

Покупаешь один раз — пользуешься всю жизнь.

👉 Акция до 31 марта: https://easyoffer.ru/pro

Задача: 683. K Empty Slots
Сложность: hard

У вас есть n лампочек, расположенных в ряд и пронумерованных от 1 до n. Изначально все лампочки выключены. Каждый день мы включаем ровно одну лампочку, и через n дней все лампочки будут включены.

Вам дан массив bulbs длины n, где bulbs[i] = x означает, что в (i+1)-й день мы включим лампочку в позиции x, где i индексируется с 0, а x индексируется с 1.

Дано целое число k, верните минимальный номер дня, такой что существует две включенные лампочки, между которыми ровно k выключенных лампочек. Если такого дня не существует, верните -1.

Пример:

Input: bulbs = [1,3,2], k = 1
Output: 2
Explanation:
On the first day: bulbs[0] = 1, first bulb is turned on: [1,0,0]
On the second day: bulbs[1] = 3, third bulb is turned on: [1,0,1]
On the third day: bulbs[2] = 2, second bulb is turned on: [1,1,1]
We return 2 because on the second day, there were two on bulbs with one off bulb between them.

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

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

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

3⃣Если какой-то сосед удовлетворяет условию (ровно k выключенных лампочек между двумя включенными), значит, условие впервые произошло в этот день, и вы можете вернуть номер этого дня. Если такого дня не существует после включения всех лампочек, верните -1.

😎 Решение:

from sortedcontainers import SortedList

class Solution:
    def kEmptySlots(self, flowers: List[int], k: int) -> int:
        active = SortedList()
        day = 0
        
        for flower in flowers:
            day += 1
            active.add(flower)
            idx = active.index(flower)
            
            if idx > 0 and flower - active[idx - 1] - 1 == k:
                return day
            if idx < len(active) - 1 and active[idx + 1] - flower - 1 == k:
                return day
        
        return -1

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

Задача: 941. Valid Mountain Array
Сложность: easy

Задав массив целых чисел arr, верните true тогда и только тогда, когда он является допустимым горным массивом. Напомним, что arr является горным массивом тогда и только тогда, когда: arr.length >= 3 Существует некоторое i с 0 < i < arr.length - 1 такое, что: arr[0] < arr[1] < ... < arr[i - 1] < arr[i] arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Пример:

Input: arr = [2,1]
Output: false

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

1⃣Убедиться, что длина массива не меньше 3.

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

3⃣Вернуть true, если оба условия выполнены, иначе вернуть false.

😎 Решение:

def validMountainArray(arr):
    if len(arr) < 3:
        return False
    
    i = 1
    while i < len(arr) and arr[i] > arr[i - 1]:
        i += 1
    
    if i == 1 or i == len(arr):
        return False
    
    while i < len(arr) and arr[i] < arr[i - 1]:
        i += 1
    
    return i == len(arr)

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

Задача: 1263. Minimum Moves to Move a Box to Their Target Location
Сложность: hard

Кладовщик - это игра, в которой игрок перемещает коробки по складу, пытаясь доставить их в целевые места. Игра представлена сеткой символов m x n, где каждый элемент - это стена, пол или коробка. Ваша задача - переместить коробку "B" в целевую позицию "T" по следующим правилам: символ "S" представляет игрока. Игрок может перемещаться вверх, вниз, влево, вправо по сетке, если это пол (пустая клетка). Символ '.' обозначает пол, что означает свободную клетку для ходьбы. Символ '#' обозначает стену, что означает препятствие (туда невозможно пройти). В сетке есть только одна коробка 'B' и одна целевая клетка 'T'. Коробку можно переместить на соседнюю свободную клетку, стоя рядом с коробкой, а затем двигаясь в направлении коробки. Это толчок. Игрок не может пройти через коробку. Верните минимальное количество толчков, чтобы переместить коробку к цели. Если нет возможности добраться до цели, верните -1.

Пример:

Input: grid = [["#","#","#","#","#","#"],
               ["#","T","#","#","#","#"],
               ["#",".",".","B",".","#"],
               ["#",".","#","#",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: 3

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

1⃣Выполните поиск в ширину (BFS) для всех возможных позиций игрока и коробки, отслеживая количество толчков.

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

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

😎 Решение:

from collections import deque

def minPushBox(grid):
    m, n = len(grid), len(grid[0])
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    def valid(x, y):
        return 0 <= x < m and 0 <= y < n and grid[x][y] != '#'
    
    def bfs(start):
        queue = deque([start])
        visited = set([start])
        while queue:
            px, py, bx, by, pushes = queue.popleft()
            if (bx, by) == target:
                return pushes
            for dx, dy in directions:
                npx, npy = px + dx, py + dy
                if valid(npx, npy) and (npx, npy, bx, by, pushes) not in visited:
                    if (npx, npy) == (bx, by):
                        nbx, nby = bx + dx, by + dy
                        if valid(nbx, nby) and (npx, npy, nbx, nby, pushes + 1) not in visited:
                            queue.append((npx, npy, nbx, nby, pushes + 1))
                            visited.add((npx, npy, nbx, nby, pushes + 1))
                    else:
                        queue.append((npx, npy, bx, by, pushes))
                        visited.add((npx, npy, bx, by, pushes))
        return -1
    
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 'S':
                player = (i, j)
            elif grid[i][j] == 'B':
                box = (i, j)
            elif grid[i][j] == 'T':
                target = (i, j)
    
    return bfs((*player, *box, 0))

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

Задача: 398. Random Pick Index
Сложность: medium

Из целочисленного массива nums с возможными дубликатами случайным образом выведите индекс заданного целевого числа. Можно предположить, что заданное целевое число должно существовать в массиве. Реализация класса Solution: Solution(int[] nums) Инициализирует объект с массивом nums. int pick(int target) Выбирает случайный индекс i из nums, где nums[i] == target. Если существует несколько допустимых i, то каждый индекс должен иметь равную вероятность возврата.

Пример:

Input
["Solution", "pick", "pick", "pick"]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
Output
[null, 4, 0, 2]

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

1⃣Инициализируйте объект с массивом nums. Сохраните этот массив для дальнейшего использования.

2⃣Реализуйте метод pick(target), который выбирает случайный индекс i из массива nums, где nums[i] равен target. Если таких индексов несколько, каждый из них должен иметь равную вероятность быть выбранным.

3⃣Для реализации метода pick используйте алгоритм reservoir sampling для выбора случайного индекса.

😎 Решение:

import random

class Solution:
    def __init__(self, nums: List[int]):
        self.nums = nums

    def pick(self, target: int) -> int:
        count = 0
        result = -1
        for i, num in enumerate(self.nums):
            if num == target:
                count += 1
                if random.randint(1, count) == count:
                    result = i
        return result

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