Python | LeetCode

#medium Задача: 772. Basic Calculator III Реализуйте базовый калькулятор для вычисления простого строкового выражения. Строка выражения содержит только неотрицательные целые числа, операторы '+', '-', '*', '/' и открывающие '(' и закрывающие скобки ')'. Целочисленное деление должно округляться к нулю. Предполагается, что данное выражение всегда корректно. Все промежуточные результаты будут находиться в диапазоне [-2^31, 2^31 - 1]. Примечание: нельзя использовать встроенные функции для вычисления строк как математических выражений, такие как eval(). Пример:

Input: s = "1+1"
Output: 2

👨‍💻 Алгоритм: 1⃣Определите вспомогательную функцию evaluate, которая принимает оператор и числовые аргументы. Заметьте, что эта функция идентична той, что представлена в подходе "Basic Calculator II". Инициализируйте несколько переменных: стек для хранения промежуточных результатов, curr для отслеживания текущего числа, которое мы строим, и previousOperator для отслеживания предыдущего оператора. Добавьте в строку s случайный символ, который не будет появляться во входных данных, например "@". 2⃣Итерация по входным данным. Для каждого символа c: если c является цифрой, добавьте его к curr. В противном случае, если c == '(', мы начинаем вычисление нового изолированного выражения. В этом случае сохраните previousOperator в стек и установите previousOperator = "+". 3⃣Если c является оператором, то необходимо вычислить значение curr. Используйте функцию evaluate, чтобы применить previousOperator к curr, и добавьте результат в стек. Затем сбросьте curr до нуля и обновите previousOperator = c. Если c == ')', это означает, что мы находимся в конце изолированного выражения и должны полностью его вычислить. Извлекайте из стека до тех пор, пока не достигнете оператора, суммируя все извлеченные числа в curr. Как только достигнете оператора, обновите previousOperator = stack.pop(). Верните сумму всех чисел в стеке. 😎 Решение:

class Solution:
    def evaluate(self, operator, first, second):
        x = int(first)
        y = int(second)
        if operator == '+':
            return str(x)
        elif operator == '-':
            return str(-x)
        elif operator == '*':
            return str(x * y)
        else:
            return str(x // y)

    def calculate(self, s: str) -> int:
        stack = []
        curr = ""
        previousOperator = '+'
        s += "@"
        operators = set("+-*/")
        
        for c in s:
            if c.isdigit():
                curr += c
            elif c == '(':
                stack.append(previousOperator)
                previousOperator = '+'
            else:
                if previousOperator in "*/":
                    stack.append(self.evaluate(previousOperator, stack.pop(), curr))
                else:
                    stack.append(self.evaluate(previousOperator, curr, "0"))
                
                curr = ""
                previousOperator = c
                if c == ')':
                    currentTerm = 0
                    while stack[-1] not in operators:
                        currentTerm += int(stack.pop())
                    curr = str(currentTerm)
                    previousOperator = stack.pop()
        
        return sum(int(num) for num in stack)

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

⚡️Слита База из 1000+ топовых курсов и материалов для айтишников 🖥 Python: @python_baza 👩‍💻 Frontend: @frontend_baza 👩‍💻 Backend: @backend_baza 🎨 Дизайн: @design_baza 📚 Книги: @archive_baza 👩‍💻 Топ GitHub: @main_it_baza Всё лучшее про IT бесплатно — уже на Базе 🚀

Курс "Дизайн карточек для WB и Ozon". Бесплатно и с нуля Дизайнер карточек для маркетплейсов — востребованная и доходная профессия 💰 Научись ей бесплатно! - Бесплатный доступ к курсу - Разбор ДЗ от наставника - Мощные кейсы в портфолио Узнать больше #реклама 16+ yudaevschool24.online О рекламодателе

#medium Задача: 487. Max Consecutive Ones II Дан бинарный массив nums, верните максимальное количество последовательных единиц в массиве, если можно перевернуть не более одного нуля. Пример:

Input: nums = [1,0,1,1,0]
Output: 4
Explanation: 
- If we flip the first zero, nums becomes [1,1,1,1,0] and we have 4 consecutive ones.
- If we flip the second zero, nums becomes [1,0,1,1,1] and we have 3 consecutive ones.
The max number of consecutive ones is 4.

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

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        longestSequence = 0
        for left in range(len(nums)):
            numZeroes = 0
            for right in range(left, len(nums)):
                if nums[right] == 0:
                    numZeroes += 1
                if numZeroes <= 1:
                    longestSequence = max(longestSequence, right - left + 1)
        return longestSequence

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

Запустить рекламу в Telegram можно от 500 €. Это можно сделать с крупнейшим селлером Telegram Ads — Magnetto.pro. Это международное digital-агентство,которое: - Работает с Telegram Ads с момента появления платформы - Ведет прямой диалог с командой сервиса - Имеет экспертизу во всех современных бизнес-нишах Преимущества рекламы с Magnetto.pro: - Качественный трафик без ботов - Оперативная премодерация объектов рекламы - Оплата без наценки за курс евро–рубль Начать сотрудничество с агентством можно в двух форматах. - Full service: все задачи на себя берет Magnetto.pro. А вы держите руку на пульсе с помощью персонального менеджера и расширенного отчета по кампаниям. - Self service: вы работаете сами, но получаете доступ к кабинету и дополнительные возможности. Получить предложение #реклама magnetto.pro О рекламодателе

#medium Задача: 771. Jewels and Stones Вам даны строки jewels, представляющие типы камней, которые являются драгоценностями, и stones, представляющие камни, которые у вас есть. Каждый символ в stones является типом камня, который у вас есть. Вы хотите узнать, сколько из камней, которые у вас есть, также являются драгоценностями. Буквы чувствительны к регистру, поэтому "a" считается другим типом камня, чем "A". Пример:

Input: jewels = "aA", stones = "aAAbbbb"
Output: 3

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

class Solution:
    def numJewelsInStones(self, J: str, S: str) -> int:
        ans = 0
        for s in S:
            for j in J:
                if j == s:
                    ans += 1
                    break
        return ans

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

Целевые кибератаки 2024: аналитика и кейсы На вебинаре 27 февраля команда Solar 4RAYS подведет итоги по следам расследований целевых атак 2024 года Вы узнаете, как профессиональные хакеры атакуют российские компании и обходят системы безопасности, когда защита не соответствует уровню угроз. А также какие тактики используют киберпреступники, каков конечный импакт для систем ИБ от воздействия хакеров и как выстроить стратегию защиты. Что будет на вебинаре: - Какие инструменты противодействия актуальны в 2025 году; - Какие отрасли бизнеса подвергались атакам и с какой целью; - Какие интересные техники использовали злоумышленники: разбор кейсов расследований. Все примеры и рекомендации основаны на реальных расследованиях инцидентов в российских организациях. Зарегистрироваться #реклама 16+ rt-solar.ru О рекламодателе

#medium Задача: 714. Best Time to Buy and Sell Stock with Transaction Fee Вам дан массив prices, где prices[i] - это цена данной акции в i-й день, и целое число fee, представляющее собой комиссию за сделку. Найдите максимальную прибыль, которую вы можете получить. Вы можете совершить сколько угодно сделок, но за каждую сделку вам придется заплатить комиссию. Примечание: Вы не можете совершать несколько сделок одновременно (то есть вы должны продать акции, прежде чем купить их снова). Комиссия за сделку взимается только один раз за каждую покупку и продажу акций. Пример:

Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8

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

def maxProfit(prices, fee):
    cash, hold = 0, -prices[0]
    for price in prices:
        cash = max(cash, hold + price - fee)
        hold = max(hold, cash - price)
    return cash

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

Квартиры в ЖК SOKOLNIKI! Рассрочка до 2,5 лет, ПВ от 10% Видовые квартиры бизнес+ класса возле парка от 28 м² от 400 000 руб./м² Первый взнос от 10% Гибкие программы рассрочки до 2,5х лет с переходом в ипотеку Квартиры от 28м² до 135м² От студий до семейных фоматов с большими гостиными Колясочные на этаже Все для удобства родителей Дизайнерские лобби Стильные входные группы Подземный паркинг Системы хранения велосипедов и самокатов Детский сад Закрытая территория Девелопер STONE 18 лет на рынке недвижимости. 27 проектов м. "Сокольники", 12 мин. от парка Перейти на сайт Проектная декларация на сайте https://наш.дом.рф/. Застройщик: ООО СЗ «КВАРТАЛ СОКОЛЬНИКИ». Финансовые услуги оказывает: ПАО "Совкомбанк". #реклама stone-sokolniki.ru О рекламодателе

#medium Задача: 713. Subarray Product Less Than K Если задан массив целых чисел nums и целое число k, верните количество смежных подмассивов, в которых произведение всех элементов в подмассиве строго меньше k. Пример:

Input: nums = [10,5,2,6], k = 100
Output: 8

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

def numSubarrayProductLessThanK(nums, k):
    if k <= 1:
        return 0
    product = 1
    count = 0
    left = 0
    for right in range(len(nums)):
        product *= nums[right]
        while product >= k:
            product //= nums[left]
            left += 1
        count += right - left + 1
    return count

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

Все новости из мира программирования на этом канале @umnyiprogrammist Подписывайтесь, чтобы не упустите ничего важного Ставь 👍 и забирай 📚 Базу знаний

Онлайн-интенсив для ИТ-специалистов в Открытых школах Т1 Уже есть опыт работы в ИТ, но хочешь прокачать скилы и продвинуться в карьере? Тогда скорее залетай на бесплатный ИТ-интенсив в Открытых школах Т1. Открытые школы — это возможность усилить свои навыки и получить оффер в ИТ-холдинг Т1. И все это за месяц, онлайн и в удобное вечернее время. Что ты получишь? ✅ бесплатное обучение в гибком формате: по вечерам, онлайн, из любого города РФ и РБ. ✅ материалы от HR для прокачки резюме и подготовки к интервью в Т1. ✅ много практики и уникальный рыночный опыт. ✅ поддержку опытных преподавателей и карьерный фаст-трек до мидла в Т1 для лучших выпускников. ✅ реальный шанс получить оффер в Т1. Более 1000 специалистов уже прошли этот путь — теперь твоя очередь! Регистрация до 14 марта! Подать заявку #реклама 16+ t1.ru О рекламодателе

#medium Задача: 767. Reorganize String Дана строка s, переставьте символы строки s так, чтобы любые два соседних символа не были одинаковыми. Верните любую возможную перестановку строки s или верните "", если это невозможно. Пример:

Input: s = "aab"
Output: "aba"

👨‍💻 Алгоритм: 1⃣Инициализируйте пустой список ans для хранения переставленных символов. Создайте приоритетную очередь pq, используя структуру данных кучи. Каждый элемент в pq — это кортеж, содержащий количество символов и сам символ. Приоритетная очередь упорядочена так, что элементы с большим количеством имеют более высокий приоритет. 2⃣Извлеките элемент с наивысшим приоритетом из pq. Присвойте его количество и символ переменным count_first и char_first соответственно. Если ans пуст или текущий символ char_first отличается от последнего символа в ans, добавьте char_first в ans. Если количество char_first не равно нулю, уменьшите его на один. Если обновленное количество больше нуля, поместите его обратно в pq. Перейдите к следующей итерации. 3⃣В противном случае, если char_first совпадает с последним символом в ans, нужно выбрать другой символ. Если pq пуста, верните пустую строку, так как переставить символы невозможно. Извлеките следующий элемент из pq, присвоив его количество и символ переменным count_second и char_second соответственно. Добавьте char_second в ans. Если количество char_second не равно нулю, уменьшите его на один. Если обновленное количество больше нуля, поместите его обратно в pq. Наконец, поместите оригинальный char_first обратно в pq. Верните переставленные символы как строку, объединив элементы в ans. 😎 Решение:

import heapq

class Solution:
    def reorganizeString(self, s: str) -> str:
        charCounts = [0] * 26
        for c in s:
            charCounts[ord(c) - ord('a')] += 1
        
        pq = []
        for i in range(26):
            if charCounts[i] > 0:
                heapq.heappush(pq, (-charCounts[i], chr(i + ord('a'))))
        
        result = []
        while pq:
            first = heapq.heappop(pq)
            if not result or first[1] != result[-1]:
                result.append(first[1])
                if -first[0] > 1:
                    heapq.heappush(pq, (first[0] + 1, first[1]))
            else:
                if not pq:
                    return ""
                second = heapq.heappop(pq)
                result.append(second[1])
                if -second[0] > 1:
                    heapq.heappush(pq, (second[0] + 1, second[1]))
                heapq.heappush(pq, first)
        
        return "".join(result)

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

Прокачаем ваш скилл по Java с junior до middle Научим писать код, который не стыдно показать Личный наставник. Актуальная программа. Попробуй! Узнать больше #реклама 16+ ykul.ru О рекламодателе

#medium Задача: 712. Minimum ASCII Delete Sum for Two Strings Если даны две строки s1 и s2, верните наименьшую ASCII-сумму удаленных символов, чтобы сделать две строки равными. Пример:

Input: s1 = "sea", s2 = "eat"
Output: 231

👨‍💻 Алгоритм: 1⃣Создайте двумерный массив dp размером (len(s1) + 1) x (len(s2) + 1), где dp[i][j] будет хранить наименьшую ASCII-сумму удаленных символов для первых i символов s1 и первых j символов s2. 2⃣Заполните первую строку и первый столбец массива dp суммами ASCII значений символов, которые необходимо удалить для достижения пустой строки. 3⃣Заполните оставшуюся часть массива dp следующим образом: Если символы s1[i-1] и s2[j-1] равны, dp[i][j] = dp[i-1][j-1]. Иначе, dp[i][j] = min(dp[i-1][j] + ord(s1[i-1]), dp[i][j-1] + ord(s2[j-1])). 😎 Решение:

def minimumDeleteSum(s1, s2):
    dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]
    for i in range(1, len(s1) + 1):
        dp[i][0] = dp[i - 1][0] + ord(s1[i - 1])
    for j in range(1, len(s2) + 1):
        dp[0][j] = dp[0][j - 1] + ord(s2[j - 1])
    for i in range(1, len(s1) + 1):
        for j in range(1, len(s2) + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = min(dp[i - 1][j] + ord(s1[i - 1]), dp[i][j - 1] + ord(s2[j - 1]))
    return dp[-1][-1]

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

Ищу работу пол года Практически под каждым постом в этом канале я вижу комментарии от людей, которые ищут работу по полгода. Это перерастает в обсуждение того, как нужно (или не нужно) искать работу, почему процесс найма сломан и как они откликались на фейковые вакансии. Честно говоря, искать работу полгода — это нонсенс. Очевидно, что человек делает что-то не так. Главная ошибка, которую совершают многие, — это создание иллюзии поиска работы. То есть человек вроде бы ищет работу, но делает это неэффективно, тратя время на нецелевые действия. Например: ➖ Просматривает вакансии перед откликом. ➖ Пытается понять, подходит ли он под вакансию. Если считает, что не подходит — не откликается. ➖ Пишет сопроводительные письма (иногда даже уникальные под каждую вакансию). ➖ Заполняет анкеты, проходит тесты. Все эти действия отнимают время, но не приводят к результату. Почему это не работает? HR-менеджер не может вручную отсмотреть 2000 откликов, оценить каждое резюме и прочитать сопроводительные письма. Поэтому компании используют ATS-системы (системы автоматического подбора), которые анализируют резюме и определяют процент его соответствия вакансии. Что делать, чтобы повысить шансы? 1️⃣ Добавить ключевые навыки в резюме — и в основной текст, и в теги. Возьмите их с easyoffer.ru 2️⃣ Убрать нерелевантный опыт, оставить только подходящий. 3️⃣ Оформить опыт так, чтобы он выглядел релевантным. Если у вас его нет, укажите проекты, стажировки или другой опыт, который можно представить как работу от 1 года. Если опыт слишком большой, сузьте его до 6 лет. 4️⃣ Откликаться на все вакансии без разбору. Если вы Junior, не ищите только стажер или Junior-вакансии — пробуйте везде. Не отказывайте себе сами, пусть это решит HR 5️⃣ Сделать резюме публичным, потому что HR-менеджеры часто ищут кандидатов не только среди откликов, но и в базе резюме. 6️⃣ Используйте ИИ по минимуму – ATS-системы считывают это и помечают "сгенерировано ИИ" ‼️ Главное правило: чем больше откликов — тем выше шанс получить оффер. Делайте резюме удобным для ATS-систем, и вас заметят. 1. Посмотрите видео о том как я вывел свою резюме в Топ1 на HH 2. Посмотрите видео как я нашел первую работу 3. Прочитайте этот кейс про оптимизацию резюме Если прям вообще тяжело. Создайте несколько разных резюме. Создайте 2, 3 да хоть 10 резюме. Настройте авто-отлики и ждите приглашения на собесы. Не нужно создавать иллюзию поиска работы, сделайте несколько простых и актуальных действий.

#easy Задача: 766. Toeplitz Matrix Дана матрица размером m x n. Вернуть true, если матрица является Тёплицевой. В противном случае вернуть false. Матрица является Тёплицевой, если все диагонали, идущие от верхнего левого к нижнему правому углу, содержат одинаковые элементы. Пример:

Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: true
Explanation:
In the above grid, the diagonals are:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".
In each diagonal all elements are the same, so the answer is True.

👨‍💻 Алгоритм: 1⃣Что отличает две координаты (r1, c1) и (r2, c2) на одной диагонали? Оказывается, две координаты находятся на одной диагонали тогда и только тогда, когда r1 - c1 == r2 - c2.м 2⃣Это приводит к следующей идее: запоминайте значение этой диагонали как groups[r - c]. Если обнаружено несоответствие, то матрица не является Тёплицевой; в противном случае, она является таковой. 3⃣Таким образом, для каждой ячейки матрицы сохраняйте значение диагонали в словаре groups с ключом r - c. Проходите по всем ячейкам матрицы и проверяйте, совпадает ли текущее значение с сохранённым в groups. Если где-то обнаруживается несоответствие, верните false. Если все элементы соответствуют, верните true. 😎 Решение:

class Solution:
    def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
        groups = {}
        for r in range(len(matrix)):
            for c in range(len(matrix[0])):
                if (r - c) not in groups:
                    groups[r - c] = matrix[r][c]
                elif groups[r - c] != matrix[r][c]:
                    return False
        return True

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

#hard Задача: 765. Couples Holding Hands Есть n пар, сидящих на 2n местах, расположенных в ряд, и они хотят держаться за руки. Люди и места представлены массивом целых чисел row, где row[i] — это ID человека, сидящего на i-м месте. Пары пронумерованы по порядку: первая пара — (0, 1), вторая пара — (2, 3) и так далее, до последней пары — (2n - 2, 2n - 1). Верните минимальное количество перестановок, чтобы каждая пара сидела рядом. Перестановка состоит из выбора любых двух человек, которые встают и меняются местами. Пример:

Input: row = [0,2,1,3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

👨‍💻 Алгоритм: 1⃣Мы могли бы предположить без доказательства, что решение, при котором мы делаем людей на каждом диване счастливыми по порядку, является оптимальным. Это предположение сильнее, чем гипотеза о жадном подходе, но кажется разумным, поскольку при каждом ходе мы делаем хотя бы одну пару счастливой. 2⃣При таком предположении, для какого-то дивана с несчастливыми людьми X и Y, мы либо заменяем Y на партнера X, либо заменяем X на партнера Y. Для каждой из двух возможностей мы можем попробовать оба варианта, используя подход с возвратом. 3⃣Для каждого дивана с двумя возможностями (т.е. оба человека на диване несчастливы) мы попробуем первый вариант, найдем ответ как ans1, затем отменим наш ход и попробуем второй вариант, найдем связанный ответ как ans2, отменим наш ход и затем вернем наименьший ответ. 😎 Решение:

class Solution:
    def minSwapsCouples(self, row: List[int]) -> int:
        self.N = len(row) // 2
        self.pairs = [[0, 0] for _ in range(self.N)]
        for i in range(self.N):
            self.pairs[i][0] = row[2 * i] // 2
            self.pairs[i][1] = row[2 * i + 1] // 2
        return self.solve(0)
    
    def swap(self, a: int, b: int, c: int, d: int):
        self.pairs[a][b], self.pairs[c][d] = self.pairs[c][d], self.pairs[a][b]
    
    def solve(self, i: int) -> int:
        if i == self.N:
            return 0
        x, y = self.pairs[i]
        if x == y:
            return self.solve(i + 1)
        
        jx, kx, jy, ky = 0, 0, 0, 0
        for j in range(i + 1, self.N):
            for k in range(2):
                if self.pairs[j][k] == x:
                    jx, kx = j, k
                if self.pairs[j][k] == y:
                    jy, ky = j, k
        
        self.swap(i, 1, jx, kx)
        ans1 = 1 + self.solve(i + 1)
        self.swap(i, 1, jx, kx)
        
        self.swap(i, 0, jy, ky)
        ans2 = 1 + self.solve(i + 1)
        self.swap(i, 0, jy, ky)
        
        return min(ans1, ans2)

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

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

#hard Задача: 711. Number of Distinct Islands II Вам дана двоичная матричная сетка m x n. Остров - это группа 1 (представляющая сушу), соединенных в четырех направлениях (горизонтальном или вертикальном). Можно предположить, что все четыре края сетки окружены водой. Остров считается одинаковым с другим, если они имеют одинаковую форму, или имеют одинаковую форму после поворота (только на 90, 180 или 270 градусов) или отражения (влево/вправо или вверх/вниз). Верните количество разных островов. Пример:

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

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

def numDistinctIslands2(grid):
    def dfs(i, j):
        shape = []
        stack = [(i, j)]
        while stack:
            x, y = stack.pop()
            if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] == 1:
                grid[x][y] = 0
                shape.append((x - i, y - j))
                stack.extend([(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)])
        return shape

    def normalize(shape):
        shapes = [[] for _ in range(8)]
        for x, y in shape:
            shapes[0].append((x, y))
            shapes[1].append((x, -y))
            shapes[2].append((-x, y))
            shapes[3].append((-x, -y))
            shapes[4].append((y, x))
            shapes[5].append((y, -x))
            shapes[6].append((-y, x))
            shapes[7].append((-y, -x))
        for s in shapes:
            s.sort()
        return min(shapes)

    unique_islands = set()
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == 1:
                shape = dfs(i, j)
                unique_islands.add(tuple(normalize(shape)))

    return len(unique_islands)

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