Python | LeetCode

#easy Задача: 202. Happy Number Напишите алгоритм для определения, является ли число n счастливым. Счастливое число определяется следующим образом: 1. Начинаем с любого положительного числа и заменяем его на сумму квадратов его цифр. 2. Повторяем процесс до тех пор, пока число не станет равным 1 (где оно останется), или пока оно не зациклится бесконечно, не достигая 1. 3. Числа, для которых этот процесс заканчивается на 1, являются счастливыми. 4. Верните true, если n является счастливым числом, и false, если нет. Пример:

Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

👨‍💻 Алгоритм: 1️⃣Определите следующее число для заданного числа n. Это можно сделать, используя операции деления и взятия по модулю, чтобы последовательно извлекать цифры из числа, пока они не закончатся, затем возводить каждую извлечённую цифру в квадрат и суммировать их. Внимательно посмотрите на код для этого, "извлечение цифр по одной" — полезная техника, которую вы будете использовать для решения множества различных задач. 2️⃣Следите за цепочкой чисел и обнаруживайте, если мы вошли в цикл. Это можно сделать с помощью HashSet. Каждый раз, когда мы генерируем следующее число в цепочке, мы проверяем, есть ли оно уже в нашем HashSet. Если его нет в HashSet, мы добавляем его. Если оно уже в HashSet, это означает, что мы находимся в цикле и должны вернуть false. 3️⃣Мы используем HashSet, а не Vector, List или Array, потому что мы многократно проверяем, находятся ли числа в нём. Проверка, находится ли число в HashSet, занимает время O(1), тогда как для других структур данных это занимает время O(n). Выбор правильных структур данных — важная часть решения этих задач. 😎 Решение:

class Solution:
    def isHappy(self, n: int) -> bool:

        def get_next(n):
            total_sum = 0
            while n > 0:
                n, digit = divmod(n, 10)
                total_sum += digit**2
            return total_sum

        seen = set()
        while n != 1 and n not in seen:
            seen.add(n)
            n = get_next(n)

        return n == 1

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Все надоело и пропал интерес, чувствуешь себя амебой и хочется только залипать в телефоне. Бывает? Психолог взрослого человека - канал для айтишников, у которых периодически опускаются руки и отключается мозг, ибо переработки и постоянная тревожность не приводят к другим исходам. ✔️ Как научиться отвлекаться от работы и отдыхать? ✔️ Как совместить кучу рабочих задач и время с семьей? ✔️ Как справиться с прокрастинацией? ✔️ Как не растерять запал, даже если начальник и коллеги 💩 и кажется, что ничего не выходит? Подписывайтесь на канал @vadimpetrov_psy и научитесь работать без упахивания, выгорания и ущерба для личной жизни! 👨🏻‍💻 Псс. Заходите в закреп канала - там много полезного, и даже бесплатный мини-курс. https://t.me/+_f2HiZ99wxswZGRi

#medium Задача: 201. Bitwise AND of Numbers Range Даны два целых числа left и right, которые представляют диапазон [left, right], верните побитовое И всех чисел в этом диапазоне включительно. Пример:

Input: left = 5, right = 7
Output: 4

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

class Solution:
    def rangeBitwiseAnd(self, m: int, n: int) -> int:
        shift = 0
        while m < n:
            m = m >> 1
            n = n >> 1
            shift += 1
        return m << shift

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Методичка: как сделать онлайн-встречи эффективнее Надоело ждать коллег, которые постоянно забывают о встречах, а отсутствие повестки и потерянные договоренности мешают нормально работать? Команда МТС Линк собрала на 37 страницах полезные материалы, чек-листы и кейсы, которые помогают компаниям проводить эффективные совещания в онлайне с помощью сервиса Встречи. Из методички узнаете: - Как создать постоянную ссылку и подключаться на встречи в 2 клика, - Как делать заметки и работать с файлами, не переживая за качество связи и безопасность данных. - Как облегчает жизнь ИИ, который расшифровывает созвоны в текст и автоматически отправляет расшифровку на почту. Еще в методичке описаны 7 способов оценки текущей эффективности ваших онлайн-встреч. Получить гайд можно бесплатно на сайте. Скачать #реклама mts-link.ru О рекламодателе

#medium Задача: 200. Number of Islands Дана двумерная бинарная сетка размером m x n, представляющая карту из '1' (земля) и '0' (вода). Верните количество островов. Остров окружён водой и образуется путём соединения соседних земель горизонтально или вертикально. Можно предположить, что все четыре края сетки окружены водой. Пример:

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

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

