Python | LeetCode

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

📺 Уникальная база IT собеседований 456+ реальных собеседований на программиста, тестировщика, аналитика и прочие IT профы. Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д. 🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!

Задача: 318. Maximum Product of Word Lengths Сложность: medium Дан массив строк words, верните максимальное значение произведения длины word[i] на длину word[j], где два слова не имеют общих букв. Если таких двух слов не существует, верните 0. Пример:

Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".

👨‍💻 Алгоритм: 1⃣Предварительная обработка масок и длин Вычислите битовые маски для всех слов и сохраните их в массиве masks. Сохраните длины всех слов в массиве lens. 2⃣Сравнение слов и проверка общих букв Сравните каждое слово с каждым последующим словом. Если два слова не имеют общих букв (проверка с использованием масок: (masks[i] & masks[j]) == 0), обновите максимальное произведение maxProd. 3⃣Возврат результата Верните максимальное значение произведения maxProd. 😎 Решение:

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        n = len(words)
        masks = [0] * n
        lens = [0] * n
        bit_number = lambda ch : ord(ch) - ord('a')
        
        for i in range(n):
            bitmask = 0
            for ch in words[i]:
                bitmask |= 1 << bit_number(ch)
            masks[i] = bitmask
            lens[i] = len(words[i])
            
        max_val = 0
        for i in range(n):
            for j in range(i + 1, n):
                if masks[i] & masks[j] == 0:
                    max_val = max(max_val, lens[i] * lens[j])
        return max_val

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

Получи грант на обучение в Центральном университете Прояви себя, получи грант до 2,8 млн на обучение ИТ и бизнесу в вузе. Для школьников 10-х и 11-х классов, СПО. Подать заявку #реклама apply.centraluniversity.ru О рекламодателе

Задача: 690. Employee Importance Сложность: medium У вас есть структура данных с информацией о сотрудниках, включая уникальный идентификатор сотрудника, значение его важности и идентификаторы его прямых подчиненных. Вам дан массив сотрудников employees, где: employees[i].id — это идентификатор i-го сотрудника. employees[i].importance — значение важности i-го сотрудника. employees[i].subordinates — список идентификаторов прямых подчиненных i-го сотрудника. Дан целочисленный id, представляющий идентификатор сотрудника. Верните суммарное значение важности этого сотрудника и всех его прямых и косвенных подчиненных. Пример:

Input: employees = [[1,5,[2,3]],[2,3,[]],[3,3,[]]], id = 1
Output: 11
Explanation: Employee 1 has an importance value of 5 and has two direct subordinates: employee 2 and employee 3.
They both have an importance value of 3.
Thus, the total importance value of employee 1 is 5 + 3 + 3 = 11.

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

class Employee:
    def __init__(self, id: int, importance: int, subordinates: List[int]):
        self.id = id
        self.importance = importance
        self.subordinates = subordinates

class Solution:
    def getImportance(self, employees: List[Employee], queryid: int) -> int:
        emap = {e.id: e for e in employees}
        return self.dfs(queryid, emap)

    def dfs(self, eid: int, emap: Dict[int, Employee]) -> int:
        employee = emap[eid]
        ans = employee.importance
        for subid in employee.subordinates:
            ans += self.dfs(subid, emap)
        return ans

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

Сколько приложений нужно вашей команде для работы? Всего один сервис — Битрикс24! А внутри десятки инструментов для совместной работы и бизнеса. Читайте подробнее в карточках. Регистрируйтесь сейчас, чтобы забрать их все себе бесплатно😊 Зарегистрироваться #реклама 16+ office-online.bitrix24.ru О рекламодателе

Задача: 173. Binary Search Tree Iterator Сложность: medium Реализуйте класс BSTIterator, который представляет итератор по обходу бинарного дерева поиска (BST) в порядке in-order: BSTIterator(TreeNode root): Инициализирует объект класса BSTIterator. Корень BST передается в качестве параметра конструктора. Указатель должен быть инициализирован на несуществующее число, меньшее любого элемента в BST. boolean hasNext(): Возвращает true, если в обходе справа от указателя существует число, иначе возвращает false. int next(): Перемещает указатель вправо, затем возвращает число на указателе. Обратите внимание, что при инициализации указателя на несуществующее наименьшее число, первый вызов next() вернет наименьший элемент в BST. Можно предположить, что вызовы next() всегда будут допустимы. То есть, при вызове next() в обходе всегда будет хотя бы одно следующее число. Пример:

Input
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output
[null, 3, 7, true, 9, true, 15, true, 20, false]

