Python | LeetCode

Задача: 39. Combination Sum Сложность: medium Дан массив уникальных целых чисел candidates и целевое целое число target. Верните список всех уникальных комбинаций из candidates, где выбранные числа в сумме дают target. Комбинации можно возвращать в любом порядке. Одно и то же число может быть выбрано из массива candidates неограниченное количество раз. Две комбинации считаются уникальными, если частота хотя бы одного из выбранных чисел отличается. Тестовые случаи сгенерированы таким образом, что количество уникальных комбинаций, дающих в сумме target, меньше 150 комбинаций для данного ввода. Пример:

    
        Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]{}
    

👨‍💻 Алгоритм: 1️⃣Как видно, вышеописанный алгоритм обратного отслеживания разворачивается как обход дерева в глубину (DFS - Depth-First Search), который часто реализуется с помощью рекурсии. Здесь мы определяем рекурсивную функцию backtrack(remain, comb, start) (на Python), которая заполняет комбинации, начиная с текущей комбинации (comb), оставшейся суммы для выполнения (remain) и текущего курсора (start) в списке кандидатов. Следует отметить, что сигнатура рекурсивной функции немного отличается в Java, но идея остается той же. 2️⃣Для первого базового случая рекурсивной функции, если remain == 0, то есть мы достигаем желаемой целевой суммы, поэтому мы можем добавить текущую комбинацию в итоговый список. Как другой базовый случай, если remain < 0, то есть мы превышаем целевое значение, мы прекращаем исследование на этом этапе. 3️⃣Помимо вышеупомянутых двух базовых случаев, мы затем продолжаем исследовать подсписок кандидатов, начиная с [start ... n]. Для каждого из кандидатов мы вызываем рекурсивную функцию саму с обновленными параметрами. Конкретно, мы добавляем текущего кандидата в комбинацию. С добавленным кандидатом у нас теперь меньше суммы для выполнения, то есть remain - candidate. Для следующего исследования мы все еще начинаем с текущего курсора start. В конце каждого исследования мы делаем откат, удаляя кандидата из комбинации. 😎 Решение:

    
        class Solution:
    def combinationSum(self, candidates, target):
        results = []

        def backtrack(remain, comb, start):
            if remain == 0:
                results.append(list(comb))
                return
            elif remain < 0:
                return

            for i in range(start, len(candidates)):
                comb.append(candidates[i])
                backtrack(remain - candidates[i], comb, i)
                comb.pop()

        backtrack(target, [], 0)

        return results{}
    

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

Задача: 316. Remove Duplicate Letters Сложность: medium Дана строка s, удалите повторяющиеся буквы так, чтобы каждая буква появилась один раз и только один раз. Вы должны сделать так, чтобы результат был наименьшим в лексикографическом порядке среди всех возможных результатов. Пример:

    
        Input: s = "bcabc"
Output: "abc"{}
    

👨‍💻 Алгоритм: 1⃣Инициализация стека Создайте стек, который будет хранить результат, построенный по мере итерации строки. 2⃣Итерация по строке На каждой итерации добавляйте текущий символ в стек, если он еще не был использован. Перед добавлением текущего символа удаляйте как можно больше символов из вершины стека, если это возможно и улучшает лексикографический порядок. 3⃣Удаление символов Удаляйте символы с вершины стека при выполнении следующих условий: Символ на вершине стека больше текущего символа. Символ может быть удален, так как он встречается позже в строке. На каждом этапе итерации по строке жадно минимизируйте содержимое стека. 😎 Решение:

    
        class Solution:
    def removeDuplicateLetters(self, s) -> str:
        stack = []
        seen = set()
        last_occurrence = {c: i for i, c in enumerate(s)}

        for i, c in enumerate(s):
            if c not in seen:
                while stack and c < stack[-1] and i < last_occurrence[stack[-1]]:
                    seen.discard(stack.pop())
                seen.add(c)
                stack.append(c)
        return ''.join(stack){}
    

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

CRM, которая работает сама Вам не надо вести базу клиентов вручную. Битрикс24 сам заполняет карточки, напоминает, расшифровывает звонки, находит повторные сделки. Меньше рутины, больше прибыли. Есть бесплатный тариф. Попробовать #реклама 16+ bitrix24.ru О рекламодателе

Задача: 1160. Find Words That Can Be Formed by Characters Сложность: easy Вам дан массив строк words и строка chars. Строка считается хорошей, если она может быть составлена из символов chars (каждый символ может быть использован только один раз). Верните сумму длин всех хороших строк в words. Пример:

    
        Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.{}
    

👨‍💻 Алгоритм: 1⃣Создайте хеш-таблицу counts, которая будет записывать частоту каждого символа в chars. Инициализируйте переменную ans = 0. 2⃣Итерируйте по каждому слову в words. Создайте хеш-таблицу wordCount, которая будет записывать частоту каждого символа в слове. Установите good = true. Итерируйте по каждому ключу c в wordCount. Пусть freq = wordCount[c]. Если counts[c] < freq, установите good = false и прервите цикл. 3⃣Если good = true, добавьте длину слова к ans. Верните ans. 😎 Решение:

    
        class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        counts = collections.Counter(chars)
        ans = 0
        
        for word in words:
            wordCount = collections.Counter(word)
            good = True
            for c, freq in wordCount.items():
                if counts[c] < freq:
                    good = False
                    break
            
            if good:
                ans += len(word)
        
        return ans{}
    

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