class Solution:
    def numIslands(self, grid):
        if not grid:
            return 0

        num_islands = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == "1":
                    self.dfs(grid, i, j)
                    num_islands += 1

        return num_islands

    def dfs(self, grid, r, c):
        if (
            r < 0
            or c < 0
            or r >= len(grid)
            or c >= len(grid[0])
            or grid[r][c] != "1"
        ):
            return
        grid[r][c] = "0"

        self.dfs(grid, r - 1, c)
        self.dfs(grid, r + 1, c)
        self.dfs(grid, r, c - 1)
        self.dfs(grid, r, c + 1)

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

🥰 Как улучшить свой код 🥰 Настрой среду, в которой ты работаешь! 🥰 Многие программисты пишут код на настройках по умолчанию - ошибка. 🥰 Не подключают плагины, которые ускорят работу и увеличат эффективность - фатальная ошибка. 👩‍💻 Канал Visual Studio Сode | Плагины сделает твою рабочую среду универсальным и мощным инструментом. 🥰 Повышай свою эффективность и подписывайся на канал Visual Studio Сode | Плагины

Как повысить эффективность вебинаров? Организация продающего вебинара - не простая задача, ведь необходимо предусмотреть множество деталей: удобную дату, вовлекающий контент, методы продвижения и взаимодействия с участниками. Вебинары от МТС Линк помогают привлекать новых клиентов и увеличивать конверсию из участника в лид. В сервисе доступен анализ поведения пользователей во время вебинара, синхронный перевод, автовебинары и интерактивные инструменты для вовлечения участников. Делимся методичкой с кейсами, чек-листами и инструкциями для маркетологов, PR и event-менеджеров, чтобы сделать вебинары эффективным инструментом для лидогенерации. Получите методичку бесплатно на сайте. Скачать #реклама 16+ mts-link.ru О рекламодателе

#medium Задача: 199. Binary Tree Right Side View Дано корень бинарного дерева, представьте, что вы стоите с правой стороны от него, верните значения узлов, которые вы видите, упорядоченные сверху вниз. Пример:

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]

👨‍💻 Алгоритм: 1️⃣Инициализируйте список правого обзора rightside. Инициализируйте две очереди: одну для текущего уровня и одну для следующего. Добавьте корень в очередь nextLevel. 2️⃣Пока очередь nextLevel не пуста: Инициализируйте текущий уровень: currLevel = nextLevel и очистите очередь следующего уровня nextLevel. Пока очередь текущего уровня не пуста: Извлеките узел из очереди текущего уровня. Добавьте сначала левый, а затем правый дочерний узел в очередь nextLevel. Теперь очередь currLevel пуста, и узел, который у нас есть, является последним и составляет часть правого обзора. Добавьте его в rightside. 3️⃣Верните rightside. 😎 Решение:

class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        if root is None:
            return []

        next_level = deque([root])
        rightside = []

        while next_level:
            curr_level = next_level
            next_level = deque()

            while curr_level:
                node = curr_level.popleft()

                if node.left:
                    next_level.append(node.left)
                if node.right:
                    next_level.append(node.right)

            rightside.append(node.val)

        return rightside

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

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

#medium Задача: 198. House Robber Вы — профессиональный грабитель, планирующий ограбление домов вдоль улицы. В каждом доме спрятана определённая сумма денег, единственное ограничение, мешающее ограбить каждый из них, заключается в том, что соседние дома оснащены охранными системами, которые автоматически свяжутся с полицией, если в одну и ту же ночь будут взломаны два соседних дома. Учитывая целочисленный массив nums, представляющий сумму денег в каждом доме, верните максимальную сумму денег, которую вы можете ограбить этой ночью, не подняв тревогу. Пример:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

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

class Solution:

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

    def rob(self, nums: List[int]) -> int:
        self.memo = {}
        return self.robFrom(0, nums)

    def robFrom(self, i, nums):
        if i >= len(nums):
            return 0
        if i in self.memo:
            return self.memo[i]
        ans = max(
            self.robFrom(i + 1, nums), self.robFrom(i + 2, nums) + nums[i]
        )
        self.memo[i] = ans
        return ans

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Помощь в трудоустройстве в IT-сфере! По всей России объявили бесплатную программу на шестимесячное обучение по IT-cпециальностям. Запись на участие в программе продлится до конца июля, но чтобы туда попасть, нужно пройти специальный профтест. По результату тестирования сразу узнаете, какая профессия вам подойдет, и проходите ли вы на бесплатное обучение. Перейти на сайт #реклама 16+ urban-university.ru О рекламодателе

#easy Задача: 191. Number of 1 Bits Напишите функцию, которая принимает бинарное представление положительного целого числа и возвращает количество установленных битов (также известных как вес Хэмминга). Пример:

Input: n = 11

Output: 3

Explanation:

The input binary string 1011 has a total of three set bits.

👨‍💻 Алгоритм: 1️⃣Решение простое: проверяем каждый из 32 битов числа. Если бит равен 1, увеличиваем количество 1-битов на единицу. 2️⃣Для проверки i-го бита числа используем битовую маску. Начинаем с маски m=1, так как двоичное представление 1 это 0000 0000 0000 0000 0000 0000 0000 0001. Логическое И между любым числом и маской 1 дает нам младший бит этого числа. 3️⃣Для проверки следующего бита сдвигаем маску влево на один: 0000 0000 0000 0000 0000 0000 0000 0010 и так далее. 😎 Решение:

def hammingWeight(n: int) -> int:
    bits = 0
    mask = 1
    for _ in range(32):
        if (n & mask) != 0:
            bits += 1
        mask <<= 1
    return bits

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

ТОП-4 Курса по Программированию ⚡Tutortop — маркетплейс курсов №1 по количеству школ-партнеров, курсов и реальных отзывов студентов. ✅Хотите стать программистом, но не знаете с какого языка начать? Помогаем разобраться в самых популярных и востребованных языках программирования. Подарок в конце подборки! Выбрать #реклама 16+ tutortop.ru О рекламодателе

#easy Задача: 190. Reverse Bits Переверните биты заданного 32-битного беззнакового целого числа. Пример:

Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.
Example 2:

👨‍💻 Алгоритм: 1️⃣Итерируем по байтам целого числа, используя побитовую операцию И (n & 0xff) с маской 11111111, чтобы извлечь крайний правый байт числа. 2️⃣Для каждого байта сначала переворачиваем биты внутри байта с помощью функции reverseByte(byte). Затем сдвигаем перевернутые биты на их окончательные позиции. 3️⃣В функции reverseByte(byte) используем технику мемоизации, которая сохраняет результат функции и возвращает его непосредственно при последующих вызовах с тем же входным значением. Мемоизация — это компромисс между использованием памяти и объемом вычислений. 😎 Решение:

import functools
class Solution:
    def reverseBits(self, n: int) -> int:
        ret, power = 0, 24
        while n:
            ret += self.reverseByte(n & 0xFF) << power
            n = n >> 8
            power -= 8
        return ret
    @functools.lru_cache(maxsize=256)
    def reverseByte(self, byte):
        return (byte * 0x0202020202 & 0x010884422010) % 1023

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Бесплатный МК по программированию для детей 8-11 лет Онлайн-школа Университета Иннополис приглашает школьников 2-5 классов на бесплатный ИТ-урок по созданию компьютерных игр! ⚡Специальные навыки не нужны! Для участия в занятии достаточно базовых знаний компьютера и владения клавиатурой! За 1.5 часа участники создадут свою первую игру на Scratch. Научатся создавать персонажей и движущиеся объекты, применять звук и эффекты в своих проектах и добавлять счёт в играх. Регистрируйтесь на бесплатный мастер-класс. Количество мест ограничено. Зарегистрироваться #реклама 16+ progmatica.innopolis.university О рекламодателе

#medium Задача: 189. Rotate Array Для целочисленного массива nums, поверните массив вправо на k шагов, где k — неотрицательное число. Пример:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

👨‍💻 Алгоритм: 1️⃣Создаем дополнительный массив, в который будем помещать каждый элемент исходного массива на его новую позицию. Элемент на позиции i в исходном массиве будет размещен на индексе (i+k) % длина массива. 2️⃣Копируем элементы из нового массива в исходный массив, сохраняя новый порядок элементов. 3️⃣Заменяем исходный массив полученным результатом, завершая процесс поворота массива. 😎 Решение:

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        a = [0] * n
        for i in range(n):
            a[(i + k) % n] = nums[i]

        nums[:] = a

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

CodeInside Аутстаффинг. Официальный telegram-канал Нужны разработчики? IT-команде не хватает рук? Надоело вечно искать аутсорс и перебирать рандомных исполнителей? Все свободные и проверенные разработчики в одном месте Codelnside. Аутстаффинг. 100+ свободных от проектов разработчиков (Middle, Senior, Lead) — и все в одном месте! Всех лично проверили в деле, оценили и привлекали к работе. По каждому — подробный опыт, языки, стек тулов, опыт ОС. По допзапросу — подробное био, отзывы и все детали. Посмотрите, оцените, подпишитесь и сохраните канал в закладках или папках, чтобы не потерять, когда понадобятся IT-руки. P. S. Плюс очень удобно для бенчмарка — можно сравнить себя, свою команду и свои текущие условия с рынком. Подписаться #реклама О рекламодателе