Explanation
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next();    // return 3
bSTIterator.next();    // return 7
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 9
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 15
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 20
bSTIterator.hasNext(); // return False

👨‍💻 Алгоритм: 1️⃣Инициализируйте пустой массив, который будет содержать узлы бинарного дерева поиска в отсортированном порядке. 2️⃣Мы обходим бинарное дерево поиска в порядке in-order и для каждого узла, который обрабатываем, добавляем его в наш массив узлов. Обратите внимание, что перед обработкой узла сначала нужно обработать (или рекурсивно вызвать) его левое поддерево, а после обработки узла — его правое поддерево. 3️⃣Когда у нас будут все узлы в массиве, нам просто нужен указатель или индекс в этом массиве для реализации двух функций next и hasNext. Всякий раз, когда вызывается hasNext, мы просто проверяем, достиг ли индекс конца массива или нет. При вызове функции next мы просто возвращаем элемент, на который указывает индекс. Также, после вызова функции next, мы должны переместить индекс на один шаг вперед, чтобы имитировать прогресс нашего итератора. 😎 Решение:

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

class BSTIterator:
    def __init__(self, root: TreeNode):
        self.nodes_sorted = []
        self.index = -1
        self._inorder(root)

    def _inorder(self, root: TreeNode) -> None:
        if not root:
            return
        self._inorder(root.left)
        self.nodes_sorted.append(root.val)
        self._inorder(root.right)

    def next(self) -> int:
        self.index += 1
        return self.nodes_sorted[self.index]

    def hasNext(self) -> bool:
        return self.index + 1 < len(self.nodes_sorted)

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

Освойте профессию Системный аналитик с нуля за 7 месяцев Освойте высокооплачиваемую IT-профессию без программирования. Выдаём диплом, помогаем с трудоустройством. Excel, BPMN, UML, Python, SQL, API Преимущества обучения в Академии Eduson: 🎓 22 реальных бизнес-кейса 🎓 официальный государственный диплом 🎓 рассрочка 0% на 24 мес. 🎓 бессрочный доступ к лекциям и материалам, которые регулярно обновляются 🎓 личный куратор с Вами на связи Начните обучаться онлайн и получать доход уже во время обучения! Получить скидку #реклама 16+ mrqz.me О рекламодателе

Задача: 939. Minimum Area Rectangle Сложность: medium Дан массив точек в плоскости X-Y points, где points[i] = [xi, yi]. Верните минимальную площадь прямоугольника, образованного из этих точек, со сторонами, параллельными осям X и Y. Если такого прямоугольника не существует, верните 0. Пример:

Input: points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output: 4

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

def minAreaRect(points):
    point_set = set(map(tuple, points))
    min_area = float('inf')
    
    for i in range(len(points)):
        for j in range(i + 1, len(points)):
            x1, y1 = points[i]
            x2, y2 = points[j]
            if x1 != x2 and y1 != y2 and (x1, y2) in point_set and (x2, y1) in point_set:
                min_area = min(min_area, abs(x2 - x1) * abs(y2 - y1))
    
    return 0 if min_area == float('inf') else min_area

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

Профессия «Аналитик данных» - начни учиться бесплатно! Освойте высокооплачиваемую IT-профессию с нуля за 6 месяцев. Выдаём диплом, помогаем с трудоустройством. Excel, SQL, PowerBI, Python. Преимущества обучения в Академии Eduson: 🎓 можно начать учиться бесплатно, если не понравится — не платите 🎓 официальный государственный диплом 🎓 рассрочка 0% на 24 мес. 🎓 бессрочный доступ к лекциям и материалам, которые регулярно обновляются 🎓 личный куратор с Вами на связи Начните обучаться онлайн и получать стабильный доход уже во время обучения! Подать заявку #реклама 16+ eduson.academy О рекламодателе

Задача: 424. Longest Repeating Character Replacement Сложность: medium Вам дана строка s и целое число k. Вы можете выбрать любой символ строки и заменить его на любой другой заглавный английский символ. Вы можете выполнить эту операцию не более k раз. Верните длину самой длинной подстроки, содержащей одну и ту же букву, которую можно получить после выполнения вышеуказанных операций. Пример:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

