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

Переверните биты заданного 32-битного беззнакового целого числа.

Пример:

Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.
Example 2:

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

1️⃣Итерируем по байтам целого числа, используя побитовую операцию И (n & 0xff) с маской 11111111, чтобы извлечь крайний правый байт числа.

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

3️⃣В функции reverseByte(byte) используем технику мемоизации, которая сохраняет результат функции и возвращает его непосредственно при последующих вызовах с тем же входным значением. Мемоизация — это компромисс между использованием памяти и объемом вычислений.

😎 Решение:

import functools
class Solution:
    def reverseBits(self, n: int) -> int:
        ret, power = 0, 24
        while n:
            ret += self.reverseByte(n & 0xFF) << power
            n = n >> 8
            power -= 8
        return ret
    @functools.lru_cache(maxsize=256)
    def reverseByte(self, byte):
        return (byte * 0x0202020202 & 0x010884422010) % 1023

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

Задача: 995. Minimum Number of K Consecutive Bit Flips
Сложность: hard

Дан бинарный массив nums и целое число k.

Операция переворота k-бит заключается в выборе подмассива длиной k из nums и одновременном изменении каждого 0 в подмассиве на 1 и каждого 1 в подмассиве на 0.

Верните минимальное количество k-битных переворотов, необходимых для того, чтобы в массиве не осталось 0. Если это невозможно, верните -1.

Подмассив - это непрерывная часть массива.

Пример:

Input: nums = [0,1,0], k = 1
Output: 2
Explanation: Flip nums[0], then flip nums[2].

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

1⃣Инициализация переменных:
Создайте массив flip, чтобы отслеживать, сколько раз был перевернут каждый элемент.
Инициализируйте flips для отслеживания количества текущих переворотов.

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

3⃣Проверка возможности выполнения задачи:
Если количество переворотов больше длины массива, верните -1.

😎 Решение:

class Solution:
    def minKBitFlips(self, nums: List[int], k: int) -> int:
        n = len(nums)
        flip = 0
        flips = 0
        flip_queue = [0] * n
        
        for i in range(n):
            if i >= k:
                flip ^= flip_queue[i - k]
            if nums[i] == flip:
                if i + k > n:
                    return -1
                flips += 1
                flip ^= 1
                flip_queue[i] = 1
        
        return flips

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

Задача: 999. Available Captures for Rook
Сложность: easy

Вам дана матрица 8 x 8, изображающая шахматную доску. На ней есть ровно одна белая ладья, представленная символом "R", некоторое количество белых слонов "B" и некоторое количество черных пешек "p". Пустые клетки обозначаются символом '.'. Ладья может перемещаться на любое количество клеток по горизонтали или вертикали (вверх, вниз, влево, вправо), пока не достигнет другой фигуры или края доски. Ладья атакует пешку, если она может переместиться на ее клетку за один ход. Примечание: Ладья не может перемещаться через другие фигуры, такие как слоны или пешки. Это означает, что ладья не может атаковать пешку, если путь ей преграждает другая фигура. Верните количество пешек, которые атакует белая ладья.

Пример:

Input: board = [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]

Output: 3

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

1⃣Поиск ладьи:
Найдите координаты белой ладьи "R" на шахматной доске.

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

3⃣Подсчет атакованных пешек:
Если встреченная фигура - черная пешка "p", увеличьте счетчик атакованных пешек.
Если встреченная фигура - белый слон "B" или край доски, остановитесь в этом направлении.

😎 Решение:

class Solution:
    def numRookCaptures(self, board: List[List[str]]) -> int:
        def count_pawns(x, y, dx, dy):
            while 0 <= x < 8 and 0 <= y < 8:
                if board[x][y] == 'B':
                    break
                if board[x][y] == 'p':
                    return 1
                x, y = x + dx, y + dy
            return 0

        for i in range(8):
            for j in range(8):
                if board[i][j] == 'R':
                    return (count_pawns(i, j, -1, 0) + count_pawns(i, j, 1, 0) +
                            count_pawns(i, j, 0, -1) + count_pawns(i, j, 0, 1))
        return 0

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

Задача: 331. Verify Preorder Serialization of a Binary Tree
Сложность: medium

Один из способов сериализации бинарного дерева — использование обхода в порядке предварительного прохода (preorder traversal). Когда мы встречаем ненулевой узел, мы записываем значение узла. Если это нулевой узел, мы записываем его с использованием специального значения, такого как '#'.