#hard Задача: 188. Best Time to Buy and Sell Stock IV Дан массив целых чисел prices, где prices[i] - это цена данной акции в i-й день, и целое число k. Найдите максимальную прибыль, которую вы можете получить. Вы можете завершить не более чем k транзакций, т.е. вы можете купить не более k раз и продать не более k раз. Обратите внимание: Вы не можете участвовать в нескольких транзакциях одновременно (т.е., вы должны продать акцию, прежде чем снова купить). Пример:

Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

👨‍💻 Алгоритм: 1️⃣Инициализация DP массива: Инициализируйте трехмерный массив dp, где dp[i][j][l] представляет максимальную прибыль на конец i-го дня с j оставшимися транзакциями и l акциями в портфеле. Начните с dp[0][0][0] = 0 (нет прибыли без акций и транзакций) и dp[0][1][1] = -prices[0] (покупка первой акции). 2️⃣Вычисление переходов: Для каждого дня и каждого возможного количества транзакций вычислите возможные действия: держать акцию, не держать акцию, купить акцию, если j > 0, или продать акцию. Обновляйте dp с использованием: dp[i][j][1] = max(dp[i−1][j][1], dp[i−1][j−1][0] - prices[i]) (максимум между удержанием акции и покупкой новой). dp[i][j][0] = max(dp[i−1][j][0], dp[i−1][j][1] + prices[i]) (максимум между неудержанием акции и продажей). 3️⃣Расчет результатов: По завершении всех дней, возвращайте максимальное значение dp[n-1][j][0] для всех j от 0 до k, что представляет максимальную прибыль без удержания акций на последний день. Обработайте специальный случай, когда 𝑘×2≥𝑛, чтобы избежать лишних расчетов. 😎 Решение:

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)        if not prices or k == 0:
            return 0

        if k * 2 >= n:
            res = 0
            for i, j in zip(prices[1:], prices[:-1]):
                res += max(0, i - j)
            return res][ishold] = balance
        dp = [[[-math.inf] * 2 for _ in range(k + 1)] for _ in range(n)]
        dp[0][0][0] = 0
        dp[0][1][1] = -prices[0]
        for i in range(1, n):
            for j in range(k + 1):
                dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]
                if j > 0:
                    dp[i][j][1] = max(
                        dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]
                    )

        res = max(dp[n - 1][j][0] for j in range(k + 1))
        return res

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Jobski - твой помощник при поиске работы в IT Сервис индивидуально подбирает вакансии, учитывая ваш опыт, навыки и стек технологий. Узнать больше #реклама jobski.ru О рекламодателе

#medium Задача: 187. Repeated DNA Sequences ДНК состоит из серии нуклеотидов, обозначаемых как 'A', 'C', 'G' и 'T'. Например, "ACGAATTCCG" — это последовательность ДНК. При изучении ДНК полезно определять повторяющиеся последовательности внутри молекулы ДНК. Дана строка s, представляющая последовательность ДНК. Верните все последовательности длиной 10 букв (подстроки), которые встречаются более одного раза в молекуле ДНК. Ответ можно возвращать в любом порядке. Пример:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]

👨‍💻 Алгоритм: 1️⃣Перебираем начальные позиции последовательности от 1 до 𝑁−𝐿, где 𝑁 — длина строки, а 𝐿 — длина подстроки (в данном случае 10): Если начальная позиция 𝑠𝑡𝑎𝑟𝑡==0, вычисляем хеш первой последовательности 𝑠[0:𝐿]. В противном случае вычисляем скользящий хеш из предыдущего значения хеша. 2️⃣Проверяем хеш в хешсете: Если хеш уже существует в хешсете, значит, мы нашли повторяющуюся последовательность, и пора обновить вывод. В противном случае добавляем хеш в хешсет. 3️⃣Возвращаем список вывода, содержащий все повторяющиеся последовательности. 😎 Решение:

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        L, n = 10, len(s)
        if n <= L:
            return []
        a = 4
        aL = pow(a, L)
        to_int = {"A": 0, "C": 1, "G": 2, "T": 3}
        nums = [to_int.get(s[i]) for i in range(n)]

        h = 0
        seen, output = set(), set()
        for start in range(n - L + 1):
            if start != 0:
                h = h * a - nums[start - 1] * aL + nums[start + L - 1]
            else:
                for i in range(L):
                    h = h * a + nums[i]
            if h in seen:
                output.add(s[start : start + L])
            seen.add(h)
        return output

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых