Python | LeetCode

Задача: 43. Multiply Strings Сложность: hard Даны два неотрицательных целых числа num1 и num2, представленные в виде строк. Верните произведение num1 и num2, также представленное в виде строки. Примечание: Вы не должны использовать встроенную библиотеку BigInteger или прямо преобразовывать входные данные в целые числа. Пример:

Input: num1 = "2", num2 = "3"
Output: "6"

👨‍💻 Алгоритм: 1️⃣Переверните оба числа. Инициализируйте массив ans с (N+M) нулями. Для каждой цифры в secondNumber: Инициализируйте переменную carry, первоначально равную 0. Инициализируйте массив (currentResult), который начинается с некоторого количества нулей, основываясь на позиции цифры в secondNumber. 2️⃣Для каждой цифры в firstNumber: Умножьте цифру из secondNumber на цифру из firstNumber и добавьте предыдущий carry к умножению. Возьмите остаток от деления умножения на 10, чтобы получить последнюю цифру. Добавьте последнюю цифру в массив currentResult. Разделите умножение на 10, чтобы получить новое значение для carry. 3️⃣После итерации по каждой цифре в первом числе, если carry не равен нулю, добавьте carry в currentResult. Добавьте currentResult к ans. Если последняя цифра в ans равна нулю, перед тем как перевернуть ans, необходимо удалить ноль из ans. В противном случае в финальном ответе будет ведущий ноль. Переверните ans и верните его. 😎 Решение:

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":
            return "0"

        first_number = num1[::-1]
        second_number = num2[::-1]

        N = len(first_number) + len(second_number)
        answer = [0] * N

        for index, digit in enumerate(second_number):
            answer = self.addStrings(
                self.multiplyOneDigit(first_number, digit, index), answer
            )

        if answer[-1] == 0:
            answer.pop()

        answer.reverse()
        return "".join(str(digit) for digit in answer)

    def multiplyOneDigit(self, first_number: str, digit2: str, num_zeros: int):
        currentResult = [0] * num_zeros
        carry = 0

        for digit1 in first_number:
            multiplication = int(digit1) * int(digit2) + carry
            carry = multiplication // 10
            currentResult.append(multiplication % 10)

        if carry != 0:
            currentResult.append(carry)
        return currentResult

    def addStrings(self, result: list, answer: list) -> list:
        carry = 0
        new_answer = []
        for digit1, digit2 in zip_longest(result, answer, fillvalue=0):
            curr_sum = digit1 + digit2 + carry
            carry = curr_sum // 10
            new_answer.append(curr_sum % 10)

        return new_answer

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

Курс по мотивации сотрудников, которые ничего не хотят Сегодня в Школе Гендира открыт бесплатный трехдневный доступ к онлайн-курсу Ежедневная мотивация. Основа курса – практика руководителей российских компаний. После обучения вы сможете: 👍 распознавать конфликты в коллективе на начальной стадии и вовремя принимать меры 👍 определить точки роста своего лидерского потенциала 👍 построить систему грейдов в компании 👍 внедрить метод OKR для мотивации ключевых сотрудников 👍 адаптировать для себя один из алгоритмов постановки задач Оставьте заявку на бесплатный доступ на странице курса. Подать заявку #реклама 16+ gd.ru О рекламодателе

Задача: 976. Largest Perimeter Triangle Сложность: easy Дан целочисленный массив nums. Верните наибольший периметр треугольника с ненулевой площадью, образованный из трех этих длин. Если невозможно образовать треугольник с ненулевой площадью, верните 0. Пример:

Input: nums = [1,2,1,10]
Output: 0
Explanation: 
You cannot use the side lengths 1, 1, and 2 to form a triangle.
You cannot use the side lengths 1, 1, and 10 to form a triangle.
You cannot use the side lengths 1, 2, and 10 to form a triangle.
As we cannot use any three side lengths to form a triangle of non-zero area, we return 0.

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

class Solution:
    def largestPerimeter(self, A: List[int]) -> int:
        A.sort()
        for i in range(len(A) - 3, -1, -1):
            if A[i] + A[i + 1] > A[i + 2]:
                return A[i] + A[i + 1] + A[i + 2]
        return 0

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

Крупнейший университет искусственного интеллекта Временные ряды — это данные, упорядоченные во времени, например, трафик на дорогах, изменения температуры или спрос на товары. С помощью AI можно предсказывать тренды, выявлять аномалии и оптимизировать процессы. Получите полный доступ к курсу по временным рядам на сайте. Это абсолютно бесплатно. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя среди наших студентов! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

