Python | LeetCode

Как самостоятельно читать анализы и выявлять заболевания Научитесь разбирать общий анализ крови с развернутой лейкоцитарной формулой. Это бесплатно. На открытом уроке вы: ✅научитесь разбирать общий анализ крови с развернутой лейкоцитарной формулой; ✅узнаете о каких дефицитах может рассказать этот недорогой анализ; ✅научитесь составлять план работы с этим анализом без лекарств; ✅ узнаете, как стать нутрициологом, где искать клиентов и как зарабатывать от 100 000 рублей, не выходя из дома При регистрации вы получите подарок - конспект урока. После урока по этому конспекту вы сможете самостоятельно разобрать свой общий анализ крови. Чтобы зарегистрироваться на урок - переходите по ссылке. ⚡Урок бесплатный, поэтому количество мест ограничено. Зарегистрироваться #реклама 16+ pro-telo1.com О рекламодателе

Задача: 319. Bulb Switcher Сложность: medium Есть n лампочек, которые изначально выключены. Сначала вы включаете все лампочки, затем выключаете каждую вторую лампочку. На третьем раунде вы переключаете каждую третью лампочку (включаете, если она выключена, или выключаете, если она включена). На i-ом раунде вы переключаете каждую i-ую лампочку. На n-ом раунде вы переключаете только последнюю лампочку. Верните количество лампочек, которые будут включены после n раундов. Пример:

Input: n = 3
Output: 1
Explanation: At first, the three bulbs are [off, off, off].
After the first round, the three bulbs are [on, on, on].
After the second round, the three bulbs are [on, off, on].
After the third round, the three bulbs are [on, off, off]. 
So you should return 1 because there is only one bulb is on.
Explanation: The two words can be "abcw", "xtfn".

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

class Solution:
    def bulbSwitch(self, n: int) -> int:
        return int(n ** 0.5)

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

Регистрируйтесь на Yandex Neuro Scale В этом году у конференции новое имя и фокус: главной темой становятся нейротехнологии. Мы покажем, как бизнес уже применяет сервисы и как создавать собственных AI-агентов с помощью инструментов нашей платформы. ✨Ждём вас на главной конференции Yandex Cloud!✨ Зарегистрироваться #реклама 16+ scale.yandex.cloud О рекламодателе Реклама на Яндексе

Задача: 905. Sort Array By Parity Сложность: easy Если задан целочисленный массив nums, переместите все четные числа в начало массива, а затем все нечетные. Верните любой массив, удовлетворяющий этому условию. Пример:

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

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

def sortArrayByParity(nums):
    evens = [x for x in nums if x % 2 == 0]
    odds = [x for x in nums if x % 2 != 0]
    return evens + odds

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

Дарим подписку на Яндекс Музыку Ответьте на 1 вопрос и Яндекс Музыка ваша для вас и 3-х ваших близких. Кинопоиск и Яндекс Книги тоже в подписке. Попробуйте бесплатно❤️ Попробовать #реклама 18+ music.yandex.ru О рекламодателе Реклама на Яндексе

Задача: 541. Reverse String II Сложность: easy Дана строка s и целое число k, переверните первые k символов для каждых 2k символов, начиная с начала строки. Если осталось меньше k символов, переверните все. Если осталось меньше 2k, но больше или равно k символов, переверните первые k символов и оставьте остальные как есть. Пример:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"

👨‍💻 Алгоритм: 1⃣Разворачиваем каждый блок из 2k символов непосредственно. Каждый блок начинается с кратного 2k: например, 0, 2k, 4k, 6k и так далее. 2⃣Будьте внимательны, если символов недостаточно, блок может не быть перевернут. 3⃣Для разворота блока символов с позиции i до j, меняем местами символы на позициях i++ и j--. 😎 Решение:

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        a = list(s)
        for start in range(0, len(a), 2 * k):
            i, j = start, min(start + k - 1, len(a) - 1)
            while i < j:
                a[i], a[j] = a[j], a[i]
                i += 1
                j -= 1
        return ''.join(a)

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

