Python | LeetCode

Онлайн-магистратура с IT специальностями от Яндекса Совместно с ИТМО, МИФИ, МФТИ. Онлайн-магистратура с актуальными программами и гибким графиком обучения. Получите высокооплачиваемую IT профессию, официальный диплом и практические знания. Господдержка оплаты. Совмещение с работой! Подать заявку #реклама 16+ practicum.yandex.ru О рекламодателе

Задача: 435. Non-overlapping Intervals Сложность: medium Дан массив интервалов intervals, где intervals[i] = [starti, endi]. Верните минимальное количество интервалов, которые нужно удалить, чтобы остальные интервалы не пересекались. Пример:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

👨‍💻 Алгоритм: 1⃣Отсортируйте интервалы по времени окончания. 2⃣Инициализируйте переменную ответа ans = 0 и целое число k для представления самого последнего времени окончания. k следует инициализировать небольшим значением, например, INT_MIN. 3⃣Итеративно пройдитесь по интервалам. Для каждого интервала: Если время начала больше или равно k, обновите k до времени окончания текущего интервала. В противном случае увеличьте ans. Верните ans. 😎 Решение:

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        ans = 0
        k = float('-inf')
        
        for x, y in intervals:
            if x >= k:
                k = y
            else:
                ans += 1
        
        return ans
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        ans = 0
        k = float('-inf')
        
        for x, y in intervals:
            if x >= k:
                k = y
            else:
                ans += 1
        
        return ans

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

Гайд по эффективным онлайн-встречам для отделов закупок Как специалистам по закупкам и тендерам экономить время на онлайн-совещаниях, сократить время на подготовку ТЗ и ускорить цикл закупок? Гайд МТС Линк — чек-листы, кейсы и подходы для упрощения коммуникации закупщиков с внутренними заказчиками и подрядчиками с помощью онлайн-встреч. ✅ В гайде: - Как создать постоянную ссылку на синки с коллегами или поставщиками и подключаться в 2 клика; - Как ускорить сбор требований без долгих переписок и конфликтов с юр.отделом; - Как обсуждать ТЗ и сразу фиксировать договоренности с помощью ИИ; - Как вести переговоры с подрядчиками и оперативно согласовать ключевые этапы сделки; - Как отслеживать выполнение условий контракта. Бонус внутри: 5 способов не выгореть от бесконечных синков. ✨ Скачайте гайд бесплатно по ссылке Скачать #реклама 16+ mts-link.ru О рекламодателе

Задача: 826. Most Profit Assigning Work Сложность: medium У вас есть n заданий и m рабочих. Вам даны три массива: difficulty, profit и worker, где: difficulty[i] и profit[i] — сложность и прибыль i-го задания, worker[j] — способность j-го рабочего (т.е. j-й рабочий может выполнить задание со сложностью не больше worker[j]). Каждому рабочему можно назначить не более одного задания, но одно задание может быть выполнено несколько раз. Например, если три рабочих выполняют одно и то же задание с оплатой $1, общая прибыль составит $3. Если рабочий не может выполнить ни одно задание, его прибыль равна $0. Верните максимальную прибыль, которую можно получить после распределения рабочих по заданиям. Пример:

Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output: 100
Explanation: Workers are assigned jobs of difficulty [4,4,6,6] and they get a profit of [20,20,30,30] separately.

👨‍💻 Алгоритм: 1⃣Создание и сортировка профиля работы Инициализируйте массив пар jobProfile с {0, 0}. Для каждого задания добавьте {difficulty[i], profit[i]} в jobProfile. Отсортируйте jobProfile по возрастанию сложности. 2⃣Обновление максимальной прибыли для каждой сложности Обновите значение прибыли каждой сложности, чтобы оно было максимальным из текущего значения и предыдущего значения прибыли. 3⃣Вычисление максимальной прибыли Для каждой способности рабочего используйте бинарный поиск, чтобы найти задание с наибольшей прибылью, которую может выполнить этот рабочий. Суммируйте полученную прибыль для всех рабочих и верните ее. 😎 Решение:

