Python | LeetCode

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

Задача: 1514. Path with Maximum Probability Сложность: medium Вам дан неориентированный взвешенный граф из n узлов (индексация с нуля), представленный списком ребер, где edges[i] = [a, b] является неориентированным ребром, соединяющим узлы a и b с вероятностью успешного прохождения этого ребра succProb[i]. Даны два узла start и end, найдите путь с максимальной вероятностью успеха, чтобы перейти от start к end, и верните его вероятность успеха. Если пути от start до end не существует, верните 0. Ваш ответ будет принят, если он отличается от правильного ответа не более чем на 1e-5. Пример:

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
Output: 0.25000
Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.

👨‍💻 Алгоритм: 1⃣Инициализируйте массив maxProb как максимальную вероятность достижения каждого узла из начального узла, установите maxProb[start] равным 1. 2⃣Расслабьте все ребра: для каждого ребра (u, v), если найдена более высокая вероятность достижения u через это ребро, обновите max_prob[u] как max_prob[u] = max_prob[v] * path_prob. Если найдена более высокая вероятность достижения v через это ребро, обновите max_prob[v]. 3⃣Если нам не удается обновить какой-либо узел с более высокой вероятностью, мы можем остановить итерацию, перейдя к шагу 4. В противном случае повторяйте шаг 2, пока все ребра не будут расслаблены n - 1 раз. Верните max_prob[end]. 😎 Решение:

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        maxProb = [0.0] * n
        maxProb[start] = 1.0

        for _ in range(n - 1):
            hasUpdate = False
            for j in range(len(edges)):
                u, v = edges[j]
                pathProb = succProb[j]
                if maxProb[u] * pathProb > maxProb[v]:
                    maxProb[v] = maxProb[u] * pathProb
                    hasUpdate = True
                if maxProb[v] * pathProb > maxProb[u]:
                    maxProb[u] = maxProb[v] * pathProb
                    hasUpdate = True
            if not hasUpdate:
                break

        return maxProb[end]

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

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

Задача: 302. Smallest Rectangle Enclosing Black Pixels Сложность: hard Вам дана бинарная матрица размером m x n, где 0 представляет собой белый пиксель, а 1 представляет собой черный пиксель. Черные пиксели соединены (то есть существует только одна черная область). Пиксели соединены по горизонтали и вертикали. Даны два целых числа x и y, которые представляют местоположение одного из черных пикселей. Верните площадь наименьшего (выравненного по осям) прямоугольника, который охватывает все черные пиксели. Вы должны написать алгоритм со сложностью менее O(mn). Пример:

Input: image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x = 0, y = 2
Output: 6

👨‍💻 Алгоритм: 1⃣Инициализация границ прямоугольника: Инициализируйте переменные left, right, top и bottom. left и top задаются значениями координат (x, y), right и bottom - значениями x + 1 и y + 1 соответственно. 2⃣Обход всех пикселей: Пройдите по всем координатам (x, y) матрицы. Если текущий пиксель является черным (image[x][y] == 1), обновите границы прямоугольника: left = min(left, x) right = max(right, x + 1) top = min(top, y) bottom = max(bottom, y + 1) 3⃣Вычисление и возврат площади: После завершения обхода матрицы, верните площадь прямоугольника, используя формулу (right - left) * (bottom - top). 😎 Решение:

class Solution:
    def minArea(self, image: List[List[str]], x: int, y: int) -> int:
        m, n = len(image), len(image[0])
        left = self.searchColumns(image, 0, y, 0, m, True)
        right = self.searchColumns(image, y + 1, n, 0, m, False)
        top = self.searchRows(image, 0, x, left, right, True)
        bottom = self.searchRows(image, x + 1, m, left, right, False)
        return (right - left) * (bottom - top)

    def searchColumns(self, image: List[List[str]], i: int, j: int, top: int, bottom: int, whiteToBlack: bool) -> int:
        while i != j:
            k, mid = top, (i + j) // 2
            while k < bottom and image[k][mid] == '0':
                k += 1
            if (k < bottom) == whiteToBlack:
                j = mid
            else:
                i = mid + 1
        return i

    def searchRows(self, image: List[List[str]], i: int, j: int, left: int, right: int, whiteToBlack: bool) -> int:
        while i != j:
            k, mid = left, (i + j) // 2
            while k < right and image[mid][k] == '0':
                k += 1
            if (k < right) == whiteToBlack:
                j = mid
            else:
                i = mid + 1
        return i

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

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

Задача: 1037. Valid Boomerang Сложность: easy Если задан массив points, где points[i] = [xi, yi] представляет точку на плоскости X-Y, верните true, если эти точки являются бумерангом. Бумеранг - это набор из трех точек, которые отличаются друг от друга и не являются прямой линией. Пример:

Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false

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

def isBoomerang(points):
    (x1, y1), (x2, y2), (x3, y3) = points
    return (x1 != x2 or y1 != y2) and (x1 != x3 or y1 != y3) and (x2 != x3 or y2 != y3) and (x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) != 0

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

Карго Бишкек Москва Доставка грузов из Кыргызстана и Китая в Россию. Узнайте стоимость на сайте! Узнать больше Продавец: Росс Карго. ОГРНИП: 31828313 #реклама rosscargo.kg О рекламодателе

Задача: 1039. Minimum Score Triangulation of Polygon Сложность: medium У вас есть выпуклый n-сторонний многоугольник, каждая вершина которого имеет целочисленное значение. Вам дан целочисленный массив values, где values[i] - это значение i-й вершины (т.е. по часовой стрелке). Вы должны триангулировать многоугольник на n - 2 треугольника. Для каждого треугольника значение этого треугольника равно произведению значений его вершин, а общий балл триангуляции равен сумме этих значений для всех n - 2 треугольников в триангуляции. Верните наименьший возможный общий балл, который вы можете получить с помощью некоторой триангуляции многоугольника. Пример:

Input: values = [1,2,3]
Output: 6

👨‍💻 Алгоритм: 1⃣Инициализация: Создаем двумерный массив dp, где dp[i][j] будет хранить минимальный возможный общий балл триангуляции многоугольника, состоящего из вершин от i до j. 2⃣Основное заполнение dp: Проходим по всем возможным длинам подмногоугольников, начиная с треугольников (длина 3) до всего многоугольника (длина n). Для каждого подмногоугольника находим минимальный возможный общий балл, проверяя все возможные треугольники, которые могут быть образованы из этого подмногоугольника. Заполнение dp для каждого подмногоугольника: Для каждого подмногоугольника от i до j, и для каждой возможной вершины k между i и j, обновляем значение dp[i][j], как сумму минимальных значений триангуляций левой и правой частей подмногоугольника, а также значения текущего треугольника, образованного вершинами i, k и j. 3⃣Возврат результата: Ответ будет в dp[0][n-1], который хранит минимальный возможный общий балл триангуляции для всего многоугольника. 😎 Решение:

def minScoreTriangulation(values):
    n = len(values)
    dp = [[0] * n for _ in range(n)]
    
    for length in range(2, n):
        for i in range(n - length):
            j = i + length
            dp[i][j] = float('inf')
            for k in range(i + 1, j):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[j] * values[k])
                
    return dp[0][n - 1]

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

Ликвидация склада LADA в Тюмени ⚡ Автодилер LADA (ВАЗ). Полный модельный ряд в наличии. Скидки до 40% всю неделю. Успей купить новый автомобиль по низкой цене! Специальное предложение: - Выгода до 200 000₽ по trade-in - Автокредит без первоначального взноса - Комплект зимней резины в подарок ⚡ Акция! Новая Lada Granta в кредит от 2 289 ₽/мес. Только до конца месяца! 📞 Адрес автосалона: Тюмень, ул. Уездная, д. 2 ✅ Гарантированная скидка 30 000₽ за заявку онлайн! Перейти на сайт Изучите все условия кредита (займа) на сайте в соответствующем разделе. Оценивайте свои финансовые возможности и риски. Финансовые услуги оказывает: ПАО Сбербанк, АО "ТБанк". #реклама vashalada72.ru О рекламодателе

Задача: 869. Reordered Power of 2 Сложность: medium Дано целое число n. Мы можем переставить цифры числа в любом порядке (включая исходный порядок), при этом ведущая цифра не должна быть нулем. Верните true, если и только если мы можем сделать это так, чтобы полученное число было степенью двойки. Пример:

Input: n = 1
Output: true

👨‍💻 Алгоритм: 1⃣Сгенерируйте все перестановки цифр числа, размещая любую цифру на первой позиции (start = 0), затем любую из оставшихся цифр на второй позиции (start = 1) и так далее. В Python можно использовать встроенную функцию itertools.permutations. 2⃣Проверьте, что перестановка представляет собой степень двойки, убедившись, что в перестановке нет ведущего нуля, и удаляя все множители 2. Если результат равен 1 (то есть, он не содержал других множителей, кроме 2), то это была степень двойки. В Python можно использовать проверку bin(N).count('1') == 1. 3⃣Верните true, если хотя бы одна перестановка является степенью двойки, иначе верните false. 😎 Решение:

class Solution:
    def reorderedPowerOf2(self, N: int) -> bool:
        A = list(map(int, str(N)))
        return self.permutations(A, 0)
    
    def isPowerOfTwo(self, A) -> bool:
        if A[0] == 0:
            return False
        N = int(''.join(map(str, A)))
        return N & (N - 1) == 0
    
    def permutations(self, A, start) -> bool:
        if start == len(A):
            return self.isPowerOfTwo(A)
        for i in range(start, len(A)):
            A[start], A[i] = A[i], A[start]
            if self.permutations(A, start + 1):
                return True
            A[start], A[i] = A[i], A[start]
        return False

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

Стратегическая инвестиция: бутик-отель в билиси Премиальный актив в центре Тбилиси - готовый бизнес с подтверждённым потенциалом роста. Отель включает 39 уникальных номеров, ресторан, современный тренажёрный зал и террасу. Ключевые показатели: - Стабильная заполняемость 60–70% - Высокие рейтинги: 4.3 на TripAdvisor, 8.2 на Agoda - Общая площадь: 1966 м² - Преимущества объекта: - Прозрачная структура владения - Полная готовность к эксплуатации - Престижное расположение Написать в Telegram #реклама ru.grovehotelgeorgia.com О рекламодателе

Задача: 958. Check Completeness of a Binary Tree Сложность: medium Дан корень бинарного дерева, определите, является ли оно полным бинарным деревом. В полном бинарном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно левее. На последнем уровне h может быть от 1 до 2^h узлов включительно. Пример:

Input: root = [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

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

from collections import deque

class Solution:
    def isCompleteTree(self, root: TreeNode) -> bool:
        if not root:
            return True

        queue = deque([root])
        nullNodeFound = False

        while queue:
            node = queue.popleft()
            
            if not node:
                nullNodeFound = True
            else:
                if nullNodeFound:
                    return False
                queue.append(node.left)
                queue.append(node.right)

        return True

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

Задача: 239. Sliding Window Maximum Сложность: hard Вам дан массив целых чисел nums. Существует скользящее окно размера k, которое перемещается с самого левого конца массива до самого правого. Вы можете видеть только k чисел в окне. Каждый раз скользящее окно перемещается вправо на одну позицию. Верните максимальные значения скользящего окна. Пример:

Input: nums = [1], k = 1
Output: [1]

👨‍💻 Алгоритм: 1⃣Инициализация и заполнение первой части окна: Создайте двустороннюю очередь dq для хранения индексов элементов и список res для хранения результатов. Пройдите по первым k элементам массива nums (от i = 0 до k - 1). Для каждого элемента: Удалите из dq все элементы, которые меньше или равны текущему элементу nums[i]. Добавьте текущий индекс i в конец dq. Добавьте в res максимальный элемент первого окна, который находится в nums[dq[0]]. 2⃣Сканирование оставшейся части массива: Пройдите по оставшимся элементам массива nums (от i = k до n - 1). Для каждого элемента: Если индекс элемента на передней части dq равен i - k, удалите этот элемент из dq, так как он выходит за пределы текущего окна. Удалите из dq все элементы, которые меньше или равны текущему элементу nums[i]. Добавьте текущий индекс i в конец dq. Добавьте в res максимальный элемент текущего окна, который находится в nums[dq[0]]. 3⃣Возвращение результата: Верните список res, содержащий максимальные элементы для каждого скользящего окна. 😎 Решение:

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq = collections.deque()
        res = []

        for i in range(k):
            while dq and nums[i] >= nums[dq[-1]]:
                dq.pop()
            dq.append(i)
        res.append(nums[dq[0]])

        for i in range(k, len(nums)):
            if dq[0] == i - k:
                dq.popleft()
            while dq and nums[i] >= nums[dq[-1]]:
                dq.pop()
            dq.append(i)
            res.append(nums[dq[0]])

        return res

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

Гайд МТС Линк для CEO по эффективным онлайн-встречам Как CEO сохранять фокус на стратегии и развивающих задачах и не терять договоренности с руководителями и топ-командой? Гайд МТС Линк — чек-листы, кейсы и подходы для оптимизации совещаний с помощью онлайн-встреч и ИИ. ✅ В гайде: - Как доносить цели, культуру и стратегию компании до каждого сотрудника; - Как снижать затраты на корпоративное обучение без потери качества и вовлечения; - Как сократить расходы на организацию имиджевых событий с помощью одного решения; - Как не устроить хаос в коммуникациях между командами при расширении компании. Бонус внутри: 5 способов не выгореть от бесконечных синков. ✨ Скачайте гайд бесплатно по ссылке Скачать #реклама 16+ mts-link.ru О рекламодателе

Задача: 1302. Deepest Leaves Sum Сложность: medium Дано корень бинарного дерева, вернуть сумму значений его самых глубоких листьев. Пример:

Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15

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

class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        deepest_sum = 0
        depth = 0
        stack = [(root, 0)]
        
        while stack:
            node, curr_depth = stack.pop()
            
            if not node.left and not node.right:
                if depth < curr_depth:
                    deepest_sum = node.val
                    depth = curr_depth
                elif depth == curr_depth:
                    deepest_sum += node.val
            else:
                if node.right:
                    stack.append((node.right, curr_depth + 1))
                if node.left:
                    stack.append((node.left, curr_depth + 1))
        
        return deepest_sum

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

Задача: 299. Bulls and Cows Сложность: medium Вы играете в игру "Быки и коровы" со своим другом. Вы записываете секретное число и просите своего друга угадать, что это за число. Когда ваш друг делает предположение, вы даете ему подсказку со следующей информацией: Количество "быков", то есть цифры в предположении, которые находятся на правильной позиции. Количество "коров", то есть цифры в предположении, которые есть в вашем секретном числе, но находятся на неправильной позиции. Конкретно, это не-бычьи цифры в предположении, которые можно переставить так, чтобы они стали быками. Дано секретное число secret и предположение вашего друга guess, верните подсказку для предположения вашего друга. Подсказка должна быть в формате "xAyB", где x — количество быков, а y — количество коров. Обратите внимание, что и secret, и guess могут содержать повторяющиеся цифры. Пример:

Input: secret = "1807", guess = "7810"
Output: "1A3B"
Explanation: Bulls are connected with a '|' and cows are underlined:
"1807"
  |
"7810"

👨‍💻 Алгоритм: 1⃣Инициализация счетчиков: Инициализируйте количество быков и коров значениями ноль. Создайте хеш-таблицу для хранения символов строки secret и их частот. 2⃣Обход строки guess: Для каждого символа ch в строке guess: Если ch присутствует в строке secret: Если текущий символ ch совпадает с символом на той же позиции в secret (ch == secret[idx]): Увеличьте количество быков: bulls += 1. Обновите количество коров, если количество текущего символа в хеш-таблице отрицательное или равно нулю (то есть этот символ уже использовался для коров): cows -= int(h[ch] <= 0). Если текущий символ ch не совпадает с символом на той же позиции в secret (ch != secret[idx]): Увеличьте количество коров, если количество текущего символа в хеш-таблице больше нуля: cows += int(h[ch] > 0). Обновите хеш-таблицу, помечая текущий символ как использованный: h[ch] -= 1. 3⃣Возврат результата: Верните количество быков и коров в формате "xAyB". 😎 Решение:

class Solution:
    def getHint(self, secret: str, guess: str) -> str:
        from collections import defaultdict
        
        h = defaultdict(int)
        for ch in secret:
            h[ch] += 1

        bulls = 0
        cows = 0
        n = len(guess)
        secretArray = list(secret)
        guessArray = list(guess)

        for idx in range(n):
            ch = guessArray[idx]
            if ch in h:
                if ch == secretArray[idx]:
                    bulls += 1
                    if h[ch] <= 0:
                        cows -= 1
                else:
                    if h[ch] > 0:
                        cows += 1
                h[ch] -= 1

        return f"{bulls}A{cows}B"

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

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

Задача: 1057. Campus Bikes Сложность: medium В городке, изображенном на плоскости X-Y, есть n рабочих и m велосипедов, причем n <= m. Вам дан массив workers длины n, где workers[i] = [xi, yi] - положение i-го рабочего. Вам также дан массив bikes длины m, где bikes[j] = [xj, yj] - позиция j-го велосипеда. Все заданные позиции уникальны. Назначаем велосипед каждому работнику. Среди доступных велосипедов и работников мы выбираем пару (workeri, bikej) с наименьшим манхэттенским расстоянием между ними и назначаем велосипед этому работнику. Если существует несколько пар (workeri, bikej) с одинаковым наименьшим манхэттенским расстоянием, мы выбираем пару с наименьшим индексом работника. Если существует несколько способов сделать это, мы выбираем пару с наименьшим индексом велосипеда. Повторяем этот процесс до тех пор, пока не останется свободных работников. Возвращаем массив answer длины n, где answer[i] - индекс (с индексом 0) велосипеда, на который назначен i-й работник. Манхэттенское расстояние между двумя точками p1 и p2 равно Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|. Пример:

Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: [1,0]

👨‍💻 Алгоритм: 1⃣Для каждой пары (работник, велосипед) вычисли Манхэттенское расстояние и сохрани все пары вместе с расстоянием в список. 2⃣Отсортируй список пар по расстоянию, а затем по индексу работника и велосипеда. Назначь велосипеды работникам, следуя отсортированному списку пар и отслеживая, какие работники и велосипеды уже были использованы. 3⃣Заполни и верни массив назначений. 😎 Решение:

def assignBikes(workers, bikes):
    pairs = []
    
    for i, (wx, wy) in enumerate(workers):
        for j, (bx, by) in enumerate(bikes):
            distance = abs(wx - bx) + abs(wy - by)
            pairs.append((distance, i, j))
    
    pairs.sort()
    
    result = [-1] * len(workers)
    bike_taken = [False] * len(bikes)
    worker_assigned = [False] * len(workers)
    
    for distance, worker_idx, bike_idx in pairs:
        if not worker_assigned[worker_idx] and not bike_taken[bike_idx]:
            result[worker_idx] = bike_idx
            bike_taken[bike_idx] = True
            worker_assigned[worker_idx] = True
    
    return result

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

От обнаружения угрозы к ее мгновенному устранению Сложно обеспечивать безопасность компании, когда в инфраструктуре много разрозненных решений, бюджеты на ИБ сокращаются, а специалистов не хватает. Риски растут, атаки становятся сложнее, а рутинные задачи мешают реагировать быстро. Приглашаем на вебинар 12 августа в 11:00, где расскажем про Solar SIEM — платформу, которая объединяет функции SIEM и SOAR/IRP, ускоряя поиск угроз в 3 раза и экономя до 40% бюджета. Узнайте, как оптимально настроенная автоматизация снижает нагрузку на команду и закрывает дыры в безопасности. Сделайте работу ИБ-специалистов ности проще и эффективнее. Регистрируйтесь на вебинар, чтобы защитить бизнес без лишних затрат! Зарегистрироваться #реклама 16+ rt-solar.ru О рекламодателе

Задача: 33. Search in Rotated Sorted Array Сложность: medium Есть массив целых чисел nums, отсортированный в порядке возрастания (с уникальными значениями). Перед передачей в вашу функцию массив nums может быть повёрнут в неизвестном индексе поворота k (1 <= k < nums.length), так что результирующий массив будет иметь вид [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (с индексацией с нуля). Например, [0,1,2,4,5,6,7] может быть повёрнут в индексе поворота 3 и стать [4,5,6,7,0,1,2]. Для данного массива nums после возможного поворота и целого числа target, верните индекс target, если он есть в массиве, или -1, если его нет в массиве. Вы должны написать алгоритм с временной сложностью O(log n). Пример:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

👨‍💻 Алгоритм: 1️⃣Выполните двоичный поиск для определения индекса поворота, инициализируя границы области поиска значениями left = 0 и right = n - 1. Пока left < right: Пусть mid = left + (right - left) // 2. Если nums[mid] > nums[n - 1], это предполагает, что точка поворота находится справа от mid, следовательно, мы устанавливаем left = mid + 1. В противном случае, поворот может находиться на позиции mid или левее от mid, в этом случае мы должны установить right = mid. 2️⃣По завершении двоичного поиска мы имеем индекс поворота, обозначенный как pivot = left. nums состоит из двух отсортированных подмассивов, nums[0 ~ left - 1] и nums[left ~ n - 1]. 3️⃣Выполните двоичный поиск по подмассиву nums[0 ~ left - 1] для поиска target. Если target находится в этом подмассиве, верните его индекс. В противном случае выполните двоичный поиск по подмассиву nums[left ~ n - 1] для поиска target. Если target находится в этом подмассиве, верните его индекс. В противном случае верните -1. 😎 Решение:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        left, right = 0, n - 1

        while left <= right:
            mid = (left + right) // 2
            if nums[mid] > nums[-1]:
                left = mid + 1
            else:
                right = mid - 1

        def binarySearch(left_boundary, right_boundary, target):
            left, right = left_boundary, right_boundary
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] == target:
                    return mid
                elif nums[mid] > target:
                    right = mid - 1
                else:
                    left = mid + 1
            return -1

        if (answer := binarySearch(0, left - 1, target)) != -1:
            return answer

        return binarySearch(lef

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