Дана строка, содержащая значения, разделенные запятыми, представляющие предварительный обход дерева (preorder). Верните true, если это правильная сериализация предварительного обхода бинарного дерева.

Гарантируется, что каждое значение в строке, разделенное запятыми, должно быть либо целым числом, либо символом '#', представляющим нулевой указатель.
Вы можете предположить, что формат ввода всегда действителен.
Например, он никогда не может содержать две последовательные запятые, такие как "1,,3".
Примечание: Вам не разрешено восстанавливать дерево.

Пример:

Input: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
Output: true

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

1⃣Инициализация и разбор строки:
Инициализируйте переменную slots значением 1, представляющую количество доступных слотов.
Разделите строку по запятым, чтобы получить массив элементов.

2⃣Итерация по элементам и проверка:
Перебирайте каждый элемент массива. Для каждого элемента уменьшайте количество слотов на 1.
Если количество слотов становится отрицательным, верните false, так как это означает неправильную сериализацию.
Если элемент не равен '#', увеличьте количество слотов на 2, так как непустой узел создает два новых слота.

3⃣Проверка завершения:
После итерации по всем элементам проверьте, равно ли количество слотов 0. Если да, верните true, в противном случае false.

😎 Решение:

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        slots = 1
        nodes = preorder.split(',')
        
        for node in nodes:
            slots -= 1
            if slots < 0:
                return False
            if node != '#':
                slots += 2
        
        return slots == 0

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

Задача: 63. Unique Paths II
Сложность: medium

Вам дана матрица размером m на n, содержащая целые числа. Робот находится в начальный момент в верхнем левом углу (то есть в ячейке grid[0][0]). Робот пытается добраться до нижнего правого угла (то есть в ячейку grid[m - 1][n - 1]). Робот может двигаться только вниз или вправо в любой момент времени.

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

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

Тестовые примеры сгенерированы таким образом, что ответ будет не более 2 * 10^9.

Пример:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

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

1️⃣Если первая ячейка, то есть obstacleGrid[0,0], содержит 1, это означает, что в первой ячейке есть препятствие. Следовательно, робот не сможет сделать ни одного хода, и мы должны вернуть количество возможных путей как 0. Если же obstacleGrid[0,0] изначально равно 0, мы устанавливаем его равным 1 и продолжаем.

2️⃣Итерация по первой строке. Если ячейка изначально содержит 1, это означает, что текущая ячейка имеет препятствие и не должна учитываться в каком-либо пути. Следовательно, значение этой ячейки устанавливается равным 0. В противном случае, устанавливаем его равным значению предыдущей ячейки, то есть obstacleGrid[i,j] = obstacleGrid[i,j-1]. Повторяем аналогичные действия для первого столбца.

3️⃣Далее, итерация по массиву начиная с ячейки obstacleGrid[1,1]. Если ячейка изначально не содержит препятствий, то количество способов добраться до этой ячейки будет равно сумме количества способов добраться до ячейки над ней и количества способов добраться до ячейки слева от неё, то есть obstacleGrid[i,j] = obstacleGrid[i-1,j] + obstacleGrid[i,j-1]. Если в ячейке есть препятствие, устанавливаем её значение равным 0 и продолжаем. Это делается для того, чтобы она не учитывалась в других путях.

😎 Решение:

class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:

        m = len(obstacleGrid)
        n = len(obstacleGrid[0])

        if obstacleGrid[0][0] == 1:
            return 0

        obstacleGrid[0][0] = 1

        for i in range(1, m):
            obstacleGrid[i][0] = int(
                obstacleGrid[i][0] == 0 and obstacleGrid[i - 1][0] == 1
            )

        for j in range(1, n):
            obstacleGrid[0][j] = int(
                obstacleGrid[0][j] == 0 and obstacleGrid[0][j - 1] == 1
            )

        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 0:
                    obstacleGrid[i][j] = (
                        obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
                    )
                else:
                    obstacleGrid[i][j] = 0

        return obstacleGrid[m - 1][n - 1]

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

Задача: 240. Search a 2D Matrix II
Сложность: medium

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

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

Пример:

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

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

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

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

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

😎 Решение:

class Solution:
    def binarySearch(self, matrix, target, start, vertical):
        lo = start
        hi = len(matrix[0]) - 1 if vertical else len(matrix) - 1

        while hi >= lo:
            mid = (lo + hi) // 2
            if vertical:
                if matrix[start][mid] < target:
                    lo = mid + 1
                elif matrix[start][mid] > target:
                    hi = mid - 1
                else:
                    return True
            else:
                if matrix[mid][start] < target:
                    lo = mid + 1
                elif matrix[mid][start] > target:
                    hi = mid - 1
                else:
                    return True
        return False

    def searchMatrix(self, matrix, target):
        if not matrix or not matrix[0]:
            return False

        shorterDim = min(len(matrix), len(matrix[0]))
        for i in range(shorterDim):
            if self.binarySearch(matrix, target, i, True) or self.binarySearch(matrix, target, i, False):
                return True
        return False

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

Задача: 1048. Longest String Chain
Сложность: easy

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

Например, "abc" является предшественником "abac", а "cba" не является предшественником "bcad". Цепочка слов - это последовательность слов [word1, word2, ..., wordk] с k >= 1, где word1 является предшественником word2, word2 является предшественником word3 и так далее. Одиночное слово тривиально является цепочкой слов с k == 1. Верните длину самой длинной возможной цепочки слов со словами, выбранными из заданного списка слов.

Пример:

Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4

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

1⃣Отсортируй список слов по длине.

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

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

😎 Решение:

def longestStrChain(words):
    words.sort(key=len)
    dp = {}
    longest_chain = 1
    
    for word in words:
        dp[word] = 1
        for i in range(len(word)):
            predecessor = word[:i] + word[i+1:]
            if predecessor in dp:
                dp[word] = max(dp[word], dp[predecessor] + 1)
        longest_chain = max(longest_chain, dp[word])
    
    return longest_chain

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

Задача: 297. Serialize and Deserialize Binary Tree
Сложность: hard

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

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

Уточнение: формат ввода/вывода такой же, как в LeetCode для сериализации бинарного дерева. Вам не обязательно придерживаться этого формата, так что будьте креативны и придумайте свои подходы.

Пример:

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

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

1⃣Сериализация дерева:
Используйте рекурсивный обход дерева в порядке root -> left subtree -> right subtree.
Для каждого узла добавляйте его значение в строку сериализации. Если узел пустой, добавляйте "None".

2⃣Пример:
Начните с корня, узел 1, строка сериализации становится "1,".
Переходите к левому поддереву с корнем 2, строка сериализации становится "1,2,".
Для узла 2, посетите его левый узел 3 ("1,2,3,None,None,") и правый узел 4 ("1,2,3,None,None,4,None,None").
Возвращайтесь к корню 1 и посетите его правое поддерево, узел 5 ("1,2,3,None,None,4,None,None,5,None,None,").

3⃣Десериализация строки:
Разделите строку на список значений.
Используйте рекурсивную функцию для создания узлов дерева, извлекая значения из списка и восстанавливая структуру дерева. Если значение "None", узел пустой.

😎 Решение:

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

class Codec:
    def rserialize(self, root, string):
        if root is None:
            string += "null,"
        else:
            string += str(root.val) + ","
            string = self.rserialize(root.left, string)
            string = self.rserialize(root.right, string)
        return string

    def serialize(self, root):
        return self.rserialize(root, "")

    def rdeserialize(self, data_list):
        if data_list[0] == "null":
            data_list.pop(0)
            return None

        root = TreeNode(int(data_list.pop(0)))
        root.left = self.rdeserialize(data_list)
        root.right = self.rdeserialize(data_list)
        return root

    def deserialize(self, data):
        data_list = data.split(',')
        return self.rdeserialize(data_list)

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

Задача: 150. Evaluate Reverse Polish Notation
Сложность: Medium

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

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

Обратите внимание на следующие моменты:

Допустимые операторы: '+', '-', '*' и '/'.
Каждый операнд может быть целым числом или другим выражением.
Деление двух целых чисел всегда округляется к нулю.
Деление на ноль в выражении отсутствует.
Входные данные представляют собой действительное арифметическое выражение в обратной польской нотации.
Ответ и все промежуточные вычисления можно представить 32-битным целым числом.

Пример:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

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

1️⃣Обработка входных массивов: Для языков, таких как Java, где входные данные представлены фиксированным массивом, необходимо определить собственные методы для манипулирования массивом (например, удаление элементов). Это может включать сдвиг элементов для заполнения пробелов после удаления элемента. В качестве альтернативы, копирование массива в ArrayList могло бы упростить удаление, но за счет увеличения сложности по памяти с O(1) до O(n).