class Solution:
    def maxProfitAssignment(self, difficulty, profit, worker):
        jobProfile = [(0, 0)]
        for i in range(len(difficulty)):
            jobProfile.append((difficulty[i], profit[i]))
        jobProfile.sort()
        
        for i in range(1, len(jobProfile)):
            jobProfile[i] = (jobProfile[i][0], max(jobProfile[i][1], jobProfile[i-1][1]))
        
        netProfit = 0
        for ability in worker:
            l, r = 0, len(jobProfile) - 1
            jobProfit = 0
            while l <= r:
                mid = (l + r) // 2
                if jobProfile[mid][0] <= ability:
                    jobProfit = max(jobProfit, jobProfile[mid][1])
                    l = mid + 1
                else:
                    r = mid - 1
            netProfit += jobPro

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

Зарабатывайте на установках Яндекс Браузера Партнёрская программа для сервисных центров, магазинов компьютерной техники, сайтов для скачивания файлов и авторов статей. Вы можете предлагать его своим клиентам и аудитории — и зарабатывать на новых установках. Выплаты до 500₽ за каждую установку Яндекс Браузера. Подать заявку #реклама 0+ partner.browser.yandex.ru О рекламодателе

Задача: 253. Meeting Rooms II Сложность: medium Дан массив интервалов времени встреч intervals, где intervals[i] = [starti, endi]. Верните минимальное количество необходимых конференц-залов. Пример:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

👨‍💻 Алгоритм: 1️⃣Отсортируйте встречи по времени их начала и инициализируйте мин-кучу с временем окончания первой встречи. 2️⃣Для каждой последующей встречи проверьте, свободна ли комната (сравните время начала встречи с минимальным временем окончания в куче): Если свободна, обновите время окончания этой комнаты. Если не свободна, добавьте новое время окончания в кучу. 3️⃣После обработки всех встреч размер кучи будет равен минимальному количеству необходимых комнат. 😎 Решение:

import heapq

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[0])
        heap = [intervals[0][1]]
        
        for i in range(1, len(intervals)):
            if intervals[i][0] >= heap[0]:
                heapq.heapreplace(heap, intervals[i][1])
            else:
                heapq.heappush(heap, intervals[i][1])
        
        return len(heap)

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

Задача: 1238. Circular Permutation in Binary Representation Сложность: medium Вам дан массив строк arr. Строка s образуется конкатенацией подпоследовательности arr, содержащей уникальные символы. Верните максимально возможную длину s. Подпоследовательность - это массив, который может быть получен из другого массива путем удаления некоторых или ни одного элемента без изменения порядка оставшихся элементов. Пример:

Input: arr = ["un","iq","ue"]
Output: 4

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

def maxLength(arr):
    def is_unique(s):
        return len(s) == len(set(s))

    def backtrack(index, current):
        if not is_unique(current):
            return 0
        max_length = len(current)
        for i in range(index, len(arr)):
            max_length = max(max_length, backtrack(i + 1, current + arr[i]))
        return max_length

    return backtrack(0, "")

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

Umnico Inbox: общайтесь с клиентами эффективнее Клиенты пишут в разные мессенджеры, а сотрудники путаются и не успевают оперативно отвечать? С Umnico Inbox вы сможете: 💻 Учитывать входящие сообщения клиентов из соцсетей, мессенджеров и сайтов объявлений в одном интерфейсе. 💰 Управлять воронкой продаж и повышать продажи на том же уровне трафика. Воронка легко настраивается под задачи и требования любого бизнеса. ✨ Автоматизировать ответы на частые вопросы и создать чат-бота на базе GPT-4 в удобном конструкторе. ✅ Работать с аудиторией в групповых чатах WhatsApp, Telegram и других мессенджеров, продвигая товары и услуги. ⚡ Настраивать уведомления на десктопе и мобильном, чтобы ни одно обращение от клиента не осталось без внимания. Попробуйте возможности Umnico Inbox бесплатно сегодня Узнать больше #реклама 16+ umnico.com О рекламодателе

Задача: 211. Design Add and Search Words Data Structure Сложность: medium Спроектируйте структуру данных, которая поддерживает добавление новых слов и проверку, соответствует ли строка любому ранее добавленному слову. Реализуйте класс WordDictionary: WordDictionary() инициализирует объект. void addWord(word) добавляет слово в структуру данных, оно может быть сопоставлено позже. bool search(word) возвращает true, если в структуре данных есть строка, которая соответствует слову, или false в противном случае. Слово может содержать точки '.', где точки могут быть сопоставлены с любой буквой. Пример:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

