Python | LeetCode

Подключите корпоративный ДМС в Совкомбанк Страхование Позаботьтесь о своей команде! ✨ ДМС от Совкомбанк Страхование – это решения под любой бюджет и потребности. 25 лет опыта, телемедицина, офисный врач и доступ к 10 000+ клиник по России. Сэкономьте до 30% с ДМС с франшизой и получите налоговые льготы. Собственная диспетчерская служба 24/7 всегда на связи. Здоровые сотрудники – успешный бизнес! Узнайте больше на сайте и оформите ДМС уже сегодня! 🏃‍♂️⚡ Перейти на сайт Финансовые услуги оказывает: ПАО "Совкомбанк", АО "Совкомбанк Страхование". #реклама sovcomins.ru О рекламодателе

Задача: 132. Palindrome Partitioning II Сложность: Hard Дана строка s. Разделите строку так, чтобы каждая подстрока разделения была палиндромом. Верните минимальное количество разрезов, необходимых для разделения строки s на палиндромы. Пример:

Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

👨‍💻 Алгоритм: 1️⃣Определение задачи и начальные условия: Алгоритм обратного отслеживания реализуется путём рекурсивного изучения кандидатов-подстрок. Мы определяем рекурсивный метод findMinimumCut, который находит минимальное количество разрезов для подстроки, начинающейся с индекса start и заканчивающейся на индексе end. Чтобы найти минимальное количество разрезов, мы также должны знать минимальное количество разрезов, которые были найдены ранее для других разделений на палиндромы. Эта информация отслеживается в переменной minimumCut. Начальное значение minimumCut будет равно максимально возможному количеству разрезов в строке, что равно длине строки минус один (т.е. разрез между каждым символом). 2️⃣Генерация подстрок и рекурсивный поиск: Теперь, когда мы знаем начальные и конечные индексы, мы должны сгенерировать все возможные подстроки, начиная с индекса start. Для этого мы будем держать начальный индекс постоянным. currentEndIndex обозначает конец текущей подстроки. 3️⃣Условие палиндрома и рекурсивное разделение: Если текущая подстрока является палиндромом, мы сделаем разрез после currentEndIndex и рекурсивно найдем минимальный разрез для оставшейся строки 😎 Решение:

class Solution:
    def minCut(self, s: str) -> int:
        return self.findMinimumCut(s, 0, len(s) - 1, len(s) - 1)

    def findMinimumCut(self, s: str, start: int, end: int, minimumCut: int) -> int:
        if start == end or self.isPalindrome(s, start, end):
            return 0
        for currentEndIndex in range(start, end + 1):
            if self.isPalindrome(s, start, currentEndIndex):
                minimumCut = min(
                    minimumCut,
                    1 + self.findMinimumCut(s, currentEndIndex + 1, end, minimumCut)
                )
        return minimumCut

    def isPalindrome(self, s: str, start: int, end: int) -> bool:
        while start < end:
            if s[start] != s[end]:
                return False
            start += 1
            end -= 1
        return True

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

EXLANTIX ET от EXEED. Уже в продаже! Гибридный кроссовер будущего! Премиальный гибридный автомобиль EXLANTIX ET в продаже! Запас хода 1180 км, Ускорение за 4,8 сек до 100 км/ч, 8 лет гарантии или 200 000 км! Благодаря надежным и современным системам EXLANTIX ET устанавливает новые стандарты гибридных автомобилей, обеспечивая защиту водителя и пассажиров при любых дорожных ситуациях. Хотите приобрести автомобиль или узнать больше? Узнать цену #реклама exeed.ru О рекламодателе

Задача: 1231. Divide Chocolate Сложность: hard У вас есть одна шоколадка, состоящая из нескольких кусочков. Каждый кусочек имеет свою сладость, заданную массивом сладости. Вы хотите поделиться шоколадом со своими k друзьями, поэтому начинаете разрезать шоколадку на k + 1 кусочков с помощью k разрезов, каждый кусочек состоит из нескольких последовательных кусочков. Будучи щедрым, вы съедите кусочек с минимальной общей сладостью, а остальные кусочки отдадите своим друзьям. Найдите максимальную общую сладость кусочка, который вы можете получить, оптимально разрезав шоколадку. Пример:

Input: sweetness = [1,2,3,4,5,6,7,8,9], k = 5
Output: 6

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

def maximizeSweetness(sweetness, k):
    def canDivide(minSweetness):
        current_sum = 0
        cuts = 0
        for sweet in sweetness:
            current_sum += sweet
            if current_sum >= minSweetness:
                cuts += 1
                current_sum = 0
        return cuts >= k + 1

    left, right = min(sweetness), sum(sweetness) // (k + 1)
    while left < right:
        mid = (left + right + 1) // 2
        if canDivide(mid):
            left = mid
        else:
            right = mid - 1
    return left

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

Задача: 130. Surrounded Regions Сложность: Medium Вам дана матрица размером m на n, которая содержит буквы 'X' и 'O'. Захватите регионы, которые окружены: Соединение: Ячейка соединена с соседними ячейками по горизонтали или вертикали. Регион: Для формирования региона соедините каждую ячейку 'O'. Окружение: Регион окружён ячейками 'X', если можно соединить регион с ячейками 'X', и ни одна из ячеек региона не находится на краю доски. Окруженный регион захватывается путём замены всех 'O' на 'X' в исходной матрице. Пример:

Input: board = [["X"]]

Output: [["X"]]

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

class Solution(object):
    def solve(self, board: List[List[str]]) -> None:
        if not board or not board[0]:
            return

        self.ROWS = len(board)
        self.COLS = len(board[0])

        from itertools import product
        borders = list(product(range(self.ROWS), [0, self.COLS - 1])) + list(
            product([0, self.ROWS - 1], range(self.COLS))
        )

        for row, col in borders:
            self.DFS(board, row, col)

        for r in range(self.ROWS):
            for c in range(self.COLS):
                if board[r][c] == "O":
                    board[r][c] = "X"
                elif board[r][c] == "E":
                    board[r][c] = "O"

    def DFS(self, board: List[List[str]], row: int, col: int) -> None:
        if board[row][col] != "O":
            return
        board[row][col] = "E"
        if col < self.COLS - 1:
            self.DFS(board, row, col + 1)
        if row < self.ROWS - 1:
            self.DFS(board, row + 1, col)
        if col > 0:
            self.DFS(board, row, col - 1)
        if row > 0:
            self.DFS(board, row - 1, col)

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

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

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

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

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

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

        while next_level:
            curr_level = next_level
            next_level = deque()

            while curr_level:
                node = curr_level.popleft()

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

            rightside.append(node.val)

        return rightside

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

Задача: 940. Distinct Subsequences II Сложность: hard Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7. Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (Например, "ace" является подпоследовательностью "abcde", а "aec" - нет. Пример:

Input: s = "abc"
Output: 7

👨‍💻 Алгоритм: 1⃣Определить матрицу DP, где dp[i][j] будет хранить количество подпоследовательностей строки s с длиной i, оканчивающихся символом j. 2⃣Инициализировать матрицу DP нулями. Пройти по каждому символу строки: Если символ еще не был встречен, все подпоследовательности до текущего символа + текущий символ. Если символ уже был встречен, учет всех подпоследовательностей, включающих текущий символ, с учетом предыдущих вхождений. 3⃣Вернуть сумму всех значений в DP по модулю 10^9 + 7. 😎 Решение:

MOD = 10**9 + 7

def countSubsequences(s):
    dp = [0] * 26
    for c in s:
        index = ord(c) - ord('a')
        dp[index] = (sum(dp) + 1) % MOD
    return sum(dp) % MOD

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

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

Задача: 681. Next Closest Time Сложность: medium Дано время, представленное в формате "ЧЧ:ММ". Сформируйте ближайшее следующее время, используя текущие цифры. Количество раз, которое можно использовать цифру, не ограничено. Можно предположить, что заданная строка всегда корректна. Например, "01:34", "12:09" являются корректными. "1:34", "12:9" являются некорректными. Пример:

Input: time = "19:34"
Output: "19:39"
Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later.
It is not 19:33, because this occurs 23 hours and 59 minutes later.

👨‍💻 Алгоритм: 1⃣Симулируйте ход часов, увеличивая время на одну минуту. Каждый раз, когда время увеличивается, если все цифры допустимы, верните текущее время. 2⃣Представьте время как целое число t в диапазоне 0 <= t < 24 * 60. Тогда часы равны t / 60, минуты равны t % 60. 3⃣Найдите каждую цифру часов и минут: часы / 10, часы % 10 и т.д. 😎 Решение:

class Solution:
    def nextClosestTime(self, time: str) -> str:
        cur = 60 * int(time[:2]) + int(time[3:])
        allowed = {int(c) for c in time if c != ':'}

        while True:
            cur = (cur + 1) % (24 * 60)
            digits = [cur // 60 // 10, cur // 60 % 10, cur % 60 // 10, cur % 60 % 10]
            if all(d in allowed for d in digits):
                return f"{cur // 60:02d}:{cur % 60:02d}"

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

Задача: 1503. Last Moment Before All Ants Fall Out of a Plank Сложность: medium У нас есть деревянная доска длиной n единиц. Некоторые муравьи ходят по доске, каждый муравей движется со скоростью 1 единица в секунду. Некоторые муравьи движутся влево, другие движутся вправо. Когда два муравья, движущиеся в разных направлениях, встречаются в какой-то точке, они меняют свои направления и продолжают двигаться дальше. Предполагается, что изменение направлений не занимает дополнительного времени. Когда муравей достигает одного из концов доски в момент времени t, он сразу же падает с доски. Дано целое число n и два целых массива left и right, обозначающие позиции муравьев, движущихся влево и вправо соответственно. Верните момент, когда последний(е) муравей(и) падает(ют) с доски. Пример:

Input: n = 4, left = [4,3], right = [0,1]
Output: 4
Explanation: In the image above:
-The ant at index 0 is named A and going to the right.
-The ant at index 1 is named B and going to the right.
-The ant at index 3 is named C and going to the left.
-The ant at index 4 is named D and going to the left.
The last moment when an ant was on the plank is t = 4 seconds. After that, it falls immediately out of the plank. (i.e., We can say that at t = 4.0000000001, there are no ants on the plank).

👨‍💻 Алгоритм: 1⃣Инициализируйте переменную ans значением 0. 2⃣Итерация по массиву left и обновление ans значением num, если оно больше текущего значения ans. 3⃣Итерация по массиву right и обновление ans значением n - num, если оно больше текущего значения ans. Верните значение ans. 😎 Решение:

class Solution:
    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:
        ans = 0
        for num in left:
            ans = max(ans, num)
        for num in right:
            ans = max(ans, n - num)
        return ans

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

Задача: 973. K Closest Points to Origin Сложность: medium Дан массив точек, где points[i] = [xi, yi] представляет собой точку на плоскости X-Y, и целое число k. Верните k точек, ближайших к началу координат (0, 0). Расстояние между двумя точками на плоскости X-Y является евклидовым расстоянием (то есть √((x1 - x2)² + (y1 - y2)²)). Вы можете вернуть ответ в любом порядке. Гарантируется, что ответ будет уникальным (за исключением порядка). Пример:

Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].

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

class Solution:
    def kClosest(self, points: list[list[int]], k: int) -> list[list[int]]:
        points.sort(key=self.squaredDistance)
        return points[:k]

    def squaredDistance(self, point: list[int]) -> int:
        return point[0] ** 2 + point[1] ** 2

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

Задача: 294. Flip Game II Сложность: medium Вы играете в игру Flip со своим другом. Вам дана строка currentState, которая содержит только символы '+' и '-'. Вы и ваш друг по очереди переворачиваете две последовательные "++" в "--". Игра заканчивается, когда игрок больше не может сделать ход, и, следовательно, другой игрок становится победителем. Верните true, если начальный игрок может гарантировать победу, и false в противном случае. Пример:

Input: currentState = "++++"
Output: true
Explanation: The starting player can guarantee a win by flipping the middle "++" to become "+--+".

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

class Solution:
    def canWin(self, currentState: str) -> bool:
        stateArray = list(currentState)
        
        for i in range(len(stateArray) - 1):
            if stateArray[i] == '+' and stateArray[i + 1] == '+':
                stateArray[i] = '-'
                stateArray[i + 1] = '-'
                newState = ''.join(stateArray)
                
                if not self.canWin(newState):
                    stateArray[i] = '+'
                    stateArray[i + 1] = '+'
                    return True
                
                stateArray[i] = '+'
                stateArray[i + 1] = '+'
        
        return False

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

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

Задача: 988. Smallest String Starting From Leaf Сложность: medium Дан корень бинарного дерева, где каждый узел имеет значение в диапазоне [0, 25], представляющее буквы от 'a' до 'z'. Верните лексикографически наименьшую строку, которая начинается с листа этого дерева и заканчивается у корня. Напоминаем, что любая более короткая префиксная строка является лексикографически меньшей. Например, "ab" лексикографически меньше, чем "aba". Лист узла - это узел, у которого нет потомков. Пример:

Input: root = [0,1,2,3,4,3,4]
Output: "dba"

👨‍💻 Алгоритм: 1⃣Инициализация и подготовка: Создайте переменную ans и установите ее значение как максимальное возможное (например, "~" для строк). Определите вспомогательную функцию dfs, которая будет выполнять обход дерева в глубину (DFS), принимая текущий узел и путь как аргументы. 2⃣Обход дерева: Если текущий узел пуст (null), просто вернитесь из функции. Добавьте текущий символ (соответствующий значению узла) в начало строки пути. Если текущий узел является листом (не имеет потомков), сравните текущий путь с ans и обновите ans, если текущий путь лексикографически меньше. Рекурсивно вызовите dfs для левого и правого потомков текущего узла. 3⃣Возврат результата: Вызовите функцию dfs с корневым узлом и пустым путем. Верните значение переменной ans, содержащее лексикографически наименьший путь от листа до корня. 😎 Решение:

class Solution:
    def smallestFromLeaf(self, root):
        def dfs(node, path):
            if not node:
                return
            path.append(chr(node.val + ord('a')))
            if not node.left and not node.right:
                s = "".join(reversed(path))
                if s < self.ans:
                    self.ans = s
            dfs(node.left, path)
            dfs(node.right, path)
            path.pop()
        
        self.ans = "~"
        dfs(root, [])
        return self.ans

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

Задача: 296. Best Meeting Point Сложность: hard Дан бинарный сетка размером m x n, где каждая 1 обозначает дом одного друга. Верните минимальное общее расстояние путешествия. Общее расстояние путешествия — это сумма расстояний между домами друзей и точкой встречи. Расстояние рассчитывается по Манхэттенскому расстоянию, где distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|. Пример:

Input: grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 6
Explanation: Given three friends living at (0,0), (0,4), and (2,2).
The point (0,2) is an ideal meeting point, as the total travel distance of 2 + 2 + 2 = 6 is minimal.
So return 6.

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

class Solution:
    def minTotalDistance(self, grid: list[list[int]]) -> int:
        minDistance = float('inf')
        for row in range(len(grid)):
            for col in range(len(grid[0])):
                distance = self.search(grid, row, col)
                minDistance = min(distance, minDistance)
        return minDistance

    def search(self, grid: list[list[int]], row: int, col: int) -> int:
        q = [(row, col, 0)]
        m = len(grid)
        n = len(grid[0])
        visited = [[False] * n for _ in range(m)]
        totalDistance = 0
        
        while q:
            r, c, d = q.pop(0)
            
            if r < 0 or c < 0 or r >= m or c >= n or visited[r][c]:
                continue
            
            if grid[r][c] == 1:
                totalDistance += d
            
            visited[r][c] = True
            
            q.append((r + 1, c, d + 1))
            q.append((r - 1, c, d + 1))
            q.append((r, c + 1, d + 1))
            q.append((r, c - 1, d + 1))
        
        return totalDistance

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

Задача: 1199. Minimum Time to Build Blocks Сложность: hard Вам дан список блоков, где blocks[i] = t означает, что на строительство i-го блока требуется t единиц времени. Блок может быть построен только одним рабочим. Рабочий может либо разделиться на двух рабочих (количество рабочих увеличивается на одного), либо построить блок и уйти домой. Оба решения требуют некоторого времени. Время, затраченное на разделение одного рабочего на двух, задано целым числом split. Обратите внимание, что если два рабочих разделяются одновременно, они разделяются параллельно, поэтому затраты времени будут равны split. Выведите минимальное время, необходимое для строительства всех блоков. Изначально есть только один рабочий. Пример:

Input: blocks = [1,2,3], split = 1
Output: 4
Explanation: Split 1 worker into 2, then assign the first worker to the last block and split the second worker into 2.
Then, use the two unassigned workers to build the first two blocks.
The cost is 1 + max(3, 1 + max(1, 2)) = 4.

👨‍💻 Алгоритм: 1⃣Подготовка кучи строительного времени: Инициализируйте кучу строительного времени, изначально содержащую все значения времени из массива blocks. 2⃣Обработка кучи: Пока в куче больше одного элемента: - извлеките минимальное значение из кучи, обозначим его как x. - извлеките следующее минимальное значение из кучи, обозначим его как y. - создайте новое время строительства, которое равно split + y, и вставьте его обратно в кучу. 3⃣Возврат результата: Когда в куче останется только одно значение, оно и будет минимальным временем, необходимым для строительства всех блоков. 😎 Решение:

import heapq

class Solution:
    def minBuildTime(self, blocks: List[int], split: int) -> int:
        heapq.heapify(blocks)
        
        while len(blocks) > 1:
            x = heapq.heappop(blocks)
            y = heapq.heappop(blocks)
            heapq.heappush(blocks, split + y)
        
        return heapq.heappop(blocks)

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

Задача: 1004. Max Consecutive Ones III Сложность: medium Если задан двоичный массив nums и целое число k, верните максимальное количество последовательных 1 в массиве, если можно перевернуть не более k 0. Пример:

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6

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

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        left = 0
        max_ones = 0
        zero_count = 0

        for right in range(len(nums)):
            if nums[right] == 0:
                zero_count += 1

            while zero_count > k:
                if nums[left] == 0:
                    zero_count -= 1
                left += 1

            max_ones = max(max_ones, right - left + 1)

        return max_ones

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

Задача: 227. Basic Calculator II Сложность: medium Дана строка s, представляющая выражение. Вычислите это выражение и верните его значение. Целочисленное деление должно округляться к нулю. Вы можете предположить, что данное выражение всегда является допустимым. Все промежуточные результаты будут находиться в диапазоне [-2^31, 2^31 - 1]. Примечание: Запрещено использовать какие-либо встроенные функции, которые вычисляют строки как математические выражения, такие как eval(). Пример:

Input: s = "3+2*2"
Output: 7

👨‍💻 Алгоритм: 1⃣Вместо использования стека, используем переменную lastNumber для отслеживания значения последнего вычисленного выражения. 2⃣Если операция сложения (+) или вычитания (-), добавляем lastNumber к результату вместо того, чтобы помещать его в стек. Текущее значение currentNumber будет обновлено на lastNumber для следующей итерации. 3⃣Если операция умножения (*) или деления (/), вычисляем выражение lastNumber * currentNumber и обновляем lastNumber с результатом выражения. Это значение будет добавлено к результату после сканирования всей строки. 😎 Решение:

class Solution:
    def calculate(self, s: str) -> int:
        length = len(s)
        if length == 0:
            return 0
        currentNumber = 0
        lastNumber = 0
        result = 0
        sign = '+'
        
        for i in range(length):
            currentChar = s[i]
            if currentChar.isdigit():
                currentNumber = (currentNumber * 10) + int(currentChar)
            if not currentChar.isdigit() and not currentChar.isspace() or i == length - 1:
                if sign == '+' or sign == '-':
                    result += lastNumber
                    lastNumber = currentNumber if sign == '+' else -currentNumber
                elif sign == '*':
                    lastNumber *= currentNumber
                elif sign == '/':
                    lastNumber //= currentNumber
                sign = currentChar
                currentNumber = 0
        result += lastNumber
        return result

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

Задача: CodeTestcaseTest ResultTest Result1187. Make Array Strictly Increasing Сложность: hard Даны два целочисленных массива arr1 и arr2. Верните минимальное количество операций (возможно, ноль), необходимых для того, чтобы сделать arr1 строго возрастающим. В одной операции вы можете выбрать два индекса 0 <= i < arr1.length и 0 <= j < arr2.length и выполнить присваивание arr1[i] = arr2[j]. Если нет способа сделать arr1 строго возрастающим, верните -1. Пример:

Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7].

👨‍💻 Алгоритм: 1⃣Сначала отсортируйте массив arr2 и инициализируйте хэш-таблицу dp для хранения промежуточных результатов. Определите функцию dfs(i, prev), которая вычисляет минимальное количество операций для сортировки массива arr1, начиная с индекса i, при условии, что предыдущий элемент равен prev. Если результат для (i, prev) уже существует в dp, то просто верните сохраненное значение. 2⃣Внутри функции dfs инициализируйте переменную cost значением float('inf'). Если arr1[i] больше, чем prev, обновите значение cost результатом вызова dfs(i + 1, arr1[i]). Используйте бинарный поиск, чтобы найти индекс idx наименьшего значения в arr2, которое больше prev. Если такой индекс существует, обновите значение cost результатом минимального значения между текущим значением cost и 1 + dfs(i + 1, arr2[idx]). 3⃣После всех вычислений обновите dp[(i, prev)] значением cost и верните cost. В конце вызовите dfs(0, -1) и верните его значение, если оно не равно float('inf'); в противном случае верните -1. 😎 Решение:

class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        arr2 = sorted(set(arr2))
        dp = {}
        
        def dfs(i, prev):
            if i == len(arr1):
                return 0
            if (i, prev) in dp:
                return dp[(i, prev)]
            
            cost = 2001
            if arr1[i] > prev:
                cost = dfs(i + 1, arr1[i])
            idx = bisect.bisect_right(arr2, prev)
            if idx < len(arr2):
                cost = min(cost, 1 + dfs(i + 1, arr2[idx]))
            
            dp[(i, prev)] = cost
            return cost
        
        result = dfs(0, -1)
        return result if result < 2001 else -1

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

Как навести порядок в работе? ✅ Вместо личных чатов — мессенджер только для коллег. ✅ Вместо ссылки на созвон и долгих поисков слотов — планерка в один клик. ✅ Вместо задачи на почте — задачка в трекере с четким чек-листом. ✅ Вместо страха белого листа — смелый креатив и рекомендации от ИИ-помощника. Вместо десятка программ — один Битрикс24. Зарегистрироваться #реклама 16+ office-online.bitrix24.ru О рекламодателе