На easyoffer 2.0 появится: Тренажер "Реальное собеседование" 🟠 Сценарии вопросов из реального собеседования 🟠Возможность подготовиться к собеседованию в конкретную компанию 🟠Итоговая статистика (прошёл/не прошёл) Сценарий вопросов взят из реального собеседования. То есть вы тренируетесь на тех вопросах, которые действительно задавались в компании X. Уже в начале следующей недели стартует краудфандинг кампания, чтобы ускорить разработку easyoffer 2.0. Все кто, поддержал проект на этом этапе смогу получить 1 год доступа к сайту по цене месячной подписки. Первые 150 донатеров получать особо-выгодную цену и бонус. Следите за стартом 👉 в этом телеграм канале, в нем информация о старте будет опубликована за 6 часов до официального начала.

Задача: 1802. Maximum Value at a Given Index in a Bounded Array Сложность: medium Даны три положительных целых числа: n, index и maxSum. Вам нужно построить массив nums (индексация с нуля), который удовлетворяет следующим условиям: - nums.length == n - nums[i] является положительным целым числом, где 0 <= i < n. - abs(nums[i] - nums[i+1]) <= 1, где 0 <= i < n-1. - Сумма всех элементов массива nums не превышает maxSum. - nums[index] максимально возможен. Верните значение nums[index] в построенном массиве. Обратите внимание, что abs(x) равно x, если x >= 0, и -x в противном случае. Пример:

Input: n = 4, index = 2,  maxSum = 6
Output: 2

👨‍💻 Алгоритм: 1⃣Определите функцию getSum(index, value) для вычисления минимальной суммы массива при условии, что nums[index] = value. 2⃣Инициализируйте диапазон поиска [left, right] значениями left = 1 и right = maxSum. Выполните бинарный поиск: вычислите mid = (left + right + 1) / 2 и проверьте, если getSum(index, mid) <= maxSum. Если условие выполняется, установите left = mid, иначе установите right = mid - 1. 3⃣Верните left по завершении бинарного поиска. 😎 Решение:

class Solution:
    def getSum(self, index: int, value: int, n: int) -> int:
        count = 0
        if value > index:
            count += (value + value - index) * (index + 1) // 2
        else:
            count += (value + 1) * value // 2 + index - value + 1
        if value >= n - index:
            count += (value + value - n + 1 + index) * (n - index) // 2
        else:
            count += (value + 1) * value // 2 + n - index - value
        return count - value

    def maxValue(self, n: int, index: int, maxSum: int) -> int:
        left, right = 1, maxSum
        while left < right:
            mid = (left + right + 1) // 2
            if self.getSum(index, mid, n) <= maxSum:
                left = mid
            else:
                right = mid - 1
        return left

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

⚡️ Айтишник из «VISION» скупил курсы айти школ и выложил гигабайты материалов к себе Каждый найдет что-то по душе: 1202 ГБ — Python 1811 ГБ — Frontend 1100 ГБ — C / C++ / C# 804 ГБ — Java 411 ГБ — SQL & БД 309 ГБ — DevOps 998 ГБ — ИБ & Хакинг 773 ГБ — Kotlin / Swift 189 ГБ — PHP 201 ГБ — GoLang 170 ГБ — Rust 167 ГБ — QA / Тестирование 310 ГБ — 1C + Лицензии 495 ГБ — Машинное обучение 704 ГБ — Аналитика Данных 991 ГБ — Дизайн Материалы в закрепе, постоянно пополняются👆🏻

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

Задача: 851. Loud and Rich Сложность: medium Есть группа из n человек, пронумерованных от 0 до n - 1, где у каждого человека разное количество денег и разный уровень спокойствия. Вам дан массив richer, где richer[i] = [ai, bi] указывает на то, что ai имеет больше денег, чем bi, и целочисленный массив quiet, где quiet[i] — это уровень спокойствия i-го человека. Все данные в richer логически корректны (т.е. данные не приведут к ситуации, где x богаче y и y богаче x одновременно). Верните целочисленный массив answer, где answer[x] = y, если y — это самый спокойный человек (то есть человек y с наименьшим значением quiet[y]) среди всех людей, которые однозначно имеют столько же или больше денег, чем человек x. Пример:

Input: richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
Output: [5,5,2,5,4,5,6,7]
Explanation: 
answer[0] = 5.
Person 5 has more money than 3, which has more money than 1, which has more money than 0.
The only person who is quieter (has lower quiet[x]) is person 7, but it is not clear if they have more money than person 0.
answer[7] = 7.
Among all people that definitely have equal to or more money than person 7 (which could be persons 3, 4, 5, 6, or 7), the person who is the quietest (has lower quiet[x]) is person 7.
The other answers can be filled out with similar reasoning.

👨‍💻 Алгоритм: 1⃣Постройте граф, описанный выше, и пусть dfs(person) будет самым спокойным человеком в поддереве person. Обратите внимание, что из-за логической последовательности утверждений граф должен быть DAG — ориентированным графом без циклов. 2⃣Теперь dfs(person) — это либо сам person, либо min(dfs(child) для каждого child из person). То есть, самый спокойный человек в поддереве — это либо сам person, либо самый спокойный человек в каком-то поддереве потомка person. 3⃣Мы можем кэшировать значения dfs(person) в answer[person], выполняя обход графа в пост-обходе. Таким образом, мы не повторяем работу. Этот метод уменьшает квадратичное время выполнения алгоритма до линейного. 😎 Решение:

class Solution {
    private lateinit var graph: Array<MutableList<Int>>
    private lateinit var answer: IntArray
    private lateinit var quiet: IntArray

    fun loudAndRich(richer: Array<IntArray>, quiet: IntArray): IntArray {
        val N = quiet.size
        graph = Array(N) { mutableListOf() }
        answer = IntArray(N) { -1 }
        this.quiet = quiet

        for (edge in richer) {
            graph[edge[1]].add(edge[0])
        }

        for (node in 0 until N) {
            dfs(node)
        }
        return answer
    }

    private fun dfs(node: Int): Int {
        if (answer[node] == -1) {
            answer[node] = node
            for (child in graph[node]) {
                val cand = dfs(child)
                if (quiet[cand] < quiet[answer[node]]) {
                    answer[node] = cand
                }
            }
        }
        return answer[node]
    }
}

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

На easyoffer 2.0 появится новый раздел: Задачи с собеседований 🟠Задачи на Алгоритмические, Live-coding и System Design из реальных собеседований 🟠Вероятность встретить ту или иную задачу 🟠Возможность подготовиться к задачам конкретной компании Есть много сайтов, на которых можно тренироваться решать задачи, но у них у всех одна проблема – сами задачи люди просто выдумывают. На easyoffer 2.0 вы сможете готовиться к live-coding и system design секциям на основе задач из реальных собеседований. Вы можете найдете самые частые задачи и сделаете упор на их решение. Считаные дни остались до старта краудфандинговой кампании, чтобы ускорить разработку easyoffer 2.0. Все кто, поддержал проект на этом этапе смогу получить 1 год доступа к сайту по цене месячной подписки, а те кто поддержат проект раньше других ито дешевле + получат существенный бонус. Следите за стартом 👉 в этом телеграм канале.

Крупнейший университет искусственного интеллекта Приглашаем на бесплатный однодневный интенсив по AI! Освой искусственный интеллект для профессионального роста: создавай нейросети, автоматизируй бизнес-задачи и зарабатывай на AI-решениях. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя в наших рядах! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

#hard Задача: 759. Employee Free Time Нам дан список schedule of employees, который представляет собой рабочее время каждого сотрудника. У каждого сотрудника есть список непересекающихся интервалов, и эти интервалы расположены в отсортированном порядке. Верните список конечных интервалов, представляющих общее свободное время положительной длины для всех сотрудников, также в отсортированном порядке. (Хотя мы представляем интервалы в форме [x, y], объекты внутри них являются интервалами, а не списками или массивами. Например, schedule[0][0].start = 1, schedule[0][0].end = 2, а schedule[0][0][0] не определено).Также мы не будем включать в наш ответ интервалы типа [5, 5], так как они имеют нулевую длину. Пример:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]

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

from typing import List

class Interval:
    def __init__(self, start: int, end: int):
        self.start = start
        self.end = end

def employeeFreeTime(schedule: List[List[Interval]]) -> List[Interval]:
    intervals = []
    for employee in schedule:
        intervals.extend(employee)
    
    intervals.sort(key=lambda x: x.start)
    
    merged = []
    for interval in intervals:
        if not merged or merged[-1].end < interval.start:
            merged.append(interval)
        else:
            merged[-1].end = max(merged[-1].end, interval.end)
    
    free_time = []
    for i in range(1, len(merged)):
        if merged[i].start > merged[i-1].end:
            free_time.append(Interval(merged[i-1].end, merged[i].start))
    
    return free_time

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

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

#medium Задача: 758. Bold Words in String При наличии массива ключевых слов и строки a выделите все ключевые слова [i] жирным шрифтом. Все буквы между тегами <b> и </b> выделяются жирным шрифтом. Возвращает после добавления тегов, выделенных жирным шрифтом. Возвращаемая строка должна содержать как можно меньшее количество тегов, и теги должны образовывать допустимую комбинацию. Пример:

Input: words = ["ab","bc"], s = "aabcd"
Output: "a<b>abc</b>d"

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

