Python | LeetCode

Партнёрская программа рекрутинга в Яндекс Еду Станьте партнёром Яндекс Еды по привлечению курьеров и получите кучу преимуществ: 💰Платим до 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)

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

Регистрируйтесь на главную конференцию Yandex Cloud! 5 тематических треков, 31 доклад, 50 экспертов, нетворкинг и общение. Участие бесплатное. Зарегистрироваться #реклама scale.yandex.cloud О рекламодателе

#medium Задача: 172. Factorial Trailing Zeroes Дано целое число n, верните количество конечных нулей в n!. Обратите внимание, что n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1. Пример:

Input: n = 3
Output: 0
Explanation: 3! = 6, no trailing zero.

👨‍💻 Алгоритм: 1️⃣Вычислите факториал n: Инициализируйте переменную nFactorial значением 1. Для каждого i от 2 до n включительно умножайте nFactorial на i. 2️⃣Подсчитайте количество конечных нулей в nFactorial: Инициализируйте переменную zeroCount значением 0. Пока nFactorial делится на 10 без остатка, делите его на 10 и увеличивайте zeroCount на 1. 3️⃣Верните значение zeroCount как количество конечных нулей в n!. 😎 Решение:

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

        n_factorial = 1
        for i in range(2, n + 1):
            n_factorial *= i

        zero_count = 0
        while n_factorial % 10 == 0:
            zero_count += 1
            n_factorial //= 10

        return zero_count

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

#easy Задача: 171. Excel Sheet Column Number Дана строка columnTitle, представляющая название столбца, как это отображается в Excel. Вернуть соответствующий номер столбца. Пример:

Input: columnTitle = "A"
Output: 1

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

class Solution:
    def titleToNumber(self, s: str) -> int:
        result = 0

        alpha_map = {chr(i + 65): i + 1 for i in range(26)}

        n = len(s)
        for i in range(n):
            cur_char = s[n - 1 - i]
            result += alpha_map[cur_char] * (26**i)
        return result

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

ITELON - надежный поставщик серверного оборудования! 20 лет на рынке IT – опыт и доверие тысяч клиентов! ⚡Серверы и системы хранения от ведущих производителей HPE, Dell, Lenovo, Huawei, Cisco и многих других! ✅ Только новое оригинальное оборудование с гарантией 3 и 5 лет. 🏠Собственный склад и сервис с предпродажным тестированием и технической поддержкой. 🚗Стабильная и предсказуемая логистика – обеспечиваем доступ к качественным мировым брендам в условиях санкций и ограничений. 💻Удобный конфигуратор серверов онлайн с ценами! Зайдите на наш сайт и узнайте больше: www.itelon.ru Свяжитесь с нами: 7 (495) 510 3335 I 8 (800) 505 5110 Перейти на сайт #реклама itelon.ru О рекламодателе

#easy Задача: 170. Two Sum III - Data structure design Разработайте структуру данных, которая принимает поток целых чисел и проверяет, есть ли в ней пара чисел, сумма которых равна определенному значению. Реализуйте класс TwoSum: - TwoSum() инициализирует объект TwoSum с изначально пустым массивом. - void add(int number) добавляет число в структуру данных. - boolean find(int value) возвращает true, если существует хотя бы одна пара чисел, сумма которых равна значению value, в противном случае возвращает false. Пример:

Input
["TwoSum", "add", "add", "add", "find", "find"]
[[], [1], [3], [5], [4], [7]]
Output
[null, null, null, null, true, false]

👨‍💻 Алгоритм: 1️⃣Инициализация указателей: Инициализируйте два указателя low и high, которые указывают на первый и последний элементы списка соответственно. 2️⃣Итерация с использованием двух указателей: Запустите цикл для итерации по списку. Цикл завершится, когда будет найдено решение с двумя суммами или когда два указателя встретятся. На каждом шаге цикла перемещайте один из указателей в зависимости от различных условий: Если сумма элементов, на которые указывают текущие указатели, меньше желаемого значения, то необходимо попытаться увеличить сумму для достижения желаемого значения, то есть переместить указатель low вперёд для получения большего значения. Если сумма элементов больше желаемого значения, то следует попытаться уменьшить сумму, перемещая указатель high в сторону указателя low. Если сумма равна желаемому значению, можно сразу выполнить возврат из функции. 3️⃣Завершение цикла: Если цикл завершается тем, что два указателя встречаются, то можно быть уверенным, что решения для желаемого значения не существует. 😎 Решение:

class TwoSum(object):

    def __init__(self) -> None:
       
        self.nums = []
        self.is_sorted = False

    def add(self, number: int) -> None:
        self.nums.append(number)
        self.is_sorted = False

    def find(self, value: int) -> bool:
        if not self.is_sorted:
            self.nums.sort()
            self.is_sorted = True

        low, high = 0, len(self.nums) - 1
        while low < high:
            currSum = self.nums[low] + self.nums[high]
            if currSum < value:
                low += 1
            elif currSum > value:
                high -= 1
            else: return True

        return False

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

#easy Задача: 169. Majority Element Дан массив nums размера n, верните элемент большинства. Элемент большинства — это элемент, который встречается более чем ⌊n / 2⌋ раз. Можно предположить, что элемент большинства всегда существует в массиве. Пример:

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

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

class Solution:
    def majorityElement(self, nums):
        counts = collections.Counter(nums)
        return max(counts.keys(), key=counts.get)

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

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

#easy Задача: 168. Excel Sheet Column Title Дано целое число columnNumber, верните соответствующий заголовок столбца, как он отображается в таблице Excel. Например: A -> 1 B -> 2 C -> 3 Z -> 26 AA -> 27 AB -> 28 Пример:

Input: columnNumber = 1
Output: "A"

👨‍💻 Алгоритм: 1️⃣Инициализация пустой строки ans: Создайте пустую строку ans, которая будет хранить заголовок столбца. 2️⃣Циклическое преобразование числа в буквы: Пока columnNumber больше 0, выполняйте следующие действия: Вычтите 1 из columnNumber для корректировки индекса (Excel использует 1-индексацию). Найдите символ, соответствующий остатку от деления columnNumber на 26, и добавьте его в начало строки ans. Присвойте columnNumber значение от деления columnNumber на 26 3️⃣Переворот и возврат результата: Так как символы добавляются в начало строки, то по завершению цикла строка ans содержит заголовок столбца в обратном порядке. Переверните строку ans, чтобы представить её в правильном порядке. Верните полученный заголовок столбца. 😎 Решение:

class Solution:
    def convertToTitle(self, columnNumber: int) -> str:
        ans = ""
        while columnNumber > 0:
            columnNumber -= 1
            
            ans += chr(columnNumber % 26 + ord("A"))
            columnNumber //= 26
        return ans[::-1]

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