👨‍💻 Алгоритм: 1⃣Определите диапазон поиска. Минимальная длина подстроки с одинаковыми символами всегда равна 1 (назовем ее min), а максимальная длина подстроки может быть равна длине данной строки (назовем ее max). Ответ будет лежать в диапазоне [min, max] (включительно). 2⃣Инициализируйте две переменные lo и hi для бинарного поиска. lo всегда указывает на длину допустимой строки, а hi - на недопустимую длину. Изначально lo равно 1, а hi равно max+1. 3⃣Выполните бинарный поиск, чтобы найти максимальное значение lo, которое представляет самую длинную допустимую подстроку. В конце lo будет содержать ответ, а hi будет на единицу больше lo. 😎 Решение:

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        lo, hi = 1, len(s) + 1

        while lo + 1 < hi:
            mid = lo + (hi - lo) // 2
            if self.canMakeValidSubstring(s, mid, k):
                lo = mid
            else:
                hi = mid

        return lo

    def canMakeValidSubstring(self, s: str, substringLength: int, k: int) -> bool:
        freqMap = [0] * 26
        maxFrequency = 0
        start = 0

        for end in range(len(s)):
            freqMap[ord(s[end]) - ord('A')] += 1

            if end + 1 - start > substringLength:
                freqMap[ord(s[start]) - ord('A')] -= 1
                start += 1

            maxFrequency = max(maxFrequency, freqMap[ord(s[end]) - ord('A')])
            if substringLength - maxFrequency <= k:
                return True

        return False

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

Радиаторы WARMMET прямо с завода с пожизненной гарантией Роскошь синего Синий — символ стабильности, уверенности и гармонии. Он помогает расслабиться, сосредоточиться и создает ощущение прохлады и свежести. В интерьере этот цвет идеально подходит для: ✨ Современных и классических гостиных, добавляя им благородства. ✨ Спален, где он создает атмосферу уюта и умиротворения. ✨ Кабинетов, способствуя концентрации и продуктивности. ✨ Ванных комнат, ассоциируясь с чистотой и водой. Оттенки синего: Ультрамарин — глубокий, насыщенный синий, придающий интерьеру выразительность. Синий сапфир — благородный и изысканный, добавляющий роскоши. Синий океан — легкий, свежий, напоминающий морские просторы. Синяя ночь — глубокий, создающий атмосферу уюта и расслабления. ⚡ Узнайте больше о дизайн-радиаторах WARMMET: Перейти на сайт #реклама warmmet.ru О рекламодателе

Задача: 713. Subarray Product Less Than K Сложность: medium Если задан массив целых чисел 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

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

5 свободных мест на курс Коммутаторы MES продвинутый Осталось 5 мест на курс Коммутаторы MES (продвинутый) в нашем авторизованном учебном центре от Академии Eltex в Москве Даты: 12-16 мая (5 дней) Другие курсы: Курс Wi-Fi (контроллер SoftWLC) 19 мая - 5 дней - Выдаем официальный сертификат Eltex. - Преподаватель корректирует программу обучения под Ваш уровень знаний. - Преподаватели прошли аттестацию на заводе Eltex. - Уже выпустили 210 сетевых инженеров! Записаться #реклама 16+ eltexcm.ru О рекламодателе

Задача: 1286. Iterator for Combination Сложность: medium Создайте класс CombinationIterator: CombinationIterator(string characters, int combinationLength) Инициализирует объект строкой characters, содержащей отсортированные различные строчные буквы английского алфавита, и числом combinationLength в качестве аргументов. next() Возвращает следующую комбинацию длины combinationLength в лексикографическом порядке. hasNext() Возвращает true, если и только если существует следующая комбинация. Пример:

Input
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
Output
[null, "ab", true, "ac", true, "bc", false]

Explanation
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next();    // return "ab"
itr.hasNext(); // return True
itr.next();    // return "ac"
itr.hasNext(); // return True
itr.next();    // return "bc"
itr.hasNext(); // return False

👨‍💻 Алгоритм: 1⃣Сгенерируйте все возможные бинарные битовые маски длины n: от 0 до 2^n - 1. 2⃣Используйте битовые маски с k установленными битами для генерации комбинаций из k элементов. Если n - 1 - j-й бит установлен в битовой маске, это указывает на присутствие символа characters[j] в комбинации и наоборот. 3⃣Теперь у вас есть все заранее вычисленные комбинации. Извлекайте их одну за другой по каждому запросу. 😎 Решение:

class CombinationIterator:
    def __init__(self, characters: str, combinationLength: int):
        self.combinations = []
        n, k = len(characters), combinationLength
        for bitmask in range(1 << n):
            if bin(bitmask).count('1') == k:
                curr = [characters[j] for j in range(n) if bitmask & (1 << n - j - 1)]
                self.combinations.append(''.join(curr))

    def next(self) -> str:
        return self.combinations.pop()

    def hasNext(self) -> bool:
        return self.combinations

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