👨‍💻 Алгоритм: 1️⃣Инициализация и добавление слова: Создайте класс WordDictionary с конструктором, который инициализирует корневой узел TrieNode. Метод addWord(String word) добавляет слово в структуру данных. Инициализируйте текущий узел как корневой и пройдите по каждому символу слова. Если символ отсутствует среди дочерних узлов текущего узла, создайте новый узел. Перемещайтесь к следующему узлу. В конце отметьте текущий узел как конец слова. 2️⃣Поиск слова в узле: Метод searchInNode(String word, TrieNode node) ищет слово в переданном узле TrieNode. Пройдите по каждому символу слова. Если символ не найден среди дочерних узлов текущего узла, проверьте, является ли символ точкой '.'. Если да, рекурсивно выполните поиск в каждом дочернем узле текущего узла. Если символ не точка и не найден, верните false. Если символ найден, перейдите к следующему узлу. В конце проверьте, является ли текущий узел концом слова. 3️⃣Поиск слова в структуре данных: Метод search(String word) использует метод searchInNode() для поиска слова, начиная с корневого узла. Верните результат поиска. Если слово найдено, верните true, иначе false. 😎 Решение:

class WordDictionary:

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

    def addWord(self, word: str) -> None:
        node = self.trie
        for ch in word:
            if ch not in node:
                node[ch] = {}
            node = node[ch]
        node["$"] = True

    def search(self, word: str) -> bool:

        def search_in_node(word, node) -> bool:
            for i, ch in enumerate(word):
                if ch not in node:
                    if ch == ".":
                        for x in node:
                            if x != "$" and search_in_node(word[i + 1:], node[x]):
                                return True
                    return False
                else:
                    node = node[ch]
            return "$" in node

        return search_in_node(word, self.trie)

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

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

Задача: 518. Coin Change II Сложность: medium Вам дан целочисленный массив coins, представляющий монеты разных номиналов, и целое число amount, представляющее общую сумму денег. Верните количество комбинаций, которые составляют эту сумму. Если эту сумму нельзя составить никакой комбинацией монет, верните 0. Предположим, что у вас есть бесконечное количество каждой монеты. Ответ гарантированно вписывается в знаковое 32-битное целое число. Пример:

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

👨‍💻 Алгоритм: 1⃣Создайте двумерный массив memo с n строками и amount + 1 столбцами. Инициализируйте значения -1, чтобы указать, что подзадача еще не решена. Реализуйте рекурсивный метод numberOfWays, который принимает два параметра: индекс i текущей рассматриваемой монеты и оставшуюся сумму, которую нужно составить. Он возвращает количество способов составить сумму, используя монеты, начиная с индекса i до последней монеты. 2⃣Если amount == 0, верните 1. Мы можем выбрать один способ, не выбирая ни одной монеты, чтобы составить сумму 0. Если i == n, у нас не осталось монет для составления суммы, верните 0. Если эта подзадача уже решена, т.е. memo[i][amount] != -1, верните memo[i][amount]. Если значение текущей монеты превышает сумму, мы не можем её использовать. Рекурсивно вызовите numberOfWays(i + 1, amount), присвойте результат memo[i][amount] и верните его. 3⃣В противном случае, добавьте общее количество способов составить сумму, как выбирая текущую монету, так и игнорируя её. Сложите значения numberOfWays(i, amount - coins[i]) и numberOfWays(i + 1, amount), сохраните результат в memo[i][amount] и верните его. Верните numberOfWays(0, amount), ответ на исходную задачу. 😎 Решение:

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        def numberOfWays(i: int, amount: int) -> int:
            if amount == 0:
                return 1
            if i == len(coins):
                return 0
            if memo[i][amount] != -1:
                return memo[i][amount]

            if coins[i] > amount:
                memo[i][amount] = numberOfWays(i + 1, amount)
            else:
                memo[i][amount] = numberOfWays(i, amount - coins[i]) + numberOfWays(i + 1, amount)
            
            return memo[i][amount]

        memo = [[-1] * (amount + 1) for _ in range(len(coins))]
        return numberOfWays(0, amount)

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

Получи грант до 1,2 млн руб. на обучение в магистратуре 4 офлайн программы, онлайн-магистратура по ML. Гранты до 1,2 млн руб. Стажировки, диплом гос. образца и фокус на твоей карьере в ЦУ Подать заявку #реклама 16+ apply.centraluniversity.ru О рекламодателе

