Задача: 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

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

Задача: 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

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

Задача: 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)

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

Задача: 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

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

Задача: 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

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

Задача: 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

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

Задача: 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

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

Задача: 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

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

Задача: 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}"

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

Задача: 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

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

Задача: 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

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

Задача: 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)

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

Задача: 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

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

Задача: 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

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

Задача: 1161. Maximum Level Sum of a Binary Tree
Сложность: medium

Дано корневое дерево, уровень корня которого равен 1, уровень его детей равен 2 и так далее.

Верните наименьший уровень x, такой что сумма всех значений узлов на уровне x максимальна.

Пример:

Input: root = [1,7,0,7,-8,null,null]
Output: 2
Explanation: 
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.

👨‍💻 Алгоритм:

1⃣Создайте целочисленную переменную maxSum для отслеживания максимальной суммы значений узлов на любом уровне, начав с большого отрицательного значения. Создайте переменную ans для хранения ответа на задачу. Создайте переменную level для хранения текущего уровня, через который мы проходим, и инициализируйте её значением 0. Инициализируйте очередь q типа TreeNode и добавьте в неё корень.

2⃣Выполните обход в ширину (BFS) до тех пор, пока очередь не станет пустой: увеличьте level на 1 и инициализируйте sumAtCurrentLevel = 0 для вычисления суммы всех значений узлов на этом уровне. Проходите через все узлы на уровне, используя только q.size() количество узлов. Внутри этого внутреннего цикла извлекайте все узлы на текущем уровне один за другим, добавляя их значения к sumAtCurrentLevel и добавляя левых и правых детей (если они существуют) в очередь. Поймите, что после прохождения всех узлов на уровне в очереди остаются только узлы уровня +1.

3⃣После прохождения всех узлов на уровне проверьте, больше ли sumAtCurrentLevel, чем maxSum. Если maxSum < sumAtCurrentLevel, обновите переменную ответа на ans = level и установите maxSum = sumAtCurrentLevel. Верните ans.

😎 Решение:

from collections import deque

class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        maxSum = float('-inf')
        ans = 0
        level = 0
        q = deque([root])
        
        while q:
            level += 1
            sumAtCurrentLevel = 0
            for _ in range(len(q)):
                node = q.popleft()
                sumAtCurrentLevel += node.val
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            
            if maxSum < sumAtCurrentLevel:
                maxSum = sumAtCurrentLevel
                ans = level
        
        return ans

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

Задача: 1406. Stone Game III
Сложность: hard

Алиса и Боб продолжают свои игры с кучами камней. Камни расположены в ряд, и каждый камень имеет ассоциированное значение, которое представлено целым числом в массиве stoneValue.
Алиса и Боб ходят по очереди, начиная с Алисы. В свой ход каждый игрок может взять 1, 2 или 3 камня из первых оставшихся камней в ряду.

Счет каждого игрока равен сумме значений взятых камней. Изначально счет каждого игрока равен 0.
Цель игры — закончить с наивысшим счетом, и победителем становится игрок с наивысшим счетом, при этом возможна ничья. Игра продолжается, пока все камни не будут взяты.

Предположим, что Алиса и Боб играют оптимально.
Верните "Alice", если Алиса выиграет, "Bob", если выиграет Боб, или "Tie", если они закончат игру с одинаковым счетом.

Пример:

Input: stoneValue = [1,2,3,7]
Output: "Bob"
Explanation: Alice will always lose. Her best move will be to take three piles and the score become 6. Now the score of Bob is 7 and Bob wins.

👨‍💻 Алгоритм:

1⃣Инициализируйте массив dp размером n+1 и установите dp[n] в 0.

2⃣Итеративно обновляйте dp[i] для всех i от n-1 до 0, вычисляя максимальную разницу в баллах, которые могут получить игроки при оптимальной игре.

3⃣Определите победителя, сравнивая dp[0] с 0: если больше, победит Алиса; если меньше, победит Боб; если равно, будет ничья.

😎 Решение:

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        dp = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            dp[i] = stoneValue[i] - dp[i + 1]
            if i + 2 <= n:
                dp[i] = max(dp[i], stoneValue[i] + stoneValue[i + 1] - dp[i + 2])
            if i + 3 <= n:
                dp[i] = max(dp[i], stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] - dp[i + 3])
        if dp[0] > 0:
            return "Alice"
        elif dp[0] < 0:
            return "Bob"
        else:
            return "Tie"

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

