Python | LeetCode

ТОП-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

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

Партнёрская программа рекрутинга в Яндекс Еду Станьте партнёром Яндекс Еды по привлечению курьеров и получите кучу преимуществ: 💰Платим до 25 000 ₽ за успешного кандидата 📞Поддержка на всех этапах 📅Свободное расписание 📊Удобные инструменты для работы Приводите новых курьеров и получайте в среднем 187 000 ₽ в месяц! Зарегистрироваться #реклама eda.yandex.ru О рекламодателе

#medium Задача: 186. Reverse Words in a String II Дан массив символов s, переверните порядок слов. Слово определяется как последовательность символов, не являющихся пробелами. Слова в s будут разделены одним пробелом. Ваш код должен решать задачу на месте, то есть без выделения дополнительного пространства. Пример:

Input: s = ["a"]
Output: ["a"]

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

class Solution:
    def reverse(self, l: List[str], left: int, right: int) -> None:
        while left < right:
            l[left], l[right] = l[right], l[left]
            left, right = left + 1, right - 1

    def reverse_each_word(self, l: List[str]) -> None:
        n = len(l)
        start = end = 0

        while start < n:
            while end < n and l[end] != ' ':
                end += 1
            self.reverse(l, start, end - 1)
            start = end + 1
            end += 1
            
    def reverseWords(self, s: List[str]) -> None:
        self.reverse(s, 0, len(s) - 1)
        self.reverse_each_word(s)

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

Такси для бизнеса. Яндекс Go Оптимизируйте свои расходы и повысьте эффективность бизнеса с Яндекс Go Узнать больше #реклама business.go.yandex О рекламодателе

#medium Задача: 179. Largest Number Дан список неотрицательных целых чисел nums. Организуйте их таким образом, чтобы они составляли наибольшее число и верните его. Поскольку результат может быть очень большим, вам необходимо вернуть строку вместо целого числа. Пример:

Input: nums = [10,2]
Output: "210"

👨‍💻 Алгоритм: 1️⃣Преобразование и сортировка: Преобразовать каждое число в строку и отсортировать массив строк с использованием специального компаратора, который для двух строк 𝑎 и b сравнивает результаты конкатенации 𝑎+𝑏 и 𝑏+𝑎. 2️⃣Проверка на нули: Если после сортировки первый элемент массива равен "0", вернуть "0", так как все числа в массиве нули. 3️⃣Формирование результата: Конкатенировать отсортированные строки для формирования наибольшего числа и вернуть это число в виде строки. 😎 Решение:

class LargerNumKey(str):
    def __lt__(x, y):
        return x + y > y + x


class Solution:
    def largestNumber(self, nums):
        largest_num = "".join(sorted(map(str, nums), key=LargerNumKey))
        return "0" if largest_num[0] == "0" else largest_num

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

Яндекс Директ Только этой осенью Яндекс Директ добавит до 20 000 ₽ на рекламу для вашего бизнеса ⚡ Зарегистрируйтесь до 30 сентября 2024 года, чтобы участвовать в акции 💰 Узнать больше #реклама yandex.ru О рекламодателе

#hard Задача: 174. Dungeon Game Демоны поймали принцессу и заперли её в самой нижней правой комнате подземелья. Подземелье состоит из комнат, расположенных в форме сетки размером m x n. Наш отважный рыцарь изначально находится в комнате в верхнем левом углу и должен пробиться через подземелье, чтобы спасти принцессу. Рыцарь имеет начальный запас здоровья, представленный положительным целым числом. Если в какой-то момент его уровень здоровья упадет до 0 или ниже, он умирает мгновенно. Некоторые комнаты охраняются демонами (представлены отрицательными числами), так что рыцарь теряет здоровье, входя в эти комнаты; другие комнаты либо пусты (обозначены как 0), либо содержат магические сферы, которые увеличивают здоровье рыцаря (представлены положительными числами). Чтобы как можно скорее добраться до принцессы, рыцарь решает двигаться только вправо или вниз на каждом шаге. Верните минимальное начальное здоровье рыцаря, необходимое для того, чтобы он мог спасти принцессу. Обратите внимание, что любая комната может содержать угрозы или усилители, даже первая комната, в которую входит рыцарь, и нижняя правая комната, где заключена принцесса. Пример:

Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Explanation: The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT-> RIGHT -> DOWN -> DOWN.

