Python | LeetCode

#medium Задача: 97. Interleaving String Даны строки s1, s2 и s3. Необходимо определить, может ли строка s3 быть сформирована путем чередования строк s1 и s2. Чередование двух строк s и t — это конфигурация, при которой s и t делятся на n и m подстрок соответственно так, что: s = s1 + s2 + ... + sn t = t1 + t2 + ... + tm |n - m| ≤ 1 Чередование может быть таким: s1 + t1 + s2 + t2 + s3 + t3 + ... или t1 + s1 + t2 + s2 + t3 + s3 + ... Примечание: a + b означает конкатенацию строк a и b. Пример:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Explanation: One way to obtain s3 is:
Split s1 into s1 = "aa" + "bc" + "c", and s2 into s2 = "dbbc" + "a".
Interleaving the two splits, we get "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac".

👨‍💻 Алгоритм: 1️⃣В рекурсивном подходе, описанном выше, рассматривается каждая возможная строка, образованная путем чередования двух заданных строк. Однако возникают случаи, когда та же часть s1 и s2 уже была обработана, но в разных порядках (перестановках). Независимо от порядка обработки, если результирующая строка до этого момента совпадает с требуемой строкой (s3), окончательный результат зависит только от оставшихся частей s1 и s2, а не от уже обработанной части. Таким образом, рекурсивный подход приводит к избыточным вычислениям. 2️⃣Эту избыточность можно устранить, используя мемоизацию вместе с рекурсией. Для этого мы поддерживаем три указателя i, j, k, которые соответствуют индексу текущего символа s1, s2, s3 соответственно. Также мы поддерживаем двумерный массив memo для отслеживания обработанных до сих пор подстрок. memo[i][j] хранит 1/0 или -1 в зависимости от того, была ли текущая часть строк, то есть до i-го индекса для s1 и до j-го индекса для s2, уже оценена. Мы начинаем с выбора текущего символа s1 (на который указывает i). Если он совпадает с текущим символом s3 (на который указывает k), мы включаем его в обработанную строку и вызываем ту же функцию рекурсивно как: is_Interleave(s1, i+1, s2, j, s3, k+1, memo). 3️⃣Таким образом, мы вызвали функцию, увеличив указатели i и k, поскольку часть строк до этих индексов уже была обработана. Аналогично, мы выбираем один символ из второй строки и продолжаем. Рекурсивная функция заканчивается, когда одна из двух строк s1 или s2 полностью обработана. Если, скажем, строка s1 полностью обработана, мы напрямую сравниваем оставшуюся часть s2 с оставшейся частью s3. Когда происходит возврат из рекурсивных вызовов, мы сохраняем значение, возвращенное рекурсивными функциями, в массиве мемоизации memo соответственно, так что когда оно встречается в следующий раз, рекурсивная функция не будет вызвана, но сам массив мемоизации вернет предыдущий сгенерированный результат. 😎 Решение:

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s3) != len(s1) + len(s2):
            return False
        dp = [[False] * (len(s2) + 1) for _ in range(len(s1) + 1)]
        for i in range(len(s1) + 1):
            for j in range(len(s2) + 1):
                if i == 0 and j == 0:
                    dp[i][j] = True
                elif i == 0:
                    dp[i][j] = dp[i][j - 1] and s2[j - 1] == s3[i + j - 1]
                elif j == 0:
                    dp[i][j] = dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]
                else:
                    dp[i][j] = (
                        dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]
                    ) or (dp[i][j - 1] and s2[j - 1] == s3[i + j - 1])
        return dp[len(s1)][len(s2)]

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

IT аутсорсинг в СПб! Обслуживание серверов и оргтехники! АйТи аутсорсинг в СПб! Сертифицированные специалисты! Опытная команда IT специалистов! Сертификаты Microsoft! CISCO Mikrotik! 12 лет на рынке! Перейти на сайт #реклама svcnet.ru О рекламодателе

#medium Задача: 96. Unique Binary Search Trees Дано целое число n. Верните количество структурно уникальных деревьев бинарного поиска (BST), которые содержат ровно n узлов с уникальными значениями от 1 до n. Пример:

Input: n = 3
Output: 5

👨‍💻 Алгоритм: 1️⃣Задача состоит в том, чтобы рассчитать количество уникальных BST (бинарных деревьев поиска). Для этого мы можем определить две функции: G(n): количество уникальных BST для последовательности длины n. F(i, n): количество уникальных BST, где число i является корнем BST (1 ≤ i ≤ n). Как видно, G(n) - это именно та функция, которая нам нужна для решения задачи. 2️⃣Позднее мы увидим, что G(n) можно вывести из F(i, n), которая, в свою очередь, рекурсивно относится к G(n). Следуя идее из раздела "Интуиция", мы видим, что общее количество уникальных BST G(n) равно сумме BST F(i, n) с перечислением каждого числа i (1 ≤ i ≤ n) в качестве корня. Таким образом, G(n) = ∑ F(i, n) для i от 1 до n. В частности, для базовых случаев есть только одна комбинация для построения BST из последовательности длиной 1 (только корень) или ничего (пустое дерево). То есть G(0) = 1, G(1) = 1. 3️⃣Дана последовательность от 1 до n, мы выбираем число i из последовательности в качестве корня, тогда количество уникальных BST с указанным корнем, определенным как F(i, n), является декартовым произведением количества BST для его левого и правого поддеревьев, как показано ниже: Например, F(3,7) - количество уникальных деревьев BST с числом 3 в качестве корня. Для построения уникального BST из всей последовательности [1, 2, 3, 4, 5, 6, 7] с 3 в качестве корня, мы должны построить поддерево из его левой подпоследовательности [1, 2] и другое поддерево из правой подпоследовательности [4, 5, 6, 7], а затем соединить их вместе (то есть декартово произведение). Теперь хитрость заключается в том, что мы можем рассматривать количество уникальных BST из последовательности [1,2] как G(2), и количество уникальных BST из последовательности [4, 5, 6, 7] как G(4). Для G(n) не имеет значения содержание последовательности, а только длина последовательности. Следовательно, F(3,7) = G(2)⋅G(4). Обобщая пример, мы можем вывести следующую формулу: F(i, n) = G(i−1)⋅G(n−i) Объединяя формулы (1), (2), мы получаем рекурсивную формулу для G(n), то есть G(n) = ∑ G(i−1)⋅G(n−i) для i от 1 до n. Чтобы вычислить результат функции, мы начинаем с меньшего числа, так как значение G(n) зависит от значений G(0)...G(n−1). 😎 Решение:

class Solution:
    def numTrees(self, n: int) -> int:
        G = [0] * (n + 1)
        G[0], G[1] = 1, 1

        for i in range(2, n + 1):
            for j in range(1, i + 1):
                G[i] += G[j - 1] * G[i - j]

        return G[n]

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Реклама для бизнеса любого уровня в Яндекс Директе Создайте эффективную рекламную кампанию с алгоритмами Яндекс Директа 👌 Начните прямо сейчас ⚡ Зарегистрироваться #реклама direct.yandex.ru О рекламодателе

#medium Задача: 95. Unique Binary Search Trees II Дано целое число n. Верните все структурно уникальные деревья бинарного поиска (BST), которые содержат ровно n узлов с уникальными значениями от 1 до n. Ответ может быть представлен в любом порядке. Пример:

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

👨‍💻 Алгоритм: 1️⃣Создайте хеш-карту memo, где memo[(start, end)] содержит список корневых узлов всех возможных BST (деревьев бинарного поиска) с диапазоном значений узлов от start до end. Реализуем рекурсивную функцию allPossibleBST, которая принимает начальный диапазон значений узлов start, конечный диапазон end и memo в качестве параметров. Она возвращает список TreeNode, соответствующих всем BST, которые могут быть сформированы с этим диапазоном значений узлов. Вызываем allPossibleBST(1, n, memo) и выполняем следующее: 2️⃣Объявляем список TreeNode под названием res для хранения списка корневых узлов всех возможных BST. Если start > end, мы добавляем null в res и возвращаем его. Если мы уже решили эту подзадачу, т.е. memo содержит пару (start, end), мы возвращаем memo[(start, end)]. 3️⃣Выбираем значение корневого узла от i = start до end, увеличивая i на 1 после каждой итерации. Рекурсивно вызываем leftSubtrees = allPossibleBST(start, i - 1, memo) и rightSubTrees = allPossibleBST(i + 1, end, memo). Перебираем все пары между leftSubtrees и rightSubTrees и создаем новый корень со значением i для каждой пары. Добавляем корень новообразованного BST в res. Устанавливаем memo[(start, end)] = res и возвращаем res. 😎 Решение:

class Solution:
    def allPossibleBST(self, start, end, memo):
        res = []
        if start > end:
            res.append(None)
            return res
        if (start, end) in memo:
            return memo[(start, end)]

        for i in range(start, end + 1):
            leftSubTrees = self.allPossibleBST(start, i - 1, memo)
            rightSubTrees = self.allPossibleBST(i + 1, end, memo)
            for left in leftSubTrees:
                for right in rightSubTrees:
                    root = TreeNode(i, left, right)
                    res.append(root)

        memo[(start, end)] = res
        return res

    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        memo = {}
        return self.allPossibleBST(1, n, memo)

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Оплачиваемая стажировка и трудоустройство без опыта — ну ничего себе 😳 Все возможно с Добровольным квалификационным экзаменом! Это бесплатный проект Правительства Москвы, где ты можешь показать свои знания по специальности, запомниться потенциальным работодателям и получить оффер в престижные компании Москвы. Тебя ждет всего три шага: 1️⃣ Пройди тест После регистрации на сайте ДКЭ тебе будет доступно 70 профессий по 7 направлениям. Выбирай тест по своей специальности и проверь уровень своих знаний! 2️⃣ Реши кейс Если ты успешно сдал тест, тебя пригласят на следующий этап, где ты с другими участниками в команде будешь решать реальный кейс одного из работодателей. 3️⃣ Стань победителем Окажись в числе лучших по общему количеству баллов за оба этапа и получи шанс попасть на оплачиваемую стажировку с дальнейшим трудоустройством. Готов проявить себя? Регистрируйся и начинай проходить тест — https://dke.moscow Реклама. АНО "РАЗВИТИЕ ЧЕЛОВЕЧЕСКОГО КАПИТАЛА", АНО "РЧК". ИНН 7710364647. erid: LjN8KNVQd

Запустите мобильное приложение для вашего магазина Запустите мобильное приложение для вашего интернет-магазина за 6 недель и увеличьте продажи на 20-30% в течение 6 месяцев! Зачем? Повысить выручку с мобильного трафика, увеличить LTV и лояльность покупателей, привлечь новую аудиторию. Что вы получаете после запуска приложения с IMSHOP.IO: - Рост конверсии в 4-5 раз - Повторные продажи до 50% - Увеличение выручки с ecom-канала в 2 раза IMSHOP.IO - крупнейший в России разработчик мобильных приложений для ретейла. С командой работают 150+ клиентов: ECCO, re:Store, FinnFlare, ТВОЕ, AllTime и другие. Узнать больше #реклама imshop.io О рекламодателе

#easy Задача: 94. Binary Tree Inorder Traversal Дан корень бинарного дерева. Верните обход значений его узлов в симметричном порядке. Пример:

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

👨‍💻 Алгоритм: Метод решения этой задачи использует рекурсию. Это классический метод, и он простой. Мы можем определить вспомогательную функцию для реализации рекурсии. 😎 Решение:

class Solution:
    def inorderTraversal(self, root):
        res = []
        self.helper(root, res)
        return res

    def helper(self, root, res):
        if root is not None:
            self.helper(root.left, res)
            res.append(root.val)
            self.helper(root.right, res)

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

❓Если вам интересно - Почему батчевые update могут вызывать дедлоки - Что делать, если одни и те же данные нужны в нескольких сервисах - Как эффективно осуществлять пагинацию, когда записей очень много ✅ То подписывайтесь на канал Senior Backend разработчика с авторскими статьями про проектирование, архитектуру, базы данных

#medium Задача: 93. Restore IP Addresses Сообщение, содержащее буквы от 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

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Jobski - твой помощник при поиске работы в IT Сервис индивидуально подбирает вакансии, учитывая ваш опыт, навыки, стек технологий. Узнать больше #реклама jobski.ru О рекламодателе

#medium Задача: 92. Reverse Linked List II Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список. Пример:

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

👨‍💻 Алгоритм: 1️⃣Определяем рекурсивную функцию, которая будет отвечать за переворачивание части односвязного списка. Назовем эту функцию recurse. Функция принимает три параметра: m, начальную точку переворота, n, конечную точку переворота, и указатель right, который начинается с узла n в связанном списке и движется назад вместе с откатом рекурсии. Если это пока не ясно, следующие диаграммы помогут. 2️⃣Также у нас есть указатель left, который начинается с узла m в связанном списке и движется вперед. В Python мы должны использовать глобальную переменную для этого, которая изменяется с каждым вызовом рекурсии. В других языках, где изменения, сделанные в вызовах функций, сохраняются, мы можем рассматривать этот указатель как дополнительную переменную для функции recurse. В рекурсивном вызове, учитывая m, n и right, мы проверяем, равно ли n единице. Если это так, дальше двигаться не нужно. 3️⃣До тех пор, пока мы не достигнем n = 1, мы продолжаем двигать указатель right на один шаг вперед, после чего делаем рекурсивный вызов с уменьшенным на один значением n. В то же время мы продолжаем двигать указатель left вперед до тех пор, пока m не станет равным 1. Когда мы говорим, что указатель движется вперед, мы имеем в виду pointer.next. Таким образом, мы откатываемся, как только n достигает 1. В этот момент указатель right находится на последнем узле подсписка, который мы хотим перевернуть, и left уже достиг первого узла этого подсписка. Тогда мы меняем данные и перемещаем указатель left на один шаг вперед с помощью left = left.next. Нам нужно, чтобы это изменение сохранялось в процессе отката. Оттуда при каждом откате указатель right движется на один шаг назад. Это и есть та симуляция, о которой мы всё время говорили. Обратное движение симулируется откатом. Мы прекращаем обмены, когда right == left, что происходит, если размер подсписка нечетный, или right.next == left, что происходит в процессе отката для четного подсписка, когда указатель right пересекает left. Мы используем глобальный булевый флаг для остановки обменов, как только эти условия выполнены. 😎 Решение:

class Solution:
    def reverseBetween(
        self, head: Optional[ListNode], m: int, n: int
    ) -> Optional[ListNode]:
        if not head:
            return None

        left, right = head, head
        stop = False

        def recurseAndReverse(right, m, n):
            nonlocal left, stop
            if n == 1:
                return
            right = right.next
            if m > 1:
                left = left.next
            recurseAndReverse(right, m - 1, n - 1)
            if left == right or right.next == left:
                stop = True
            if not stop:
                left.val, right.val = right.val, left.val
                left = left.next

        recurseAndReverse(right, m, n)
        return head

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#medium Задача: 91. Decode Ways Сообщение, содержащее буквы от 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 с ключом как текущий индекс, чтобы сохранить его для будущих пересекающихся подзадач. 😎 Решение:

from functools import lru_cache

class Solution:

    @lru_cache(maxsize=None)
    def recursiveWithMemo(self, index, s) -> int:
        if index == len(s):
            return 1

        if s[index] == "0":
            return 0

        if index == len(s) - 1:
            return 1

        answer = self.recursiveWithMemo(index + 1, s)
        if int(s[index: index + 2]) <= 26:
            answer += self.recursiveWithMemo(index + 2, s)

        return answer

    def numDecodings(self, s: str) -> int:
        return self.recursiveWithMemo(0, s)

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать #реклама yandex.ru О рекламодателе

#medium Задача: 90. Subsets II Дан массив целых чисел nums, который может содержать повторяющиеся элементы. Верните все возможные подмножества (степенной набор). Результирующий набор не должен содержать дублирующихся подмножеств. Возвращаемый результат может быть в любом порядке. Пример:

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

👨‍💻 Алгоритм: 1️⃣Отсортируйте массив nums. Сортировка необходима для того, чтобы все сгенерированные подмножества также были отсортированы. Это помогает идентифицировать дубликаты. 2️⃣Инициализируйте maxNumberOfSubsets максимальным количеством подмножеств, которые можно сгенерировать, т.е., 2 в степени n. Инициализируйте множество, seen, типа string, для хранения всех сгенерированных подмножеств. Добавление всех отсортированных подмножеств в множество дает нам возможность отловить любые дублирующие подмножества. 3️⃣Итерируйте от 0 до maxNumberOfSubsets - 1. Установленные биты в двоичном представлении subsetIndex указывают на позицию элементов в массиве nums, которые присутствуют в текущем подмножестве. Инициализируйте строку hashcode, которая будет хранить список чисел в текущемSubset в виде строки, разделенной запятыми. hashcode необходим для уникальной идентификации каждого подмножества с помощью множества. Выполните внутренний цикл for от j = 0 до n - 1, чтобы проверить позицию установленных битов в subsetIndex. Если на позиции j установлен бит, добавьте nums[j] в текущее подмножество currentSubset и добавьте nums[j] в строку hashcode. Добавьте текущее подмножество currentSubset в seen и в список подмножеств, если сгенерированный hashcode еще не в seen. Верните подмножества. 😎 Решение:

class Solution:
    def subsetsWithDup(self, nums):
        n = len(nums)
        nums.sort()
        maxNumberOfSubsets = 2**n
        seen = set()
        subsets = []
        for subsetIndex in range(maxNumberOfSubsets):
            currentSubset = []
            hashcode = ""
            for j in range(n):
                mask = 2**j
                isSet = mask & subsetIndex
                if isSet != 0:
                    currentSubset.append(nums[j])
                    hashcode += str(nums[j]) + ","
            if hashcode not in seen:
                subsets.append(currentSubset)
                seen.add(hashcode)
        return subsets

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Такси для бизнеса. Яндекс Go Оптимизируйте свои расходы и повысьте эффективность бизнеса с Яндекс Go Узнать больше #реклама business.go.yandex О рекламодателе

#medium Задача: 89. Gray Code Последовательность Грея с n-битами — это последовательность из 2^n целых чисел, где: 1. Каждое число находится в включающем диапазоне от 0 до 2^n - 1, 2. Первое число равно 0, 3. Каждое число встречается в последовательности не более одного раза, 4. Двоичное представление каждой пары соседних чисел отличается ровно на один бит, 5. Двоичное представление первого и последнего чисел отличается ровно на один бит. Для заданного числа n возвращается любая допустимая последовательность Грея с n-битами. Пример:

Input: n = 2
Output: [0,1,3,2]
Explanation:
The binary representation of [0,1,3,2] is [00,01,11,10].
- 00 and 01 differ by one bit
- 01 and 11 differ by one bit
- 11 and 10 differ by one bit
- 10 and 00 differ by one bit
[0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01].
- 00 and 10 differ by one bit
- 10 and 11 differ by one bit
- 11 and 01 differ by one bit
- 01 and 00 differ by one bit

👨‍💻 Алгоритм: 1️⃣Инициализируйте список результатов для хранения последовательности решений. Добавьте 0 в список перед вызовом вспомогательного метода, так как все последовательности Грея начинаются с 0. 2️⃣Инициализируйте множество visited. Это позволяет отслеживать числа, присутствующие в текущей последовательности, чтобы избежать повторения. Начните с числа 0. В функции grayCodeHelper() используйте цикл for, чтобы найти каждое возможное число (next), которое может быть сгенерировано путем изменения одного бита последнего числа в списке результатов (current). Делайте это, переключая i-ый бит на каждой итерации. Поскольку максимально возможное количество битов в любом числе последовательности равно n, необходимо переключить n битов. 3️⃣Если next не присутствует в множестве использованных чисел (isPresent), добавьте его в список результатов и множество isPresent. Продолжайте поиск с next. Если grayCodeHelper(next) возвращает true, это означает, что допустимая последовательность найдена. Дальнейший поиск не требуется (ранняя остановка). Это раннее завершение улучшает время выполнения. Если с next не найдена допустимая последовательность, удаляем его из списка результатов и множества isPresent и продолжаем поиск. При достижении базового условия, когда длина текущей последовательности равна 2^n, возвращаем true. Выход из цикла for означает, что с current в качестве последнего числа не найдена допустимая последовательность кода Грея. Поэтому возвращаем false. 😎 Решение:

class Solution:
    def grayCode(self, n: int):
        result = [0]
        isPresent = {0}
        self.grayCodeHelper(result, n, isPresent)
        return result

    def grayCodeHelper(self, result, n, isPresent):
        if len(result) == (1 << n):
            return True
        current = result[-1]
        for i in range(n):
            nextNum = current ^ (1 << i)
            if nextNum not in isPresent:
                isPresent.add(nextNum)
                result.append(nextNum)
                if self.grayCodeHelper(result, n, isPresent):
                    return True
                isPresent.remove(nextNum)
                result.pop()
        return False

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#easy Задача: 88. Merge Sorted Array Вам даны два массива целых чисел nums1 и nums2, отсортированных в порядке неубывания, а также два целых числа m и n, представляющих количество элементов в nums1 и nums2 соответственно. Слейте nums1 и nums2 в один массив, отсортированный в порядке неубывания. Итоговый отсортированный массив не должен возвращаться функцией, а должен храниться внутри массива nums1. Чтобы это обеспечить, длина nums1 составляет m + n, где первые m элементов обозначают элементы, которые должны быть объединены, а последние n элементов установлены в 0 и должны быть проигнорированы. Длина nums2 составляет n. Пример:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

👨‍💻 Алгоритм: 1️⃣Самая простая реализация заключалась бы в создании копии значений в nums1, называемой nums1Copy, а затем использовании двух указателей для чтения и одного указателя для записи для чтения значений из nums1Copy и nums2 и записи их в nums1. 2️⃣Инициализируйте nums1Copy новым массивом, содержащим первые m значений nums1. Инициализируйте указатель для чтения p1 в начале nums1Copy. Инициализируйте указатель для чтения p2 в начале nums2. 3️⃣Инициализируйте указатель для записи p в начале nums1. Пока p все еще находится внутри nums1: Если nums1Copy[p1] существует и меньше или равно nums2[p2]: Запишите nums1Copy[p1] в nums1[p], и увеличьте p1 на 1. Иначе Запишите nums2[p2] в nums1[p], и увеличьте p2 на 1. Увеличьте p на 1. 😎 Решение:

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        nums1_copy = nums1[:m]
        p1 = 0
        p2 = 0
        for p in range(n + m):
            if p2 >= n or (p1 < m and nums1_copy[p1] <= nums2[p2]):
                nums1[p] = nums1_copy[p1]
                p1 += 1
            else:
                nums1[p] = nums2[p2]
                p2 += 1

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Для тех кто изучает  любой язык программирования с нуля или уже имеет опыт, кто ищет поддержку и напарника на безвозмездной основе добавляйтесь и давайте помогать друг другу в освоении программирования. Группа https://t.me/lp2024it

Бакалавриат и специалитет Президентской академии! ✅ Важное для абитуриентов! 🎓 🎓Хотите стать студентом одного из лучших университетов страны? Тогда не упустите шанс поступить на программы бакалавриата и специалитета в Президентскую академию (РАНХиГС). На выбор более 100 программ обучения, стажировки и практики в органах государственной власти и крупных коммерческих компаниях, участие в реальных проектах во время обучения, стипендии и общежития. Создавайте будущее страны вместе с РАНХиГС. Подробности о поступлении и об Академии вы найдете на нашем сайте. Успейте подать заявку! Узнать больше #реклама ranepa.ru О рекламодателе