Задача: 656. Coin Path Сложность: hard Вам дан целочисленный массив монет (1-индексированный) длины n и целое число maxJump. Вы можете перейти на любой индекс i массива coins, если coins[i] != -1 и вы должны заплатить coins[i] при посещении индекса i. Кроме того, если вы в данный момент находитесь на индексе i, вы можете перейти только на любой индекс i + k, где i + k <= n и k - значение в диапазоне [1, maxJump]. Изначально вы находитесь на индексе 1 (coins[1] не -1). Вы хотите найти путь, который достигнет индекса n с минимальной стоимостью. Верните целочисленный массив индексов, которые вы посетите в таком порядке, чтобы достичь индекса n с минимальной стоимостью. Если существует несколько путей с одинаковой стоимостью, верните лексикографически наименьший такой путь. Если невозможно достичь индекса n, возвращается пустой массив. Путь p1 = [Pa1, Pa2, ..., Pax] длины x лексикографически меньше, чем p2 = [Pb1, Pb2, ..., Pbx] длины y, если и только если при первом j, где Paj и Pbj отличаются, Paj < Pbj; если такого j нет, то x < y. Пример:

Input: coins = [1,2,4,-1,2], maxJump = 2
Output: [1,3,5]

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

import heapq

def minCostPath(coins, maxJump):
    n = len(coins)
    if coins[0] == -1:
        return []
    
    dp = [float('inf')] * n
    dp[0] = coins[0]
    path = [[] for _ in range(n)]
    path[0] = [1]
    
    heap = [(coins[0], 0)]  # (cost, index)
    
    while heap:
        current_cost, i = heapq.heappop(heap)
        if current_cost > dp[i]:
            continue
        for k in range(1, maxJump + 1):
            if i + k < n and coins[i + k] != -1:
                new_cost = current_cost + coins[i + k]
                if new_cost < dp[i + k] or (new_cost == dp[i + k] and path[i] + [i + k + 1] < path[i + k]):
                    dp[i + k] = new_cost
                    path[i + k] = path[i] + [i + k + 1]
                    heapq.heappush(heap, (new_cost, i + k))
    
    return path[-1] if dp[-1] != float('inf') else []

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

Задача: 948. Bag of Tokens Сложность: medium Вы начинаете с начальной силой, равной power, начальным счетом 0 и мешком жетонов, представленным в виде целочисленного массива tokens, где каждый tokens[i] обозначает значение tokeni. Ваша цель - максимизировать общее количество очков, стратегически разыгрывая эти жетоны. За один ход вы можете разыграть неразыгранный жетон одним из двух способов (но не обоими для одного и того же жетона): лицом вверх: Если ваша текущая сила не меньше жетонов[i], вы можете сыграть токени, потеряв силу жетонов[i] и получив 1 очко. Лицом вниз: Если ваш текущий счет не меньше 1, вы можете сыграть токени, получив силу токенов[i] и потеряв 1 счет. Верните максимально возможный счет, который вы можете получить, сыграв любое количество токенов. Пример:

Input: tokens = [100], power = 50

Output: 0

👨‍💻 Алгоритм: 1⃣Отсортировать массив tokens. Использовать два указателя: left и right, чтобы отслеживать начало и конец массива токенов. Инициализировать переменные для текущей силы power, текущего счета score и максимального счета maxScore 2⃣Повторять следующие шаги, пока left не превысит right: Если текущая сила power достаточна для разыгрывания токена tokens[left] лицом вверх, разыграть его и увеличить счет. Если текущая сила недостаточна, но счет больше 0, разыграть токен tokens[right] лицом вниз и уменьшить счет. Обновить максимальный счет, если текущий счет больше максимального. 3⃣Вернуть максимальный счет. 😎 Решение:

def bagOfTokensScore(tokens, power):
    tokens.sort()
    left, right = 0, len(tokens) - 1
    score, maxScore = 0, 0
    
    while left <= right:
        if power >= tokens[left]:
            power -= tokens[left]
            score += 1
            left += 1
            maxScore = max(maxScore, score)
        elif score > 0:
            power += tokens[right]
            score -= 1
            right -= 1
        else:
            break
    
    return maxScore

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