👨‍💻 Алгоритм: 1️⃣Определение матрицы dp: Создайте матрицу dp размером с подземелье, где элемент dp[row][col] указывает минимальное количество здоровья, необходимое рыцарю, чтобы начать путь из ячейки dungeon[row][col] и достигнуть цели (нижней правой ячейки). 2️⃣Инициализация и заполнение dp: Начните с правого нижнего угла подземелья и идите в обратном направлении — справа налево и снизу вверх. Для каждой ячейки вычислите соответствующее значение в dp: Если возможно, шаг вправо из текущей ячейки подземелья требует right_health здоровья. Если возможно, шаг вниз из текущей ячейки подземелья требует down_health здоровья. Возьмите минимальное значение из right_health и down_health для dp[row][col]. Если ни один из вышеперечисленных вариантов не доступен (то есть вы находитесь в ячейке назначения), учитывайте два подслучая: Если в ячейке магический шар, достаточно 1 единицы здоровья. Если в ячейке демон, рыцарю необходимо иметь единицу здоровья плюс урон, который может нанести демон. 3️⃣Результат вычислений: Значение в dp[0][0] будет указывать на минимальное количество здоровья, необходимое рыцарю, чтобы начать свой путь из верхней левой ячейки подземелья и успешно спасти принцессу, учитывая все угрозы на его пути. 😎 Решение:

class Solution(object):
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        rows, cols = len(dungeon), len(dungeon[0])
        dp = [[float("inf")] * cols for _ in range(rows)]

        def get_min_health(currCell: int, nextRow: int, nextCol: int) -> float:
            if nextRow >= rows or nextCol >= cols:
                return float("inf")
            nextCell = dp[nextRow][nextCol]
            # hero needs at least 1 point to survive
            return max(1, nextCell - currCell)

        for row in reversed(range(rows)):
            for col in reversed(range(cols)):
                currCell = dungeon[row][col]

                right_health = get_min_health(currCell, row, col + 1)
                down_health = get_min_health(currCell, row + 1, col)
                next_health = min(right_health, down_health)

                if next_health != float("inf"):
                    min_health = next_health
                else:
                    min_health = 1 if currCell >= 0 else (1 - currCell)

                dp[row][col] = min_health

        return dp[0][0]

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

Регистрация бизнеса в Гонконге. Онлайн. VitaLiberta Сделаем старт Вашей международной компании в Гонконге легким и непринужденным. Вы концентрируетесь на старте бизнеса. Vita Liberta Limited поддерживает предпринимателей из Гонконга и Китая, а также из других частей мира. Мы обслуживаем юридических лиц в полном соответствии с законодательством Гонконга. Получить предложение #реклама vitaliberta.hk О рекламодателе

#hard Задача: 174. Dungeon Game Демоны захватили принцессу и заточили её в правом нижнем углу подземелья. Подземелье состоит из m x n комнат, расположенных в виде двумерной сетки. Наш отважный рыцарь изначально находится в левом верхнем углу и должен пробиться через подземелье, чтобы спасти принцессу. У рыцаря есть начальное количество очков здоровья, представленное положительным целым числом. Если в какой-то момент его очки здоровья упадут до 0 или ниже, он немедленно умрёт. Некоторые комнаты охраняются демонами (представлены отрицательными числами), поэтому рыцарь теряет здоровье, заходя в эти комнаты; другие комнаты либо пусты (представлены как 0), либо содержат магические шары, увеличивающие здоровье рыцаря (представлены положительными числами). Чтобы как можно быстрее добраться до принцессы, рыцарь решает двигаться только вправо или вниз на каждом шаге. Верните минимальное начальное количество здоровья рыцаря, чтобы он мог спасти принцессу. Учтите, что любая комната может содержать угрозы или усиления, включая первую комнату, в которую входит рыцарь, и последнюю комнату, где заточена принцесса. Пример:

Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Explanation: The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT-> RIGHT -> DOWN -> DOWN.