Не платите больше. Зафиксируйте цену сегодня Сколько клиентов вы уже упустили? Каждая просроченная заявка – это деньги вашим конкурентам. amoCRM помогает закрывать сделки, пока другие теряют лиды. Мы не делаем универсальных решений для всех. Только то, что работает в продажах. И одно из лучших решений, которое вы можете принять сейчас – это зафиксировать текущую цену. С 01 сентября amoCRM станет дороже. Но если подключитесь до этой даты, мы зафиксируем текущую цену для вас — и сейчас, и при продлении. ✨ Переходите по ссылке и успейте зафиксировать свою выгоду! Узнать больше #реклама 16+ amocrm.ru О рекламодателе

Задача: 117. Populating Next Right Pointers in Each Node II Сложность: medium Вам дано бинарное дерево:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Заполните каждый указатель next, чтобы он указывал на следующий правый узел. Если следующего правого узла нет, указатель next должен быть установлен в NULL. Изначально все указатели next установлены в NULL. Пример:

Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

👨‍💻 Алгоритм: 1️⃣Инициализируйте очередь Q, которая будет использоваться во время обхода. Существует несколько способов реализации обхода в ширину, особенно когда дело доходит до определения уровня конкретного узла. Можно добавить в очередь пару (узел, уровень), и каждый раз, когда мы добавляем детей узла, мы добавляем (node.left, parent_level+1) и (node.right, parent_level+1). Этот подход может оказаться неэффективным для нашего алгоритма, так как нам нужны все узлы на одном уровне, и потребуется дополнительная структура данных. 2️⃣Более эффективный с точки зрения памяти способ разделения узлов одного уровня - использовать разграничение между уровнями. Обычно мы вставляем в очередь элемент NULL, который обозначает конец предыдущего уровня и начало следующего. Это отличный подход, но он все равно потребует некоторого объема памяти, пропорционального количеству уровней в дереве. 3️⃣Подход, который мы будем использовать, предполагает структуру вложенных циклов, чтобы обойти необходимость NULL указателя. По сути, на каждом шаге мы фиксируем размер очереди, который всегда соответствует всем узлам на определенном уровне. Как только мы узнаем этот размер, мы обрабатываем только это количество элементов и больше ничего. К тому времени, как мы закончим обработку заданного количества элементов, в очереди окажутся все узлы следующего уровня. Вот псевдокод для этого:

while (!Q.empty())
{
    size = Q.size()
    for i in range 0..size
    {
        node = Q.pop()
        Q.push(node.left)
        Q.push(node.right)
    }
}

Мы начинаем с добавления корня дерева в очередь. Так как на уровне 0 есть только один узел, нам не нужно устанавливать какие-либо соединения, и мы можем перейти к циклу while. 😎 Решение:

class Solution:
    def connect(self, root: Optional["Node"]) -> Optional["Node"]:
        if not root:
            return root

        Q = collections.deque([root])

        while Q:
            size = len(Q)

            for i in range(size):
                node = Q.popleft()
                if i < size - 1:
                    node.next = Q[0]
                if node.left:
                    Q.append(node.left)
                if node.right:
                    Q.append(node.right)

        return root

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

Задача: 1151. Minimum Swaps to Group All 1's Together Сложность: medium Дан бинарный массив data, необходимо вернуть минимальное количество перестановок, чтобы сгруппировать все 1, присутствующие в массиве, вместе в любом месте массива. Пример:

Input: data = [1,0,1,0,1]
Output: 1
Explanation: There are 3 ways to group all 1's together:
[1,1,1,0,0] using 1 swap.
[0,1,1,1,0] using 2 swaps.
[0,0,1,1,1] using 1 swap.
The minimum is 1.

👨‍💻 Алгоритм: 1⃣Используем два указателя, left и right, чтобы поддерживать скользящее окно длиной ones и проверяем каждый фрагмент массива data, подсчитывая количество единиц в нем (cnt_one) и запоминая максимальное значение max_one. 2⃣Пока окно скользит по массиву data, поддерживаем его длину равной ones. 3⃣Обновляем количество единиц в окне, добавляя новую границу data[right] и вычитая левую границу data[left]. 😎 Решение:

class Solution:
    def minSwaps(self, data):
        ones = sum(data)
        cnt_one = max_one = 0
        left = right = 0

        while right < len(data):
            cnt_one += data[right]
            right += 1
            if right - left > ones:
                cnt_one -= data[left]
                left += 1
            max_one = max(max_one, cnt_one)
        return ones - max_one

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

Получи грант до 1,2 млн руб. на обучение в магистратуре Хочешь развиваться в сфере ИТ и получить фундаментальные знания с практикой? Поступай в магистратуру Центрального университета! - 4 офлайн программы по востребованным направлениям ИТ - Онлайн-программа по машинному обучению - 300 мест с грантами до 1,2 млн руб. - Вечерние занятия и учеба по выходным — удобно совмещать с работой - Обучение по модели STEM-образования: на стыке науки, технологий и бизнеса - Возможность стажировок и трудоустройства в ведущих компаниях - Государственный диплом за 2 года Магистратура в Центральном университете — это современный подход к образованию, сильный преподавательский состав и актуальные кейсы от индустрии. Оставляй заявку на грант уже сейчас! Подать заявку #реклама 16+ apply.centraluniversity.ru О рекламодателе

Задача: 304. Range Sum Query 2D - Immutable Сложность: medium Дана двумерная матрица matrix. Обработайте несколько запросов следующего типа: Вычислите сумму элементов матрицы внутри прямоугольника, определенного его верхним левым углом (row1, col1) и нижним правым углом (row2, col2). Реализуйте класс NumMatrix: - NumMatrix(int[][] matrix) Инициализирует объект целочисленной матрицей matrix.- int sumRegion(int row1, int col1, int row2, int col2) Возвращает сумму элементов матрицы внутри прямоугольника, определенного его верхним левым углом (row1, col1) и нижним правым углом (row2, col2). Необходимо разработать алгоритм, где метод sumRegion работает за O(1) по времени. Пример:

Input
["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]
[[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]

👨‍💻 Алгоритм: 1⃣Инициализация: Создайте двумерный массив sums размером (m + 1) x (n + 1), где m и n — размеры исходной матрицы matrix. Заполните этот массив нулями. 2⃣Предварительное вычисление сумм: Заполните массив sums, где каждый элемент sums[i][j] будет содержать сумму всех элементов матрицы от начала до позиции (i-1, j-1) включительно. 3⃣Вычисление диапазонной суммы: Для каждого запроса суммы элементов внутри прямоугольника, определенного его углами (row1, col1) и (row2, col2), используйте предварительно вычисленный массив sums для получения результата за O(1) времени. 😎 Решение:

class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        if not matrix or not matrix[0]:
            self.dp = []
            return
        m, n = len(matrix), len(matrix[0])
        self.dp = [[0] * (n + 1) for _ in range(m + 1)]
        for r in range(m):
            for c in range(n):
                self.dp[r + 1][c + 1] = self.dp[r + 1][c] + self.dp[r][c + 1] + matrix[r][c] - self.dp[r][c]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return self.dp[row2 + 1][col2 + 1] - self.dp[row1][col2 + 1] - self.dp[row2 + 1][col1] + self.dp[row1][col1]

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

Задача: 517. Super Washing Machines Сложность: hard У вас есть n супер стиральных машин, расположенных в одну линию. Изначально каждая стиральная машина содержит некоторое количество платьев или пуста. За один ход вы можете выбрать любые m (1 <= m <= n) стиральные машины и одновременно передать одно платье из каждой выбранной машины в одну из её соседних стиральных машин. Дан целочисленный массив machines, представляющий количество платьев в каждой стиральной машине слева направо по линии. Верните минимальное количество ходов, необходимых для того, чтобы во всех стиральных машинах стало одинаковое количество платьев. Если это невозможно, верните -1. Пример:

Input: machines = [1,0,5]
Output: 3
Explanation:
1st move:    1     0 <-- 5    =>    1     1     4
2nd move:    1 <-- 1 <-- 4    =>    2     1     3
3rd move:    2     1 <-- 3    =>    2     2     2

👨‍💻 Алгоритм: 1⃣Проверьте, можно ли решить задачу: длина массива machines должна быть делителем суммы элементов массива machines. Если нет, верните -1. Вычислите количество платьев, которое должно быть в каждой машине: dresses_per_machine = sum(machines) / len(machines). Нормализуйте задачу, заменив количество платьев в каждой машине на количество платьев, которые нужно удалить из этой машины (может быть отрицательное значение). 2⃣Инициализируйте переменные curr_sum, max_sum и res нулем. Итеративно пройдитесь по всем машинам m в массиве machines, обновляя curr_sum и max_sum на каждом шагу: curr_sum += m, max_sum = max(max_sum, abs(curr_sum)). 3⃣Обновляйте результат res на каждом шагу: res = max(res, max_sum, m). Верните res. 😎 Решение:

class Solution:
    def findMinMoves(self, machines: List[int]) -> int:
        n = len(machines)
        dressTotal = sum(machines)
        if dressTotal % n != 0:
            return -1
        
        dressPerMachine = dressTotal // n
        machines = [m - dressPerMachine for m in machines]

        currSum = maxSum = res = 0
        for m in machines:
            currSum += m
            maxSum = max(maxSum, abs(currSum))
            res = max(res, maxSum, m)
        
        return res

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

Баранкины и камни силы Смотрите на Кинопоиске с 7 августа. Семья таксистов обретает сверхсилы — и родственницу из XIX века. Фантастическая комедия с Андреем Федорцовым Узнать больше #реклама 16+ kinopoisk.ru О рекламодателе

Задача: 568. Maximum Vacation Days Сложность: hard LeetCode хочет предоставить одному из своих лучших сотрудников возможность путешествовать по n городам для сбора задач по алгоритмам. Однако, как говорится, "делу время, потехе час". Вы можете брать отпуска в некоторых конкретных городах и неделях. Ваша задача — спланировать поездку, чтобы максимально увеличить количество дней отпуска, которые вы сможете взять, соблюдая при этом определенные правила и ограничения. Правила и ограничения: Вы можете путешествовать только между n городами, обозначенными индексами от 0 до n-1. Изначально вы находитесь в городе с индексом 0 в понедельник. Города связаны рейсами. Рейсы представлены матрицей n x n, называемой flights, представляющей статус авиалинии от города i до города j. Если рейса из города i в город j нет, flights[i][j] == 0; иначе flights[i][j] == 1. Также для всех i выполняется flights[i][i] == 0. У вас есть k недель (каждая неделя состоит из семи дней) для путешествий. Вы можете летать не более одного раза в день и можете летать только утром каждого понедельника. Время полета настолько короткое, что его влияние не учитывается. Для каждого города у вас есть ограниченные дни отпуска в разные недели, заданные матрицей n x k, называемой days. Значение days[i][j] представляет максимальное количество дней отпуска, которые вы можете взять в городе i на неделе j. Вы можете оставаться в городе большее количество дней, чем количество дней отпуска, но вы должны работать в дополнительные дни, которые не будут учитываться как дни отпуска. Даны две матрицы flights и days, верните максимальное количество дней отпуска, которые вы можете взять в течение k недель. Пример:

Input: flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]]
Output: 12
Explanation:
One of the best strategies is:
1st week : fly from city 0 to city 1 on Monday, and play 6 days and work 1 day.
(Although you start at city 0, we could also fly to and start at other cities since it is Monday.)
2nd week : fly from city 1 to city 2 on Monday, and play 3 days and work 4 days.
3rd week : stay at city 2, and play 3 days and work 4 days.
Ans = 6 + 3 + 3 = 12.

👨‍💻 Алгоритм: 1⃣Использовать функцию dfs (поиск в глубину), которая возвращает количество отпускных дней, которые можно взять, начиная с текущего города cur_city и текущей недели weekno. В каждом вызове функции проходить по всем городам и находить все города, которые связаны с текущим городом. Такой город обозначен 1 в соответствующей позиции flights[cur_city][i]. 2⃣Для текущего города можно либо остаться в нем, либо поехать в связанный город. Обозначим город, в который меняется расположение, как j. После смены города нужно найти количество отпускных дней, которые можно взять, начиная с нового города и с новой недели. Это количество отпускных дней можно представить как: days[j][weekno] + dfs(flights, days, j, weekno + 1). 3⃣Для текущего города необходимо найти максимальное количество отпускных дней, выбирая различные города в качестве следующего местоположения. Из всех вариантов отпускных дней выбираем максимальное значение, которое и будет возвращено для каждого вызова функции dfs. 😎 Решение:

class Solution:
    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:
        n, k = len(flights), len(days[0])
        memo = [[-1] * k for _ in range(n)]

        def dfs(cur_city, weekno):
            if weekno == k:
                return 0
            if memo[cur_city][weekno] != -1:
                return memo[cur_city][weekno]
            max_vac = 0
            for next_city in range(n):
                if cur_city == next_city or flights[cur_city][next_city] == 1:
                    max_vac = max(max_vac, days[next_city][weekno] + dfs(next_city, weekno + 1))
            memo[cur_city][weekno] = max_vac
            return max_vac

        return dfs(0, 0)

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

Дарим подписку на Яндекс Музыку Ответьте на 1 вопрос и Яндекс Музыка ваша для вас и 3-х ваших близких. Кинопоиск и Яндекс Книги тоже в подписке. Попробуйте бесплатно❤️ Попробовать #реклама 18+ music.yandex.ru О рекламодателе Реклама на Яндексе

Задача: 638. Shopping Offers Сложность: medium В магазине LeetCode Store есть n предметов для продажи. Каждый товар имеет свою цену. Однако существуют специальные предложения, и специальное предложение состоит из одного или нескольких различных видов товаров с распродажной ценой. Вам дан целочисленный массив price, где price[i] - цена i-го товара, и целочисленный массив needs, где needs[i] - количество штук i-го товара, который вы хотите купить. Вам также дан массив special, где special[i] имеет размер n + 1, где special[i][j] - количество штук j-го товара в i-м предложении, а special[i][n] (т.е., Возвращает наименьшую цену, которую вы можете заплатить за определенный товар из заданных, где вы могли бы оптимально использовать специальные предложения. Вам не разрешается покупать больше товаров, чем вы хотите, даже если это снизит общую цену. Вы можете использовать любое из специальных предложений столько раз, сколько захотите. Пример:

Input: price = [2,5], special = [[3,0,5],[1,2,10]], needs = [3,2]
Output: 14

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

def shoppingOffers(price, special, needs):
    memo = {}
    
    def dfs(cur_needs):
        val = sum(cur_needs[i] * price[i] for i in range(len(needs)))
        for sp in special:
            new_needs = []
            for i in range(len(needs)):
                if sp[i] > cur_needs[i]:
                    break
                new_needs.append(cur_needs[i] - sp[i])
            if len(new_needs) == len(needs):
                val = min(val, memo.get(tuple(new_needs), dfs(new_needs)) + sp[-1])
        memo[tuple(cur_needs)] = val
        return val

    return dfs(needs)

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

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

⚡ Официальный релиз easyoffer 2.0 состоится уже в течение нескольких дней. Напоминаю, что в честь релиза запускаем акцию. Первые 500 покупателей получат: 🚀 Скидку 50% на PRO тариф на 1 год 🎁 Подарок ценностью 5000₽ для тех, кто подписан на этот канал 🔔 Подпишитесь на этот канал: https://t.me/+b2fZN17A9OQ3ZmJi В нем мы опубликуем сообщение о релизе в первую очередь

Задача: 583. Delete Operation for Two Strings Сложность: medium Даны две строки word1 и word2, вернуть минимальное количество шагов, необходимых для того, чтобы сделать word1 и word2 одинаковыми. На одном шаге можно удалить ровно один символ в любой строке. Пример:

Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

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

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [0] * (n + 1)

        for i in range(m + 1):
            temp = [0] * (n + 1)
            for j in range(n + 1):
                if i == 0 or j == 0:
                    temp[j] = i + j
                elif word1[i - 1] == word2[j - 1]:
                    temp[j] = dp[j - 1]
                else:
                    temp[j] = 1 + min(dp[j], temp[j - 1])
            dp = temp

        return dp[n]

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

Дима Билан на Yandex Ecom Open Air 8 августа Регистрируйтесь на B2B-фестиваль от Яндекса для тех, кто развивает онлайн-коммерцию. Участие бесплатно! Зарегистрироваться #реклама 18+ ecomfest.ru О рекламодателе