def addBoldTags(keywords, s):
    n = len(s)
    bold = [False] * n
    for word in keywords:
        start = s.find(word)
        while start != -1:
            for i in range(start, start + len(word)):
                bold[i] = True
            start = s.find(word, start + 1)
    
    result = []
    i = 0
    while i < n:
        if bold[i]:
            result.append("<b>")
            while i < n and bold[i]:
                result.append(s[i])
                i += 1
            result.append("</b>")
        else:
            result.append(s[i])
            i += 1
    return "".join(result)

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

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

#hard Задача: 757. Set Intersection Size At Least Two Вам дан двумерный целочисленный массив intervals, в котором intervals[i] = [starti, endi] представляет все целые числа от starti до endi включительно. Содержащее множество - это массив nums, в котором каждый интервал из intervals содержит не менее двух целых чисел в nums. Например, если intervals = [[1,3], [3,7], [8,9]], то [1,2,4,7,8,9] и [2,3,4,8,9] - содержащие множества. Верните минимально возможный размер содержащего множества. Пример:

Input: intervals = [[1,3],[3,7],[8,9]]
Output: 5

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

def minSetSize(intervals):
    intervals.sort(key=lambda x: x[1])
    nums = []
    for start, end in intervals:
        if not nums or nums[-1] < start:
            nums.append(end - 1)
            nums.append(end)
        elif nums[-1] == end - 1:
            nums.append(end)
    return len(nums)

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

"Поступашки — ШАД, Стажировки и Магистратура", - лучше гайд в мире образования и карьеры. Канал ведут преподаватели Яндекса, ВШЭ и ШАД. Внутри: 🔺Слив вопросов с собеса в Яндекс 🔺Как бесплатно вкатиться в айти 🔺Подборка топовых магистратур по Data Science ...и еще море полезнейшего контента. Я жалею, что не нашел этот канал раньше. Подписывайтесь, потом сами себе спасибо скажете: ⬇️ @postypashki_old

UserGate Open Conf 17 / 04 / 2025 ⚡ ИТ-конференция про защиту в открытую. Здесь мы создаем площадку для открытого диалога между заказчиками, партнерами, экспертами и специалистами в сфере продуктов, технологий и услуг информационной безопасности. Что мы готовим для вас: - аналитические данные исследования рынка информационной безопасности; - обзор новых видов и эволюции киберугроз с разбором кейсов по борьбе с ними; - планы внедрения новых фич и обновлений продуктов экосистемы UserGate; - 30+ продуктовых, партнерских и клиентских докладов; - нетворкинг, продуктовые демо, обмен опытом и консультации экспертов ИБ; - ответы на любые вопросы и сбор обратной связи о работе продуктов и устройств UserGate. Зарегистрироваться #реклама openconf.usergate.com О рекламодателе

#medium Задача: 756. Pyramid Transition Matrix Вы складываете блоки так, чтобы получилась пирамида. Каждый блок имеет цвет, который представлен одной буквой. Каждый ряд блоков содержит на один блок меньше, чем ряд под ним, и располагается по центру сверху. Чтобы пирамида выглядела эстетично, допускаются только определенные треугольные узоры. Треугольный узор состоит из одного блока, уложенного поверх двух блоков. Шаблоны задаются в виде списка допустимых трехбуквенных строк, где первые два символа шаблона представляют левый и правый нижние блоки соответственно, а третий символ - верхний блок. Например, "ABC" представляет треугольный шаблон с блоком 'C', уложенным поверх блоков 'A' (слева) и 'B' (справа). Обратите внимание, что это отличается от "BAC", где "B" находится слева внизу, а "A" - справа внизу. Вы начинаете с нижнего ряда блоков bottom, заданного в виде одной строки, который вы должны использовать в качестве основания пирамиды. Учитывая bottom и allowed, верните true, если вы можете построить пирамиду до самой вершины так, чтобы каждый треугольный узор в пирамиде был в allowed, или false в противном случае. Пример:

Input: bottom = "BCD", allowed = ["BCC","CDE","CEA","FFF"]
Output: true

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

def pyramidTransition(bottom, allowed):
    from collections import defaultdict

    allowed_dict = defaultdict(list)
    for pattern in allowed:
        allowed_dict[pattern[:2]].append(pattern[2])

    def can_build(current_level):
        if len(current_level) == 1:
            return True
        next_level = []
        for i in range(len(current_level) - 1):
            if current_level[i:i+2] not in allowed_dict:
                return False
            next_level.append(allowed_dict[current_level[i:i+2]])
        return any(can_build("".join(c)) for c in product(*next_level))

    return can_build(bottom)

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

Курс графического дизайна с нуля Выбери свое направление в дизайне: графический дизайн, веб-дизайн, UX/UI-дизайн. И изучи бесплатно основы дизайна с личным наставником! 3 работы в портфолио. Узнать больше #реклама 16+ yudaevschool24.online О рекламодателе