Сегодня QA.GURU анонсировали закрытый вебинар «Как Python открывает новые горизонты в карьере тестировщика». Обещают последние тренды QA, блок с лайфкодингом и живую сессию вопросов. ▶ По этой ссылке можно зарегистрироваться для бесплатного участия в этот четверг в 8 вечера мск. В программе: — Зачем ручным тестировщикам разбираться в автоматизации и почему Python — оптимальный старт; — Какие навыки выводят QA в топ в 2025 году (спойлер: нейросети пока не конкуренты); — Практика: пишем ручной тест, автоматизируем на Python, сравниваем Playwright, Selenium и Selene, запускаем с Pytest и без. Спикер, Станислав Васенков — QA, за плечами которого больше 10 лет автоматизации, ex-Head of QAA pflb.ru и автор библиотеки allure-notifications. Победитель хакатона по автоматизации тестирования от EPAM. Организатор конференций, спикер Heisenbug, основатель QA.GURU и AUTOTESTS.AI. Стас знает, о чём говорит — и умеет научить. 🔗 Забирайте ссылку. Кто успеет — тот в игре.

Как девушке освоить профессию Data Scientist? ✅Диплом магистра МФТИ ✅DS, ML, AI, CV, NLP ✅Очное высшее — онлайн ✅Кредит от 337 р/мес Data Science, МФТИ — среда для профессионального и карьерного роста в IT! Записаться онлайн Изучите все условия кредита (займа) на сайте в соответствующем разделе. Оценивайте свои финансовые возможности и риски. Финансовые услуги оказывает: ПАО Сбербанк. #реклама 16+ mipt.online О рекламодателе

Задача: 673. Number of Longest Increasing Subsequence Сложность: medium Дан массив целых чисел nums, верните количество самых длинных строго возрастающих подпоследовательностей. Пример:

Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2

👨‍💻 Алгоритм: 1⃣Объявите два массива динамического программирования length и count, и инициализируйте их значениями length[i]=1 и count[i]=1. Итерируйте i от 0 до n−1. Для каждого i итерируйте j от 0 до i−1 и, если nums[j] < nums[i], обновите length[i] и count[i] в зависимости от значений length[j] и count[j]. 2⃣Найдите максимальное значение в массиве length и сохраните его в переменной maxLength. Инициализируйте переменную result = 0. 3⃣Итерируйте i от 0 до n−1 и, если length[i] = maxLength, добавьте count[i] к result. Верните result. 😎 Решение:

class Solution:
    def findNumberOfLIS(self, nums):
        n = len(nums)
        length = [1] * n
        count = [1] * n

        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    if length[j] + 1 > length[i]:
                        length[i] = length[j] + 1
                        count[i] = 0
                    if length[j] + 1 == length[i]:
                        count[i] += count[j]

        maxLength = max(length)
        result = 0

        for i in range(n):
            if length[i] == maxLength:
                result += count[i]

        return result

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

ИИ помогает менеджерам продавать больше! Битрикс24 CRM + Ai упрощает работу менеджера. Расшифровывает записи звонков клиентам и сам заполняет карточку сделки. Менеджер в это время уже звонит следующему клиенту. Попробуйте умную CRM Попробовать #реклама 16+ bitrix24.ru О рекламодателе

Задача: 587. Erect the Fence Сложность: hard Вам дан массив trees, где trees[i] = [xi, yi] представляет местоположение дерева в саду. Оградите весь сад с использованием минимальной длины веревки, так как это дорого. Сад хорошо огорожен только в том случае, если все деревья окружены. Верните координаты деревьев, которые находятся точно на периметре ограды. Вы можете вернуть ответ в любом порядке. Пример:

Input: trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
Output: [[1,1],[2,0],[4,2],[3,3],[2,4]]
Explanation: All the trees will be on the perimeter of the fence except the tree at [2, 2], which will be inside the fence.

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

class Solution:
    def orientation(self, p, q, r):
        return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])

    def outerTrees(self, points):
        points.sort(key=lambda x: (x[0], x[1]))
        hull = []

        for point in points:
            while len(hull) >= 2 and self.orientation(hull[-2], hull[-1], point) > 0:
                hull.pop()
            hull.append(point)

        hull.pop()

        for point in reversed(points):
            while len(hull) >= 2 and self.orientation(hull[-2], hull[-1], point) > 0:
                hull.pop()
            hull.append(point)

        return list(set(map(tuple, hull)))

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