Задача: 433. Minimum Genetic Mutation Сложность: medium Генетическая строка может быть представлена строкой длиной 8 символов, содержащей символы 'A', 'C', 'G' и 'T'. Предположим, нам нужно исследовать мутацию от генетической строки startGene до генетической строки endGene, где одна мутация определяется как изменение одного символа в генетической строке. Например, "AACCGGTT" --> "AACCGGTA" является одной мутацией. Также существует генетический банк bank, который содержит все допустимые генетические мутации. Генетическая строка должна быть в банке, чтобы считаться допустимой. Даны две генетические строки startGene и endGene и генетический банк bank, верните минимальное количество мутаций, необходимых для мутации от startGene до endGene. Если такой мутации не существует, верните -1. Обратите внимание, что начальная строка считается допустимой, поэтому она может не быть включена в банк. Пример:

Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1

👨‍💻 Алгоритм: 1⃣Инициализируйте очередь и множество seen. Очередь будет использоваться для выполнения BFS, а множество seen будет использоваться для предотвращения повторного посещения одного и того же узла. Изначально в очередь и множество должен быть помещен startGene. 2⃣Выполняйте BFS. На каждом узле, если node == endGene, верните количество шагов, пройденных до этого момента. В противном случае, итеративно заменяйте каждый символ в строке на один из "A", "C", "G", "T" для нахождения соседей. Для каждого соседа, если он еще не был посещен и находится в bank, добавьте его в очередь и в множество seen. 3⃣Если BFS завершился и endGene не был найден, задача невыполнима. Верните -1. 😎 Решение:

from collections import deque

class Solution:
    def minMutation(self, start: str, end: str, bank: List[str]) -> int:
        queue = deque([start])
        seen = set([start])
        steps = 0
        
        while queue:
            for _ in range(len(queue)):
                node = queue.popleft()
                
                if node == end:
                    return steps
                
                for c in "ACGT":
                    for i in range(len(node)):
                        neighbor = node[:i] + c + node[i+1:]
                        if neighbor not in seen and neighbor in bank:
                            queue.append(neighbor)
                            seen.add(neighbor)
            steps += 1
        
        return -1

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

Задача: 216. Combination Sum III Сложность: medium Найдите все допустимые комбинации k чисел, которые в сумме дают n, при условии, что: Используются только числа от 1 до 9. Каждое число используется не более одного раза. Верните список всех возможных допустимых комбинаций. Список не должен содержать одинаковые комбинации, и комбинации могут возвращаться в любом порядке. Пример:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

👨‍💻 Алгоритм: 1️⃣ Инициализация и запуск рекурсивной функции: Создайте вспомогательную функцию backtrack, которая принимает текущую оставшуюся сумму, размер комбинации k, текущую комбинацию, индекс следующего элемента для добавления и список результатов. Инициализируйте пустые векторы для хранения текущей комбинации и всех возможных результатов. Запустите функцию backtrack с начальными значениями: полной суммой n, размером комбинации k, пустой комбинацией, начальным индексом 0 и пустым списком результатов. 2️⃣ Рекурсивная обработка: В функции backtrack проверьте, если текущая сумма равна нулю и размер комбинации равен k, добавьте копию текущей комбинации в список результатов. Если текущая сумма меньше нуля или размер комбинации равен k, прекратите текущую ветвь обработки. Иначе, итерируйтесь по оставшимся кандидатам, начиная с текущего индекса. Для каждого кандидата добавьте его в текущую комбинацию, обновите оставшуюся сумму и вызовите backtrack с обновленными параметрами. После возвращения из рекурсивного вызова удалите последний элемент из комбинации для рассмотрения следующего кандидата. 3️⃣ Возвращение результатов: По завершении всех рекурсивных вызовов функция combinationSum3 возвращает список всех найденных комбинаций. 😎 Решение:

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        results = []

        def backtrack(remain, comb, next_start):
            if remain == 0 and len(comb) == k:
                results.append(list(comb))
                return
            elif remain < 0 or len(comb) == k:
                return

            for i in range(next_start, 9):
                comb.append(i + 1)
                backtrack(remain - i - 1, comb, i + 1)
                comb.pop()

        backtrack(n, [], 0)

        return results

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