Задача: 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree Сложность: easy Даны два бинарных дерева: original и cloned, а также ссылка на узел target в оригинальном дереве. Дерево cloned является копией оригинального дерева. Верните ссылку на тот же узел в дереве cloned. Обратите внимание, что вам не разрешается изменять какое-либо из двух деревьев или узел target, и ответ должен быть ссылкой на узел в дереве cloned. Пример:

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

👨‍💻 Алгоритм: 1⃣Добавьте корень в очередь. 2⃣Пока очередь не пуста, извлекайте узел из очереди. Если узел является целевым, завершите выполнение. Добавьте сначала левый, затем правый дочерний узел в очередь. 3⃣Верните ссылку на найденный целевой узел. 😎 Решение:

    
        class Solution:
    def getTargetCopy(self, original, cloned, target):
        queue_o = [original]
        queue_c = [cloned]
        
        while queue_o:
            node_o = queue_o.pop(0)
            node_c = queue_c.pop(0)
            
            if node_o is target:
                return node_c
            
            if node_o.left:
                queue_o.append(node_o.left)
                queue_c.append(node_c.left)
            if node_o.right:
                queue_o.append(node_o.right)
                queue_c.append(node_c.right)
        return None{}
    

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

⚡️ В сети начали массово сливать курсы и книги известных онлайн школ по айти Вот отсортированная база с тонной материала (постепенно пополняется): (363 видео, 87 книги) — Python (415 видео, 68 книги) — Frontend (143 видео, 33 книги) — ИБ/Хакинг (352 видео, 89 книги) — С/С++/C# (343 видео, 87 книги) — Java/QA (176 видео, 32 книги) — Git/Linux (174 видео, 91 книги) — DevOps (167 видео, 53 книги) — PHP/1С (227 видео, 83 книги) — SQL/БД (114 видео, 77 книги) — Сисадмин (107 видео, 43 книги) — BA/SA (181 видео, 32 книги) — Go/Rust (167 видео, 43 книги) — Kotlin/Swift (112 видео, 24 книги) — Flutter (137 видео, 93 книги) — DS/ML (113 видео, 82 книги) — GameDev (183 видео, 37 книги) — Дизайн (136 видео, 33 книги) — PM/HR Скачивать ничего не нужно — все выложили в Telegram

Задача: 1276. Number of Burgers with No Waste of Ingredients Сложность: medium Даны два целых числа tomatoSlices и cheeseSlices. Ингредиенты разных бургеров таковы: Jumbo Burger: 4 ломтика помидора и 1 ломтик сыра. Small Burger: 2 ломтика помидора и 1 ломтик сыра. Верните [total_jumbo, total_small] так, чтобы количество оставшихся tomatoSlices было равно 0, а количество оставшихся cheeseSlices было равно 0. Если невозможно сделать так, чтобы оставшиеся tomatoSlices и cheeseSlices были равны 0, верните []. Пример:

    
        Input: tomatoSlices = 16, cheeseSlices = 7
Output: [1,6]{}
    

👨‍💻 Алгоритм: 1⃣Проверьте, возможно ли решить задачу, убедившись, что tomatoSlices четно и находится в допустимых пределах. 2⃣Решите систему уравнений: 4J + 2S = tomatoSlices J + S = cheeseSlices 3⃣Если решение существует, верните его, иначе верните пустой список. 😎 Решение:

    
        def numOfBurgers(tomatoSlices, cheeseSlices):
    if tomatoSlices % 2 != 0 or tomatoSlices < 2 * cheeseSlices or tomatoSlices > 4 * cheeseSlices:
        return []
    total_jumbo = (tomatoSlices - 2 * cheeseSlices) // 2
    total_small = cheeseSlices - total_jumbo
    return [total_jumbo, total_small]{}
    

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

Задача: 87. Scramble String Сложность: hard Мы можем перемешать строку s, чтобы получить строку t, используя следующий алгоритм: 1. Если длина строки равна 1, остановиться. 2. Если длина строки больше 1, выполнить следующее: - Разделить строку на две непустые подстроки в случайном индексе, например, если строка это s, разделить её на x и y, где s = x + y. - Случайным образом решить, поменять ли местами две подстроки или оставить их в том же порядке. То есть после этого шага s может стать s = x + y или s = y + x. - Применить шаг 1 рекурсивно к каждой из двух подстрок x и y. Для двух строк s1 и s2 одинаковой длины вернуть true, если s2 является перемешанной строкой s1, в противном случае вернуть false. Пример:

    
        Input: s1 = "great", s2 = "rgeat"
