Python | LeetCode

Регистрация бизнеса в Гонконге. Онлайн. 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]

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

#medium Задача: 167. Two Sum II - Input Array Is Sorted Дан массив целых чисел numbers, индексированный с 1, который уже отсортирован в неубывающем порядке. Найдите два числа так, чтобы их сумма составляла заданное целевое число. Пусть эти два числа будут numbers[index1] и numbers[index2], где 1 <= index1 < index2 <= numbers.length. Верните индексы этих двух чисел, index1 и index2, увеличенные на один, в виде массива из двух элементов [index1, index2]. Тесты генерируются таким образом, что существует ровно одно решение. Нельзя использовать один и тот же элемент дважды. Ваше решение должно использовать только константное дополнительное пространство. Пример:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

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

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        low = 0
        high = len(numbers) - 1
        while low < high:
            sum = numbers[low] + numbers[high]

            if sum == target:
                return [low + 1, high + 1]
            elif sum < target:
                low += 1
            else:
                high -= 1
        return [-1, -1]

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

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

#medium Задача: 166. Fraction to Recurring Decimal Даны два целых числа, представляющих числитель и знаменатель дроби. Верните дробь в строковом формате. Если дробная часть повторяется, заключите повторяющуюся часть в скобки. Если возможны несколько ответов, верните любой из них. Гарантируется, что длина строки ответа будет меньше 10^4 для всех предоставленных входных данных. Пример:

Input: numerator = 1, denominator = 2
Output: "0.5"

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

class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        if numerator == 0:
            return "0"

        fraction = []
        if (numerator < 0) != (denominator < 0):
            fraction.append("-")

        dividend = abs(numerator)
        divisor = abs(denominator)

        fraction.append(str(dividend // divisor))
        remainder = dividend % divisor
        if remainder == 0:
            return "".join(fraction)

        fraction.append(".")
        lookup = {}
        while remainder != 0:
            if remainder in lookup:
                fraction.insert(lookup[remainder], "(")
                fraction.append(")")
                break

            lookup[remainder] = len(fraction)
            remainder *= 10
            fraction.append(str(remainder // divisor))
            remainder %= divisor

        return "".join(fraction)

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

#medium Задача: 165. Compare Version Numbers Даны две строки версий, version1 и version2. Сравните их. Строка версии состоит из ревизий, разделенных точками '.'. Значение ревизии — это её целочисленное преобразование с игнорированием ведущих нулей. Для сравнения строк версий сравнивайте их значения ревизий в порядке слева направо. Если одна из строк версий имеет меньше ревизий, то отсутствующие значения ревизий следует считать равными 0. Верните следующее: - Если version1 < version2, верните -1. - Если version1 > version2, верните 1. - В противном случае верните 0. Пример:

Input: version1 = "1.2", version2 = "1.10"
Output: -1
Explanation:
version1's second revision is "2" and version2's second revision is "10": 2 < 10, so version1 < version2.

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

class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        nums1 = version1.split(".")
        nums2 = version2.split(".")
        n1, n2 = len(nums1), len(nums2)

        for i in range(max(n1, n2)):
            i1 = int(nums1[i]) if i < n1 else 0
            i2 = int(nums2[i]) if i < n2 else 0
            if i1 != i2:
                return 1 if i1 > i2 else -1
        return 0

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

Сообщество IT-специалистов в Telegram от Selectel. Канал крупнейшего независимого провайдера IT-инфраструктуры и облаков. Шесть причин подписаться на канал: - железные новости; - обзоры продуктов; - разборы кейсов; - актуальные IT-статьи; - анонсы митапов; - бесплатные курсы. Подписаться #реклама О рекламодателе

#medium Задача: 164. Maximum Gap Дан массив целых чисел nums. Верните максимальную разницу между двумя последовательными элементами в его отсортированной форме. Если массив содержит менее двух элементов, верните 0. Необходимо написать алгоритм, который работает за линейное время и использует линейное дополнительное пространство. Пример:

Input: nums = [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either (3,6) or (6,9) has the maximum difference 3.

👨‍💻 Алгоритм: 1️⃣Инициализация: Определите минимальное и максимальное значения в массиве для расчета возможного максимального интервала (разрыва) между элементами в идеально распределенном массиве. Вычислите размер ведра (bucket size), необходимый для размещения всех элементов массива так, чтобы если массив был равномерно распределен, каждый ведер должен содержать хотя бы один элемент. Размер ведра = (max_value - min_value) / (количество элементов - 1). 2️⃣Размещение элементов в ведрах: Создайте ведра для хранения минимальных и максимальных значений каждого ведра. Используйте формулу для распределения каждого элемента в соответствующем ведре на основе его значения. Игнорируйте пустые ведра при расчете максимального интервала. 3️⃣Вычисление максимального интервала: Пройдите через ведра и вычислите максимальный интервал, сравнивая минимальное значение текущего непустого ведра с максимальным значением предыдущего непустого ведра. Максимальный интервал будет наибольшей разницей между "минимальными" и "максимальными" значениями последовательных непустых ведер. 😎 Решение:

class Solution:
    def maximumGap(self, nums):
        if (
            nums is None or len(nums) < 2
        ): 
            return 0

        nums.sort()  
        maxGap = 0

        for i in range(len(nums) - 1):
            maxGap = max(nums[i + 1] - nums[i], maxGap)

        return maxGap

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