Большая распродажа: скидки на серверы Dell, HPE В Сервер Молл выгодное предложение на серверы Dell, HPE предыдущих поколений — самое время для апгрейда и масштабирования. Модели серверов под любые задачи: 1С, базы данных, виртуализация, видеонаблюдение, файловое хранилище, VPN и иные нагрузки. Конфигурации — от бюджетных до некогда топов с двумя процессорами Intel Xeon Gold. Все серверы в наличии и готовы к отправке! Выберите готовый вариант или сконфигурируйте под свои задачи. Консультации в любом объёме. ⚡ Бесплатная Гарантия 5 лет ⚡Доставка по всей России = 0 руб ⚡Постпродажная поддержка Если вы ждали повод собрать инфраструктуру с нуля, масштабировать или заменить старую технику — он перед вами. Акция продлится, пока серверы есть в наличии ✅ Пишите в наш Чат или Звоните — 8 800 755-25-51 📞 Узнать цену #реклама 16+ servermall.ru О рекламодателе

Задача: 556. Next Greater Element III Сложность: medium Мы можем перемешать строку s, чтобы получить строку t, используя следующий алгоритм: Дано положительное целое число n. Найдите наименьшее целое число, которое имеет точно такие же цифры, как и число n, и больше самого числа n по значению. Если такого положительного целого числа не существует, верните -1. Учтите, что возвращенное число должно помещаться в 32-битное целое число. Если существует допустимый ответ, но он не помещается в 32-битное целое число, верните -1. Пример:

Input: n = 12
Output: 21

👨‍💻 Алгоритм: 1⃣Нахождение и перестановка цифр Преобразуйте число n в массив цифр. Найдите первую цифру, которая нарушает убывающий порядок (с конца массива). Назовем её индексом i. Найдите первую цифру, которая больше digits[i-1] (с конца массива). Назовем её индексом j. Поменяйте местами цифры на позициях i-1 и j. 2⃣Обратный порядок оставшихся цифр Обратный порядок части массива от индекса i до конца, чтобы получить наименьшую перестановку, которая больше исходной. 3⃣Проверка результата и преобразование обратно в число Преобразуйте массив цифр обратно в число. Если число превышает 32-битный предел, верните -1. В противном случае верните полученное число. 😎 Решение:

class Solution:
    def swap(self, s, i0, i1):
        if i0 == i1:
            return s
        s = list(s)
        s[i0], s[i1] = s[i1], s[i0]
        return ''.join(s)
    
    def permute(self, a, l, r):
        if l == r:
            self.list.append(a)
        else:
            for i in range(l, r + 1):
                a = self.swap(a, l, i)
                self.permute(a, l + 1, r)
                a = self.swap(a, l, i)
    
    def nextGreaterElement(self, n: int) -> int:
        s = str(n)
        self.list = []
        self.permute(s, 0, len(s) - 1)
        self.list.sort()
        if s in self.list:
            index = self.list.index(s)
            if index < len(self.list) - 1:
                result = int(self.list[index + 1])
                if result <= 2**31 - 1:
                    return result
        return -1

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

Конференция для блогеров ПОСТ РОСТ 12 сентября В самом начале сентября Яндекс собирает авторов контента на первую конференцию для блогеров! Что вас ждёт: — Выступления топ-экспертов о том, как блогеру расти и развивать свой контент — Спонтанный нетворкинг — Классные активности — Консультации специалистов по монетизации контента Участие бесплатное Зарегистрироваться #реклама yandex.ru О рекламодателе

Задача: 914. X of a Kind in a Deck of Cards Сложность: easy Вам дан целочисленный массив deck, где deck[i] - число, написанное на i-й карте. Разделите карты на одну или несколько групп так, чтобы: в каждой группе было ровно x карт, где x > 1, и на всех картах в одной группе было написано одно и то же целое число. Верните true, если такое разделение возможно, или false в противном случае. Пример:

Input: deck = [1,2,3,4,4,3,2,1]
Output: true

👨‍💻 Алгоритм: 1⃣Создать словарь для подсчета частоты каждого числа в массиве deck. 2⃣Найти наибольший общий делитель (НОД) всех частот. 3⃣Проверить, больше ли НОД 1, чтобы определить, можно ли разделить карты на группы. 😎 Решение:

from collections import Counter
from math import gcd
from functools import reduce

def hasGroupsSizeX(deck):
    count = Counter(deck)
    freq_values = list(count.values())
    g = reduce(gcd, freq_values)
    return g > 1

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