2️⃣Обработка типов и деление в Python: Необходимо быть внимательным при обработке типов в Python во время обработки списка, поскольку числа могут быть представлены как строки или целые числа. Кроме того, стандартное деление в Python не округляет к нулю. Вместо этого использование int(a / b) достигает желаемого результата округления, что отличается от деления нацело int(a // b), которое является другим распространенным подходом.

3️⃣Использование лямбда-функций: Лямбда-функции могут упростить реализацию арифметических операций (таких как +, -, *, /). Если вы знакомы с лямбда-функциями, они предлагают элегантное решение для динамической обработки операций. Если лямбда-функции новы или не поддерживаются в используемом языке программирования, можно использовать другие методы, а изучение лямбда-функций можно отложить на потом.

😎 Решение:

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        operations = {
            "+": lambda a, b: a + b,
            "-": lambda a, b: a - b,
            "/": lambda a, b: int(a / b),
            "*": lambda a, b: a * b,
        }

        current_position = 0

        while len(tokens) > 1:
            while tokens[current_position] not in "+-*/":
                current_position += 1

            operator = tokens[current_position]
            number_1 = int(tokens[current_position - 2])
            number_2 = int(tokens[current_position - 1])

            operation = operations[operator]
            tokens[current_position] = operation(number_1, number_2)

            tokens.pop(current_position - 2)
            tokens.pop(current_position - 2)
            current_position -= 1

        return int(tokens[0])

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

Задача: 291. Word Pattern II
Сложность: medium

Дан шаблон и строка s, вернуть true, если строка s соответствует шаблону.

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

Пример:

Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"

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

1⃣Инициализация структур данных и определение рекурсивной функции:
Создайте хеш-таблицу symbolMap для отображения символов шаблона на подстроки строки s.
Создайте множество wordSet для хранения уникальных подстрок строки s, которые были отображены на символ.
Определите рекурсивную функцию isMatch, принимающую индексы в строке s (sIndex) и в шаблоне (pIndex), чтобы определить, соответствует ли строка s шаблону.

2⃣Рекурсивная проверка соответствия:
Базовый случай: если pIndex равно длине шаблона, верните true, если sIndex равно длине строки s; иначе верните false.
Получите символ из шаблона по индексу pIndex.
Если символ уже ассоциирован с подстрокой, проверьте, совпадают ли следующие символы в строке s с этой подстрокой. Если нет, верните false. Если совпадают, вызовите isMatch для следующего символа в шаблоне.

3⃣Отображение новых подстрок:
Если символ новый, попробуйте сопоставить его с новыми подстроками строки s, начиная с sIndex и до конца строки.
Для каждой новой подстроки проверьте, существует ли она уже в `

😎 Решение:

class Solution:
    def wordPatternMatch(self, pattern: str, s: str) -> bool:
        symbol_map = {}
        word_set = set()
        return self.is_match(s, 0, pattern, 0, symbol_map, word_set)

    def is_match(self, s, s_index, pattern, p_index, symbol_map, word_set):
        if p_index == len(pattern):
            return s_index == len(s)
        
        symbol = pattern[p_index]
        if symbol in symbol_map:
            word = symbol_map[symbol]
            if not s.startswith(word, s_index):
                return False
            return self.is_match(s, s_index + len(word), pattern, p_index + 1, symbol_map, word_set)

        for k in range(s_index + 1, len(s) + 1):
            new_word = s[s_index:k]
            if new_word in word_set:
                continue
            symbol_map[symbol] = new_word
            word_set.add(new_word)
            if self.is_match(s, k, pattern, p_index + 1, symbol_map, word_set):
                return True
            del symbol_map[symbol]
            word_set.remove(new_word)
        
        return False

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

Задача: 657. Robot Return to Origin
Сложность: easy

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

Вам дана строка moves, представляющая последовательность движений робота, где moves[i] представляет его i-ое движение. Допустимые движения: 'R' (вправо), 'L' (влево), 'U' (вверх) и 'D' (вниз).

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

Примечание: направление, в котором "смотрит" робот, не имеет значения. 'R' всегда будет перемещать робота на один шаг вправо, 'L' всегда будет перемещать его на один шаг влево и т.д. Также предполагается, что величина перемещения робота одинакова для каждого хода.

Пример:

Input: moves = "UD"
Output: true

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

1⃣Инициализация координат:
Начните с координат (0, 0).

2⃣Обработка движений:
Пройдите по строке moves и обновляйте координаты в зависимости от движения:
'R' увеличивает координату x на 1.
'L' уменьшает координату x на 1.
'U' увеличивает координату y на 1.
'D' уменьшает координату y на 1.

3⃣Проверка конечных координат:
Если после всех движений координаты снова равны (0, 0), верните true. В противном случае, верните false.

😎 Решение:

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        x, y = 0, 0
        for move in moves:
            if move == 'R':
                x += 1
            elif move == 'L':
                x -= 1
            elif move == 'U':
                y += 1
            elif move == 'D':
                y -= 1
        return x == 0 and y == 0

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

Задача: 1258. Synonymous Sentences
Сложность: medium

Вам дан список эквивалентных пар строк synonyms, где synonyms[i] = [si, ti] означает, что si и ti являются эквивалентными строками. Вам также дан текст предложения. Верните все возможные синонимичные предложения, отсортированные лексикографически.

Пример:

Input: synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]], text = "I am happy today but was sad yesterday"
Output: ["I am cheerful today but was sad yesterday","I am cheerful today but was sorrow yesterday","I am happy today but was sad yesterday","I am happy today but was sorrow yesterday","I am joy today but was sad yesterday","I am joy today but was sorrow yesterday"]

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

1⃣Построить граф синонимов, используя структуру данных, такую как Union-Find или просто с использованием DFS/BFS.

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

3⃣Отсортировать полученные предложения лексикографически.

😎 Решение:

from collections import defaultdict
from itertools import product

def generateSentences(synonyms, text):
    graph = defaultdict(set)
    for s1, s2 in synonyms:
        graph[s1].add(s2)
        graph[s2].add(s1)

    def find_synonyms(word):
        synonyms = set()
        stack = [word]
        while stack:
            w = stack.pop()
            if w not in synonyms:
                synonyms.add(w)
                stack.extend(graph[w])
        return synonyms

    words = text.split()

    synonym_groups = [sorted(find_synonyms(word)) for word in words]

    sentences = list(map(' '.join, product(*synonym_groups)))

    sentences.sort()

    return sentences

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

Задача: 1354. Construct Target Array With Multiple Sums
Сложность: hard

Дан массив целых чисел target длины n. Начав с массива arr, состоящего из n единиц, вы можете выполнить следующую процедуру:

Пусть x будет суммой всех элементов, находящихся в вашем массиве.
Выберите индекс i так, чтобы 0 <= i < n, и установите значение arr в индексе i равным x.
Вы можете повторять эту процедуру столько раз, сколько потребуется.
Верните true, если возможно построить массив target из arr, в противном случае верните false.

Пример:

Input: target = [8,5]
Output: true

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

1⃣Использование максимальной кучи (Max Heap) для отслеживания максимальных значений в target:
Сначала необходимо инициализировать кучу с максимальным приоритетом, чтобы всегда иметь доступ к наибольшему элементу в массиве target.
Вычислить сумму всех элементов в target и сохранить ее.

2⃣Повторение процесса переворота:
Извлечь наибольшее значение из кучи. Вычесть это значение из общей суммы.
Проверить несколько условий:
Если извлеченное значение равно 1 или общая сумма равна 1, вернуть true.
Если извлеченное значение меньше общей суммы, общая сумма равна 0, или извлеченное значение делится на общую сумму без остатка, вернуть false.
Остаток от деления наибольшего значения на общую сумму является новым значением, которое нужно вставить обратно в кучу. Обновить общую сумму.

3⃣Повторение цикла до достижения результата:
Повторять шаг 2 до тех пор, пока не будут выполнены условия выхода из цикла (возврат true или false).

😎 Решение:

import heapq

class Solution:
    def isPossible(self, target: List[int]) -> bool:
        total = sum(target)
        target = [-x for x in target]
        heapq.heapify(target)
        
        while -target[0] > 1:
            maxVal = -heapq.heappop(target)
            total -= maxVal
            if maxVal < total or total == 0 or maxVal % total == 0:
                return False
            maxVal %= total
            total += maxVal
            heapq.heappush(target, -maxVal)
        return True

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

Задача: 116. Populating Next Right Pointers in Each Node
Сложность: medium

Вам дано идеальное бинарное дерево, где все листья находятся на одном уровне, и у каждого родителя есть два детей. Бинарное дерево имеет следующее определение:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Заполните каждый указатель next так, чтобы он указывал на следующий правый узел. Если следующего правого узла нет, указатель next должен быть установлен в NULL.

Изначально все указатели next установлены в NULL.

Пример:

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

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

1️⃣Инициализируйте очередь Q, которую мы будем использовать во время обхода. Существует несколько способов реализации обхода в ширину, особенно когда речь идет о определении уровня конкретного узла. Можно добавлять в очередь пару (узел, уровень), и каждый раз, когда добавляются дети узла, мы добавляем (node.left, parent_level + 1) и (node.right, parent_level + 1). Этот подход не будет очень эффективен для нашего алгоритма, так как нам нужны все узлы на одном уровне, и для этого потребуется еще одна структура данных.

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

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

while (!Q.empty())
{
    size = Q.size()
    for i in range 0..size
    {
        node = Q.pop()
        Q.push(node.left)
        Q.push(node.right)
    }
}

Мы начинаем с добавления корня дерева в очередь. Поскольку на уровне 0 есть только один узел, нам не нужно устанавливать какие-либо соединения, и мы можем перейти к циклу while.

😎 Решение:

import collections

class Solution:
    def connect(self, root: "Node") -> "Node":
        if not root:
            return root

        Q = collections.deque([root])

        while Q:
            size = len(Q)
            for i in range(size):
                node = Q.popleft()
                if i < size - 1:
                    node.next = Q[0]
                if node.left:
                    Q.append(node.left)
                if node.right:
                    Q.append(node.right)

        return root

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

Задача: 228. Summary Ranges
Сложность: easy

Вам дан отсортированный массив уникальных целых чисел nums.

Диапазон [a,b] - это множество всех целых чисел от a до b (включительно).

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

Каждый диапазон [a,b] в списке должен быть представлен в формате:

"a->b" если a != b
"a" если a == b

Пример:

Input: nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: The ranges are:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

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

1⃣Создайте список строк ranges, который будет содержать решение задачи, и начните итерацию по всем элементам nums с указателем i = 0. Каждая итерация внешнего цикла представляет собой поиск одного диапазона. Для начала сохраните начало текущего диапазона в start = nums[i].

2⃣Проверьте, отличается ли следующий элемент в nums на индексе i + 1 от nums[i] на 1 или больше. Если следующий элемент отличается на 1, увеличьте i на 1, чтобы включить (i+1)-й элемент в этот диапазон и продолжайте проверку следующего элемента. Продолжайте добавлять элементы в этот диапазон, пока последовательные элементы отличаются на 1, используя цикл while для выполнения этой логики.

3⃣Если следующий элемент отличается более чем на 1 или если все элементы в nums уже обработаны, проверьте, равен ли start значению nums[i]. Если start == nums[i], добавьте только start как строку в ranges, так как у нас есть только один элемент в этом диапазоне. Если start != nums[i], добавьте строку start->nums[i] в ranges. Увеличьте i на 1, чтобы начать новый диапазон.

😎 Решение:

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        ranges = []
        i = 0
        while i < len(nums):
            start = nums[i]
            while i + 1 < len(nums) and nums[i] + 1 == nums[i + 1]:
                i += 1
            if start != nums[i]:
                ranges.append(f"{start}->{nums[i]}")
            else:
                ranges.append(f"{start}")
            i += 1
        return ranges

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

from collections import Counter

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        counts = Counter(nums1)
        result = []

        for num in nums2:
            if counts[num] > 0:
                result.append(num)
                counts[num] -= 1

        return result

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

Задача: 476. Number Complement
Сложность: easy

Дополнение целого числа — это число, которое получается при замене всех 0 на 1 и всех 1 на 0 в его двоичном представлении.

Например, целое число 5 в двоичной системе — "101", и его дополнение — "010", что соответствует целому числу 2. Дано целое число num, верните его дополнение.

Пример:

Input: num = 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

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

1⃣Вычислите длину в битах входного числа: l=⌊log 2 (num)⌋+1.

2⃣Постройте битовую маску из 1-битов длины l: bitmask=(1≪l)−1.

3⃣Верните результат операции XOR числа и битовой маски: num⊕bitmask num⊕bitmask.

😎 Решение:

class Solution:
    def findComplement(self, num: int) -> int:
        bitmask = num
        bitmask |= (bitmask >> 1)
        bitmask |= (bitmask >> 2)
        bitmask |= (bitmask >> 4)
        bitmask |= (bitmask >> 8)
        bitmask |= (bitmask >> 16)
        return bitmask ^ num

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