👨‍💻 Алгоритм: 1️⃣Определяем матрицу dp[row][col], где элемент dp[row][col] указывает минимальное количество очков здоровья, которое потребуется рыцарю, начиная с соответствующей ячейки подземелья dungeon[row][col], чтобы добраться до цели. 2️⃣Для расчета значений матрицы dp начинаем с правого нижнего угла подземелья и идем в порядке справа-налево и снизу-вверх. Для каждой ячейки подземелья рассчитываем соответствующее значение dp[row][col]. 3️⃣Значение dp[row][col] определяется следующими условиями: Если возможно, сделав шаг вправо из текущей ячейки подземелья, рыцарь может нуждаться в right_health очках здоровья. Если возможно, сделав шаг вниз из текущей ячейки подземелья, рыцарь может нуждаться в down_health очках здоровья. Если существует хотя бы одна из вышеуказанных альтернатив, берём минимальное значение из них для dp[row][col]. Если ни одна из вышеуказанных альтернатив не существует, то есть мы находимся в целевой ячейке, возможны два случая: Если текущая ячейка содержит магический шар, то достаточно одного очка здоровья. Если текущая ячейка содержит демона, то рыцарь должен иметь одно очко здоровья плюс очки урона, которые нанесет демон. 😎 Решение:

class Solution(object):
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        rows, cols = len(dungeon), len(dungeon[0])
        dp = [[float("inf")] * cols for _ in range(rows)]

        def get_min_health(currCell: int, nextRow: int, nextCol: int) -> float:
            if nextRow >= rows or nextCol >= cols:
                return float("inf")
            nextCell = dp[nextRow][nextCol]
            return max(1, nextCell - currCell)

        for row in reversed(range(rows)):
            for col in reversed(range(cols)):
                currCell = dungeon[row][col]

                right_health = get_min_health(currCell, row, col + 1)
                down_health = get_min_health(currCell, row + 1, col)
                next_health = min(right_health, down_health)

                if next_health != float("inf"):
                    min_health = next_health
                else:
                    min_health = 1 if currCell >= 0 else (1 - currCell)

                dp[row][col] = min_health

        return dp[0][0]

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

🧑‍💻 Если твой английский позволяет ответить только на вопрос "Do you speak English", то с этим нужно что-то делать, будучи программистом. 🫤 Ты в курсе, что ... - говорят по-английски — 20% из всех людей. - Большое кол-во IT документации написано на английском. Хочешь понимать код лучше? Изучи язык, который используется в его основе. 📕 На нашем канале ты постепенно будешь набираться опыта, в этом тебе помогут: - Тесты для изучения английского: проверьте свои знания на практике. - Английский через мемы: учите язык весело и с интересом. - Шпаргалки для повторения: закрепите знания быстро и эффективно. - Английский сленг программиста: станьте настоящим профи в коммуникации. 🔥 Маленький шаг в изучении иностранного откроет перед тобой большие возможности будущего специалиста и значительно повысит твое зп. 🌸 Подпишись, do it!

Требуются парни и девушки желающие работать в сфере IT. Опыт в программировании не нужен. Тебя ждёт: 1. Удалённая работа; 2. График свободный от 3-х часов в день; 3. Зарплата от 1000$/мес. ⚡ С нас обучение и помощь с заказами. Мы проводим бесплатный 7-дневонлайн-интенсив по Frontend-разработке, где будем показывать, как разрабатывать сайты и веб-приложения. За эти 7 дней обучения ты: 1. Создашь полноценный веб-сайт на HTML и CSS; 2. Оживишь страницу с помощью JavaScript; 3. Подключишь Backend и загрузишь сайт на хостинг; 4. Получишь советы по доработке своего проекта; А главное, ты увидишь, что разрабатывать сайты и приложения не так сложно, как кажется. И поймёшь, как тебе развиваться в этой профессии, чтобы уже в этом году зарабатывать от 1000$ на вёрстке сайтов. Успей попробовать бесплатно Попробовать #реклама itlogia.ru О рекламодателе

#medium Задача: 173. Binary Search Tree Iterator Реализуйте класс 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)

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