Задача: 617. Merge Two Binary Trees
Сложность: medium

Вам даны два бинарных дерева root1 и root2. Представьте, что при наложении одного из них на другое некоторые узлы двух деревьев перекрываются, а другие - нет. Вам нужно объединить эти два дерева в новое бинарное дерево. Правило слияния таково: если два узла пересекаются, то в качестве нового значения объединенного узла используется сумма значений узлов. В противном случае в качестве узла нового дерева будет использоваться узел NOT null. Возвращается объединенное дерево. Примечание: Процесс объединения должен начинаться с корневых узлов обоих деревьев.

Пример:

Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]

👨‍💻 Алгоритм:

1⃣Если один из узлов пуст (null), возвращаем другой узел. Если оба узла пустые, возвращаем null.

2⃣Если оба узла не пустые, создаем новый узел, значение которого равно сумме значений двух узлов. Рекурсивно объединяем левые и правые поддеревья.

3⃣Возвращаем новый узел, который является корнем объединенного дерева.

😎 Решение:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def mergeTrees(root1, root2):
    if not root1:
        return root2
    if not root2:
        return root1
    
    mergedNode = TreeNode(root1.val + root2.val)
    mergedNode.left = mergeTrees(root1.left, root2.left)
    mergedNode.right = mergeTrees(root1.right, root2.right)
    
    return mergedNode

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

Задача: 924. Minimize Malware Spread
Сложность: hard

Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока не останется ни одного узла, который можно было бы заразить таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим из initial ровно один узел. Верните тот узел, удаление которого минимизирует M(initial). Если можно удалить несколько узлов, чтобы минимизировать M(initial), верните такой узел с наименьшим индексом. Обратите внимание, что если узел был удален из начального списка зараженных узлов, он все равно может быть заражен позже из-за распространения вредоносного ПО.

Пример:

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20

👨‍💻 Алгоритм:

1⃣Определить количество зараженных узлов после распространения вредоносного ПО для исходного списка initial.

2⃣Для каждого узла в initial удалить его и вычислить количество зараженных узлов после распространения вредоносного ПО.

3⃣Найти узел, удаление которого минимизирует количество зараженных узлов. Если есть несколько таких узлов, выбрать узел с наименьшим индексом.

😎 Решение:

def minMalwareSpread(graph, initial):
    def dfs(node, infected):
        for neighbor in range(len(graph)):
            if graph[node][neighbor] == 1 and neighbor not in infected:
                infected.add(neighbor)
                dfs(neighbor, infected)

    n = len(graph)
    initial_set = set(initial)
    initial.sort()
    min_infected = float('inf')
    best_node = initial[0]
    
    for node in initial:
        infected = set(initial_set)
        infected.remove(node)
        for i in initial_set:
            if i != node:
                dfs(i, infected)
        if len(infected) < min_infected:
            min_infected = len(infected)
            best_node = node
    
    return best_node

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

Задача: 1165. Single-Row Keyboard
Сложность: easy

Есть специальная клавиатура, на которой все клавиши расположены в один ряд.

Дана строка keyboard длиной 26, указывающая на раскладку клавиатуры (индексирована от 0 до 25). Изначально ваш палец находится на индексе 0. Чтобы напечатать символ, нужно переместить палец на индекс нужного символа. Время, затраченное на перемещение пальца с индекса i на индекс j, равно |i - j|.

Вам нужно напечатать строку word. Напишите функцию для расчета времени, необходимого для её набора одним пальцем.

Пример:

Input: keyboard = "abcdefghijklmnopqrstuvwxyz", word = "cba"
Output: 4
Explanation: The index moves from 0 to 2 to write 'c' then to 1 to write 'b' then to 0 again to write 'a'.
Total time = 2 + 1 + 1 = 4.

👨‍💻 Алгоритм:

1⃣Клавиатура содержит уникальные строчные английские буквы, поэтому мы можем сопоставить её с массивом размера 26. Создадим массив размера 26, назовём его keyIndices. Сохраните индекс каждой буквы в этом массиве, проходя по строке keyboard. Инициализируйте переменную result значением 0, которая будет хранить сумму всех расстояний. Объявите переменную prev, которая будет хранить индекс предыдущей клавиши. Поскольку начальная позиция равна 0, инициализируйте её значением 0.

2⃣Проходите по строке word буква за буквой. Для каждой буквы c добавьте ∣prev−indexOf(c)∣ к result. Обновите prev до индекса c.

3⃣Повторите шаги 6 и 7 для всех букв. В конце прохода result будет содержать итоговое время, необходимое для набора слова.

😎 Решение:

class Solution:
    def calculateTime(self, keyboard: str, word: str) -> int:
        key_indices = [-1] * 26
        for i, c in enumerate(keyboard):
            key_indices[ord(c) - ord('a')] = i
        
        prev = 0
        result = 0
        
        for c in word:
            index = key_indices[ord(c) - ord('a')]
            result += abs(prev - index)
            prev = index
        
        return result

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

Задача: 1000. Minimum Cost to Merge Stones
Сложность: hard

Имеется n кучек камней, расположенных в ряд. В i-й куче находятся камни stones[i]. Ход состоит в объединении ровно k последовательных куч в одну кучу, и стоимость этого хода равна общему количеству камней в этих k кучах. Верните минимальную стоимость объединения всех куч камней в одну кучу. Если это невозможно, верните -1.

Пример:

Input: stones = [3,2,4,1], k = 2
Output: 20

👨‍💻 Алгоритм:

1⃣Проверка на возможность объединения:
Проверьте, можно ли объединить все кучи в одну, если количество куч n не равно 1 по модулю k-1. Если нет, верните -1.

2⃣Инициализация и динамическое программирование:
Создайте таблицу dp для хранения минимальных затрат на объединение подмассивов камней.
Используйте таблицу prefix для хранения префиксных сумм камней, чтобы быстро вычислять сумму камней в подмассиве.

3⃣Заполнение таблицы dp:
Заполните таблицу dp минимальными затратами на объединение подмассивов камней, используя динамическое программирование.
Для каждого подмассива длиной от k до n, найдите минимальную стоимость его объединения.

😎 Решение:

class Solution:
    def mergeStones(self, stones: List[int], k: int) -> int:
        n = len(stones)
        if (n - 1) % (k - 1) != 0:
            return -1

        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + stones[i]

        dp = [[0] * n for _ in range(n)]
        for m in range(k, n + 1):
            for i in range(n - m + 1):
                j = i + m - 1
                dp[i][j] = min(dp[i][t] + dp[t + 1][j] for t in range(i, j, k - 1))
                if (j - i) % (k - 1) == 0:
                    dp[i][j] += prefix[j + 1] - prefix[i]

        return dp[0][n - 1]

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

Задача: 482. License Key Formatting
Сложность: easy

Вам дан лицензионный ключ, представленный в виде строки s, которая состоит только из буквенно-цифровых символов и тире. Строка разделена на n + 1 групп с помощью n тире. Вам также дано целое число k.

Мы хотим переформатировать строку s так, чтобы каждая группа содержала ровно k символов, за исключением первой группы, которая может быть короче k, но все же должна содержать хотя бы один символ. Кроме того, между двумя группами должно быть вставлено тире, и все строчные буквы следует преобразовать в прописные.

Верните переформатированный лицензионный ключ.

Пример:

Input: s = "5F3Z-2e-9-w", k = 4
Output: "5F3Z-2E9W"
Explanation: The string s has been split into two parts, each part has 4 characters.
Note that the two extra dashes are not needed and can be removed.

👨‍💻 Алгоритм:

1⃣Инициализация
Установите count в 0 для подсчета символов в текущей группе. Установите ans в пустую строку для хранения конечного результата.

2⃣Итерация по входной строке в обратном порядке
Пропускайте символы '-'. Если текущий символ не '-', добавьте его в ans и увеличьте count на 1. Если count достигает k, добавьте '-' в ans и сбросьте count.

3⃣Завершение
Проверьте, есть ли в конце строки ans тире, и удалите его, если оно есть. Переверните строку ans и верните её.

😎 Решение:

class Solution:
    def licenseKeyFormatting(self, s: str, k: int) -> str:
        count = 0
        ans = []

        for char in reversed(s):
            if char != '-':
                ans.append(char.upper())
                count += 1
                if count == k:
                    ans.append('-')
                    count = 0
        
        if ans and ans[-1] == '-':
            ans.pop()

        return ''.join(reversed(ans))

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