Output: true
Explanation: One possible scenario applied on s1 is:
"great" --> "gr/eat" // divide at random index.
"gr/eat" --> "gr/eat" // random decision is not to swap the two substrings and keep them in order.
"gr/eat" --> "g/r / e/at" // apply the same algorithm recursively on both substrings. divide at random index each of them.
"g/r / e/at" --> "r/g / e/at" // random decision was to swap the first substring and to keep the second substring in the same order.
"r/g / e/at" --> "r/g / e/ a/t" // again apply the algorithm recursively, divide "at" to "a/t".
"r/g / e/ a/t" --> "r/g / e/ a/t" // random decision is to keep both substrings in the same order.
The algorithm stops now, and the result string is "rgeat" which is s2.
As one possible scenario led s1 to be scrambled to s2, we return true.{}
    

👨‍💻 Алгоритм: 1️⃣- Итерируйте i от 0 до n-1. - Итерируйте j от 0 до n-1. - Установите dp[1][i][j] в булево значение s1[i] == s2[j]. (Базовый случай динамического программирования). 2️⃣- Итерируйте length от 2 до n. - Итерируйте i от 0 до n + 1 - length. - Итерируйте j от 0 до n + 1 - length. 3️⃣- Итерируйте newLength от 1 до length - 1. - Если dp[newLength][i][j] && dp[length-newLength][i+newLength][j+newLength]) || (dp[newLength][i][j+length-newLength] && dp[length-newLength][i+newLength][j]) верно, установите dp[length][i][j] в true. - Верните dp[n][0][0]. 😎 Решение:

    
        class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        n = len(s1)
        dp = [
            [[False for j in range(n)] for i in range(n)] for l in range(n + 1)
        ]
        for i in range(n):
            for j in range(n):
                dp[1][i][j] = s1[i] == s2[j]
        for length in range(2, n + 1):
            for i in range(n + 1 - length):
                for j in range(n + 1 - length):
                    for new_length in range(1, length):
                        dp1 = dp[new_length][i]
                        dp2 = dp[length - new_length][i + new_length]
                        dp[length][i][j] |= dp1[j] and dp2[j + new_length]
                        dp[length][i][j] |= (
                            dp1[j + length - new_length] and dp2[j]
                        )
        return dp[n][0][0]{}
    

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

Бесплатный курс по дизайну: веб, графический и UX/UI Получи востребованные навыки: - создание дизайна сайтов и приложений - создание инфографики и карточек для маркетплейсов - работа в графическом редакторе Figma и др. Студенты курса в среднем зарабатывают от 68 000 ₽ уже во время обучения💰 Зарегистрироваться #реклама 16+ ydaev.ru О рекламодателе

Задача: 679. 24 Game Сложность: hard Дан массив целых чисел cards длиной 4. У вас есть четыре карты, каждая из которых содержит число в диапазоне от 1 до 9. Вам нужно расположить числа на этих картах в математическом выражении, используя операторы ['+', '-', '*', '/'] и скобки '(' и ')' так, чтобы получить значение 24. Вы ограничены следующими правилами: Оператор деления '/' представляет собой реальное деление, а не целочисленное деление. Например, 4 / (1 - 2 / 3) = 4 / (1 / 3) = 12. Каждая операция выполняется между двумя числами. В частности, мы не можем использовать '-' как унарный оператор. Например, если cards = [1, 1, 1, 1], выражение "-1 - 1 - 1 - 1" не допускается. Вы не можете объединять числа вместе. Например, если cards = [1, 2, 1, 2], выражение "12 + 12" недопустимо. Вернуть true, если вы можете получить такое выражение, которое оценивается в 24, и false в противном случае. Пример:

    
        Input: cards = [4,1,8,7]
Output: true
Explanation: (8-4) * (7-1) = 24{}
    

👨‍💻 Алгоритм: 1⃣Создайте функцию generatePossibleResults(a, b), которая возвращает массив результатов всех возможных математических операций над двумя числами. 2⃣ Создайте функцию checkIfResultReached(list), чтобы проверить, можем ли мы достичь результата 24, используя текущий массив list. Сначала проверьте базовые условия: если размер массива равен 1, верните true, если результат равен 24, иначе верните false. 3⃣Если размер массива больше 1, выберите любые два числа из списка, выполните все математические операции над ними, создайте новый список с обновленными элементами и снова вызовите рекурсивную функцию с этим новым списком. Если ни одна комбинация не приводит к результату 24, верните false. Вызовите checkIfResultReached с исходным списком карт. 😎 Решение:

    
        class Solution:
    def generatePossibleResults(self, a, b):
        res = [a + b, a - b, b - a, a * b]
        if a != 0:
            res.append(b / a)
        if b != 0:
            res.append(a / b)
        return res

    def checkIfResultReached(self, list):
        if len(list) == 1:
            return abs(list[0] - 24) <= 0.1

        for i in range(len(list)):
            for j in range(i + 1, len(list)):
                new_list = [list[k] for k in range(len(list)) if k != i and k != j]
                for res in self.generatePossibleResults(list[i], list[j]):
                    new_list.append(res)
                    if self.checkIfResultReached(new_list):
                        return True
                    new_list.pop()
        return False

    def judgePoint24(self, cards):
        return self.checkIfResultReached(list(map(float, cards))){}
    

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