Задача: 980. Unique Paths III
Сложность: hard


Вам дан целочисленный массив grid размером m x n, где grid[i][j] может быть:

1, представляющая начальную клетку. Существует ровно одна начальная клетка.
2, представляющая конечную клетку. Существует ровно одна конечная клетка.
0, представляющая пустые клетки, по которым можно ходить.
-1, представляющая препятствия, по которым нельзя ходить.
Верните количество 4-направленных путей от начальной клетки до конечной клетки, которые проходят по каждой непересекаемой клетке ровно один раз.

Пример:

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths: 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

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

1⃣Как видно, метод обратного отслеживания (backtracking) является методологией для решения определенного типа задач.

2⃣Для задачи обратного отслеживания можно сказать, что существует тысяча реализаций обратного отслеживания на тысячу людей, как будет видно из дальнейшей реализации.

3⃣Здесь мы просто покажем один пример реализации, следуя псевдокоду, показанному в разделе интуиции.

😎 Решение:

class Solution:
    def uniquePathsIII(self, grid: list[list[int]]) -> int:
        def backtrack(row, col, remain):
            if grid[row][col] == 2 and remain == 1:
                self.path_count += 1
                return

            temp = grid[row][col]
            grid[row][col] = -4
            remain -= 1

            for ro, co in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                next_row, next_col = row + ro, col + co

                if 0 <= next_row < self.rows and 0 <= next_col < self.cols and grid[next_row][next_col] >= 0:
                    backtrack(next_row, next_col, remain)

            grid[row][col] = temp

        non_obstacles = 0
        start_row = start_col = 0

        self.rows, self.cols = len(grid), len(grid[0])

        for row in range(self.rows):
            for col in range(self.cols):
                if grid[row][col] >= 0:
                    non_obstacles += 1
                if grid[row][col] == 1:
                    start_row, start_col = row, col

        self.path_count = 0
        backtrack(start_row, start_col, non_obstacles)

        return self.path_count

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

Задача: 755. Pour Water
Сложность: medium

Вы стоите в позиции 0 на бесконечной числовой прямой. В позиции target находится пункт назначения. Вы можете сделать некоторое количество ходов numMoves так, чтобы: на каждом ходу вы могли пойти либо налево, либо направо. Во время i-го хода (начиная с i == 1 до i == numMoves) вы делаете i шагов в выбранном направлении. Учитывая целое число target, верните минимальное количество ходов (т.е. минимальное numMoves), необходимое для достижения пункта назначения.

Пример:

Input: heights = [2,1,1,2,1,2,2], volume = 4, k = 3
Output: [2,2,2,3,2,2,2]

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

1⃣Инициализируйте цикл для добавления объема воды.

2⃣Для каждой единицы воды: Проверьте, может ли вода двигаться влево и упасть на более низкий уровень. Если нет, проверьте, может ли вода двигаться вправо и упасть на более низкий уровень. Если нет, добавьте воду в текущую позицию.

3⃣Повторите шаг 2, пока не будет добавлен весь объем воды.

😎 Решение:

def pourWater(heights, volume, k):
    for _ in range(volume):
        drop_index = k
        for d in (-1, 1):
            i = k
            while 0 <= i + d < len(heights) and heights[i + d] <= heights[i]:
                if heights[i + d] < heights[i]:
                    drop_index = i + d
                i += d
            if drop_index != k:
                break
        heights[drop_index] += 1
    return heights

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

Задача: 1129. Shortest Path with Alternating Colors
Сложность: medium

Вам дано целое число n, количество узлов в ориентированном графе, где узлы помечены от 0 до n - 1. Каждое ребро в этом графе может быть красным или синим, и могут быть самопетли и параллельные ребра.

Вам даны два массива redEdges и blueEdges, где:
redEdges[i] = [ai, bi] указывает, что в графе существует направленное красное ребро от узла ai к узлу bi, и
blueEdges[j] = [uj, vj] указывает, что в графе существует направленное синее ребро от узла uj к узлу vj.
Верните массив answer длины n, где каждый answer[x] — это длина кратчайшего пути от узла 0 до узла x, такого что цвета ребер чередуются вдоль пути, или -1, если такого пути не существует.

Пример:

Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output: [0,1,-1]

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

1⃣Создание структуры данных и инициализация:
Создайте список смежности adj, который будет содержать пары (сосед, цвет) для каждого узла.
Создайте массив answer длиной n, инициализированный значением -1, чтобы хранить длину кратчайшего пути для каждого узла.
Создайте 2D массив visit для отслеживания, были ли узлы посещены с использованием ребра определённого цвета.

2⃣Инициализация очереди и начальных условий:
Создайте очередь для хранения трёх значений (узел, количество шагов, цвет предыдущего ребра).
Добавьте в очередь начальный узел (0, 0, -1) и установите visit[0][0] и visit[0][1] в true, так как повторное посещение узла 0 бессмысленно.

3⃣Обработка очереди и обновление результата:
Пока очередь не пуста, извлекайте элемент из очереди и получайте (узел, количество шагов, цвет предыдущего ребра).
Для каждого соседа, если сосед не был посещён с использованием ребра текущего цвета и текущий цвет не равен предыдущему, обновите массив answer и добавьте соседа в очередь.

😎 Решение:

from collections import deque, defaultdict

class Solution:
    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
        adj = defaultdict(list)
        for a, b in redEdges:
            adj[a].append((b, 0))
        for u, v in blueEdges:
            adj[u].append((v, 1))
        
        answer = [-1] * n
        visit = [[False, False] for _ in range(n)]
        queue = deque([(0, 0, -1)])
        answer[0] = 0
        visit[0][0] = visit[0][1] = True
        
        while queue:
            node, steps, prevColor = queue.popleft()
            
            for neighbor, color in adj[node]:
                if not visit[neighbor][color] and color != prevColor:
                    if answer[neighbor] == -1:
                        answer[neighbor] = steps + 1
                    visit[neighbor][color] = True
                    queue.append((neighbor, steps + 1, color))
        
        return answer

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

Задача: 328. Odd Even Linked List
Сложность: medium

Дан заголовок односвязного списка. Сгруппируйте все узлы с нечетными индексами вместе, а затем узлы с четными индексами, и верните упорядоченный список.

Первый узел считается нечетным, второй узел — четным и так далее.

Учтите, что относительный порядок внутри обеих групп (четной и нечетной) должен оставаться таким же, как в исходном списке.

Вы должны решить задачу с дополнительной сложностью по памяти O(1) и временной сложностью O(n).

Пример:

Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]

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

1⃣Инициализация указателей:
Создайте указатели odd и even для работы с нечетными и четными узлами, соответственно. Инициализируйте odd началом списка head, а even — следующим узлом head.next. Также создайте указатель evenHead для сохранения начала четного списка.

2⃣Разделение списка:
Используйте цикл для прохождения списка, перенаправляя нечетные узлы в oddList, а четные узлы в evenList. Обновляйте указатели odd и even в процессе итерации.

3⃣Соединение списков:
После окончания цикла соедините конец нечетного списка с началом четного списка, используя указатель evenHead.

😎 Решение:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if not head:
            return None
        odd, even = head, head.next
        evenHead = even
        
        while even and even.next:
            odd.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next
        
        odd.next = evenHead
        return head

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

Задача: 1049. Last Stone Weight II
Сложность: medium

Вам дан массив целых чисел stones, где stones[i] - вес i-го камня. Мы играем в игру с камнями. На каждом ходу мы выбираем два любых камня и разбиваем их вместе. Предположим, что камни имеют веса x и y, причем x <= y. Результат разбивания таков: если x == y, оба камня уничтожаются, а если x != y, камень веса x уничтожается, а камень веса y приобретает новый вес y - x. В конце игры остается не более одного камня. Верните наименьший возможный вес оставшегося камня. Если камней не осталось, верните 0.

Пример:

Input: stones = [2,7,4,1,8,1]
Output: 1

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

1⃣Используй метод динамического программирования, чтобы проверить, можно ли разделить камни на две группы с равной суммой.

2⃣Определи, какие веса можно достичь, используя половину суммы всех камней.

3⃣Найди наибольшую достижимую сумму, которая меньше или равна половине общей суммы, и верни разницу между общей суммой и удвоенной этой суммой.Верни максимальную длину среди всех цепочек.

😎 Решение:

def lastStoneWeightII(stones):
    total_sum = sum(stones)
    half_sum = total_sum // 2
    dp = [0] * (half_sum + 1)

    for stone in stones:
        for j in range(half_sum, stone - 1, -1):
            dp[j] = max(dp[j], dp[j - stone] + stone)

    return total_sum - 2 * dp[half_sum]

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

Задача: 1217. Minimum Cost to Move Chips to The Same Position
Сложность: easy

У нас есть n фишек, где позиция i-й фишки равна position[i].

Нам нужно переместить все фишки в одну и ту же позицию. За один шаг мы можем изменить позицию i-й фишки с position[i] на:
position[i] + 2 или position[i] - 2 с затратами = 0.
position[i] + 1 или position[i] - 1 с затратами = 1.
Верните минимальные затраты, необходимые для перемещения всех фишек в одну и ту же позицию.

Пример:

Input: position = [2,2,2,3,3]
Output: 2
Explanation: We can move the two chips at position  3 to position 2. Each move has cost = 1. The total cost = 2.

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

1⃣Посчитать количество фишек на четных и нечетных позициях.

2⃣Сравнить количество фишек на четных и нечетных позициях.

3⃣Вернуть минимальное количество фишек как минимальную стоимость для перемещения всех фишек в одну позицию.

😎 Решение:

class Solution:
    def minCostToMoveChips(self, position: List[int]) -> int:
        even_count = sum(1 for pos in position if pos % 2 == 0)
        odd_count = len(position) - even_count
        return min(even_count, odd_count)

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

Задача: 669. Trim a Binary Search Tree
Сложность: medium

Дано корневое дерево двоичного поиска и нижняя и верхняя границы как low и high. Обрежьте дерево так, чтобы все его элементы лежали в диапазоне [low, high]. Обрезка дерева не должна изменять относительную структуру элементов, которые останутся в дереве (то есть любой потомок узла должен оставаться потомком). Можно доказать, что существует единственный ответ.

Верните корень обрезанного дерева двоичного поиска. Обратите внимание, что корень может измениться в зависимости от заданных границ.

Пример:

Input: root = [1,0,2], low = 1, high = 2
Output: [1,null,2]

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

1⃣Если node.val > high, то обрезанное двоичное дерево должно находиться слева от узла.

2⃣Если node.val < low, то обрезанное двоичное дерево должно находиться справа от узла.

3⃣В противном случае обрезаем обе стороны дерева.

😎 Решение:

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

class Solution:
    def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
        if not root:
            return None
        if root.val > high:
            return self.trimBST(root.left, low, high)
        if root.val < low:
            return self.trimBST(root.right, low, high)
        root.left = self.trimBST(root.left, low, high)
        root.right = self.trimBST(root.right, low, high)
        return root

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

Задача: 1119. Remove Vowels from a String
Сложность: easy

Дана строка s, удалите из нее гласные 'a', 'e', 'i', 'o' и 'u' и верните новую строку.

Пример:

Input: s = "leetcodeisacommunityforcoders"
Output: "ltcdscmmntyfrcdrs"

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

1⃣Создайте метод isVowel(), который возвращает true, если переданный символ является одной из гласных [a, e, i, o, u], и false в противном случае.

2⃣Инициализируйте пустую строку ans.

3⃣Пройдитесь по каждому символу в строке s, и для каждого символа c проверьте, является ли он гласной, используя isVowel(c). Если нет, добавьте символ в строку ans. В конце верните строку ans.

😎 Решение:

class Solution:
    def removeVowels(self, s: str) -> str:
        def isVowel(c):
            return c in 'aeiou'
        
        ans = []
        for char in s:
            if not isVowel(char):
                ans.append(char)
                
        return ''.join(ans)

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

Задача: 198. House Robber
Сложность: medium

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

Учитывая целочисленный массив nums, представляющий сумму денег в каждом доме, верните максимальную сумму денег, которую вы можете ограбить этой ночью, не подняв тревогу.

Пример:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

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

1️⃣Определите функцию robFrom(), которая принимает индекс дома, который грабитель должен осмотреть, и массив nums, необходимый для вычислений. На каждом шаге рекурсивного вызова у грабителя есть два варианта: ограбить текущий дом или нет.

2️⃣Если грабитель выбирает ограбить текущий дом, он должен пропустить следующий, т.е. вызвать robFrom(i + 2, nums). Ответ будет равен значению robFrom(i + 2, nums) плюс сумма, которую грабитель получит, ограбив текущий дом, т.е. nums[i]. В противном случае он может перейти к следующему дому и вернуть прибыль, которую он получит в подзадаче, т.е. robFrom(i + 1, nums).

3️⃣Нужно найти, сохранить в кэше и вернуть максимум из этих двух вариантов на каждом шаге. robFrom(0, nums) даст ответ на всю задачу.

😎 Решение:

class Solution:

    def __init__(self):
        self.memo = {}

    def rob(self, nums: List[int]) -> int:
        self.memo = {}
        return self.robFrom(0, nums)

    def robFrom(self, i, nums):
        if i >= len(nums):
            return 0
        if i in self.memo:
            return self.memo[i]
        ans = max(
            self.robFrom(i + 1, nums), self.robFrom(i + 2, nums) + nums[i]
        )
        self.memo[i] = ans
        return ans

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

Задача: 860. Lemonade Change
Сложность: easy

На лимонадной стойке каждый лимонад стоит $5. Покупатели стоят в очереди, чтобы купить лимонад, и заказывают по одному (в порядке, указанном в массиве bills). Каждый покупатель покупает только один лимонад и платит либо $5, $10, либо $20. Вы должны предоставить правильную сдачу каждому покупателю, чтобы чистая сделка была такой, что покупатель платит $5.

Обратите внимание, что изначально у вас нет никакой сдачи.

Дан целочисленный массив bills, где bills[i] — купюра, которой платит i-й покупатель. Верните true, если вы можете предоставить каждому покупателю правильную сдачу, или false в противном случае.

Пример:

Input: bills = [5,5,5,10,20]
Output: true
Explanation: 
From the first 3 customers, we collect three $5 bills in order.
From the fourth customer, we collect a $10 bill and give back a $5.
From the fifth customer, we give a $10 bill and a $5 bill.
Since all customers got correct change, we output true.

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

1⃣Инициализируем переменные для хранения количества пятерок и десяток. Если покупатель платит $5, добавляем эту купюру в наш запас.

2⃣Если покупатель платит $10, проверяем наличие пятерки для сдачи. Если пятерки нет, возвращаем false. В противном случае, уменьшаем количество пятерок и увеличиваем количество десяток.

3⃣Если покупатель платит $20, сначала пытаемся дать сдачу десяткой и пятеркой. Если это невозможно, проверяем наличие трех пятерок. Если не можем дать сдачу, возвращаем false. После обработки всех покупателей, возвращаем true.

😎 Решение:

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five = ten = 0
        for bill in bills:
            if bill == 5:
                five += 1
            elif bill == 10:
                if five == 0: return False
                five -= 1
                ten += 1
            else:
                if five > 0 and ten > 0:
                    five -= 1
                    ten -= 1
                elif five >= 3:
                    five -= 3
                else:
                    return False
        return True

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

Задача: 270. Closest Binary Search Tree Value
Сложность: easy

Дано корень бинарного дерева поиска и целевое значение. Верните значение в дереве, которое ближе всего к целевому. Если существует несколько ответов, выведите наименьшее.

Пример:

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

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

1️⃣Построить массив с помощью inorder обхода:
Выполнить inorder обход дерева и собрать элементы в отсортированный массив.

2️⃣Найти ближайший элемент:
Пройти по массиву и определить элемент, наиболее близкий к целевому значению.

3️⃣Выбрать наименьший из ближайших элементов:
Если несколько элементов одинаково близки к целевому значению, выбрать наименьший из них.

😎 Решение:

class Solution:
    def closestValue(self, root: TreeNode, target: float) -> int:
        closest = root.val
        while root:
            closest = min(root.val, closest, key=lambda x: (abs(target - x), x))
            root = root.left if target < root.val else root.right
        return closest

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

Задача: 1031. Maximum Sum of Two Non-Overlapping Subarrays
Сложность: medium

Если задан целочисленный массив nums и два целых числа firstLen и secondLen, верните максимальную сумму элементов в двух непересекающихся подмассивах с длинами firstLen и secondLen. Массив с длиной firstLen может находиться до или после массива с длиной secondLen, но они должны быть непересекающимися. Подмассив - это смежная часть массива.

Пример:

Input: nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2
Output: 20

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

1⃣Предварительные вычисления:
Вычислите сумму всех подмассивов длины firstLen и secondLen и сохраните их в списках.

2⃣Поиск максимальной суммы:
Переберите все возможные позиции для подмассива длины firstLen и для каждого такого подмассива найдите максимальную сумму для подмассива длины secondLen, который не пересекается с текущим подмассивом длины firstLen.

3⃣Сравнение двух случаев:
Рассмотрите оба случая: подмассив длины firstLen до подмассива длины secondLen и подмассив длины secondLen до подмассива длины firstLen. Найдите максимальную сумму для каждого случая.

😎 Решение:

class Solution:
    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:
        def maxSumNonOverlap(nums, firstLen, secondLen):
            n = len(nums)
            prefix = [0] * (n + 1)
            for i in range(n):
                prefix[i + 1] = prefix[i] + nums[i]

            max_first = [0] * n
            for i in range(firstLen - 1, n):
                max_first[i] = max(max_first[i - 1], prefix[i + 1] - prefix[i + 1 - firstLen])

            max_second = [0] * n
            for i in range(secondLen - 1, n):
                max_second[i] = max(max_second[i - 1], prefix[i + 1] - prefix[i + 1 - secondLen])

            max_sum = 0
            for i in range(firstLen + secondLen - 1, n):
                max_sum = max(max_sum, max_first[i - secondLen] + (prefix[i + 1] - prefix[i + 1 - secondLen]))

            return max_sum

        return max(maxSumNonOverlap(nums, firstLen, secondLen), maxSumNonOverlap(nums[::-1], secondLen, firstLen))

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

Задача: 56. Merge Intervals
Сложность: medium

Дан массив интервалов, где intervals[i] = [starti, endi]. Объедините все перекрывающиеся интервалы и верните массив неперекрывающихся интервалов, которые покрывают все интервалы во входных данных.

Пример:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

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

1️⃣ Представление графа:
Имея представленную интуицию, мы можем изобразить граф в виде списка смежности, вставляя направленные ребра в обоих направлениях, чтобы симулировать неориентированные ребра.

2️⃣Определение компонент связности:
Для определения, в какой компоненте связности находится каждый узел, мы выполняем обходы графа от произвольных непосещенных узлов до тех пор, пока все узлы не будут посещены. Для эффективности мы храним посещенные узлы в множестве (Set), что позволяет проводить проверки на принадлежность и вставку за константное время.

3️⃣Объединение интервалов внутри компонент:
Наконец, мы рассматриваем каждую связную компоненту, объединяя все её интервалы, создавая новый интервал с началом, равным минимальному началу среди всех интервалов в компоненте, и концом, равным максимальному концу.

😎 Решение:

import collections

class Solution:
    def overlap(self, a, b):
        return a[0] <= b[1] and b[0] <= a[1]

    def buildGraph(self, intervals):
        graph = collections.defaultdict(list)
        for i, interval_i in enumerate(intervals):
            for j in range(i + 1, len(intervals)):
                if self.overlap(interval_i, intervals[j]):
                    graph[tuple(interval_i)].append(intervals[j])
                    graph[tuple(intervals[j])].append(interval_i)
        return graph

    def mergeNodes(self, nodes):
        min_start = min(node[0] for node in nodes)
        max_end = max(node[1] for node in nodes)
        return [min_start, max_end]

    def getComponents(self, graph, intervals):
        visited = set()
        comp_number = 0
        nodes_in_comp = collections.defaultdict(list)

        def markComponentDFS(start):
            stack = [start]
            while stack:
                node = tuple(stack.pop())
                if node not in visited:
                    visited.add(node)
                    nodes_in_comp[comp_number].append(node)
                    stack.extend(graph[node])

        for interval in intervals:
            if tuple(interval) not in visited:
                markComponentDFS(interval)
                comp_number += 1

        return nodes_in_comp, comp_number

    def merge(self, intervals):
        graph = self.buildGraph(intervals)
        nodes_in_comp, number_of_comps = self.getComponents(graph, intervals)
        return [self.mergeNodes(nodes_in_comp[comp]) for comp in range(number_of_comps)]

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

Задача: 477. Total Hamming Distance
Сложность: medium

Хэммингово расстояние между двумя целыми числами — это количество позиций, в которых соответствующие биты отличаются.

Дан целочисленный массив nums, верните сумму Хэмминговых расстояний между всеми парами чисел в nums.

Пример:

Input: nums = [4,14,2]
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

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

1⃣Для каждой уникальной пары элементов из массива вычисляем битовое XOR, чтобы найти позиции, где биты различаются. Бит, равный 1 в результате, указывает на различие.

2⃣Для каждой пары элементов используем XOR, чтобы получить битовую разницу, и подсчитываем количество битов, равных 1, чтобы определить Хэммингово расстояние между парой.

3⃣Суммируем все Хэмминговы расстояния для всех пар, чтобы получить общую сумму Хэмминговых расстояний.

😎 Решение:

class Solution:
    def totalHammingDistance(self, nums):
        ans = 0
        
        if not nums:
            return ans
        
        for i in range(len(nums) - 1):
            for j in range(i + 1, len(nums)):
                ans += bin(nums[i] ^ nums[j]).count('1')
        
        return ans

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

Задача: 484. Find Permutation
Сложность: medium

Перестановка perm из n целых чисел всех чисел в диапазоне [1, n] может быть представлена в виде строки s длиной n - 1, где:

s[i] == 'I', если perm[i] < perm[i + 1], и
s[i] == 'D', если perm[i] > perm[i + 1].
Дана строка s, восстановите лексикографически наименьшую перестановку perm и верните её.

Пример:

Input: s = "I"
Output: [1,2]
Explanation: [1,2] is the only legal permutation that can represented by s, where the number 1 and 2 construct an increasing relationship.

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

1⃣Инициализация
Создайте пустой стек stack. Создайте пустой список result для хранения конечной перестановки.

2⃣Для каждого числа i
Если текущий символ в строке s равен 'D', добавьте i в стек. Если текущий символ в строке s равен 'I', добавьте i в стек, затем извлеките все элементы из стека и добавьте их в result.

3⃣Завершение
Добавьте n в стек и извлеките все элементы из стека, добавив их в result. Верните список result, который представляет лексикографически наименьшую перестановку.

😎 Решение:

class Solution:
    def findPermutation(self, s: str) -> List[int]:
        res = [0] * (len(s) + 1)
        stack = []
        j = 0
        for i in range(1, len(s) + 1):
            if s[i - 1] == 'I':
                stack.append(i)
                while stack:
                    res[j] = stack.pop()
                    j += 1
            else:
                stack.append(i)
        stack.append(len(s) + 1)
        while stack:
            res[j] = stack.pop()
            j += 1
        return res

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

Задача: 989. Add to Array-Form of Integer
Сложность: easy

Массивная форма целого числа num - это массив, представляющий его цифры в порядке слева направо.

Например, для num = 1321, массивная форма - это [1, 3, 2, 1].
Дано num в массивной форме целого числа и целое число k, верните массивную форму числа num + k.

Пример:

Input: num = [1,2,0,0], k = 34
Output: [1,2,3,4]
Explanation: 1200 + 34 = 1234

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

1⃣Инициализация переменных:
Преобразуйте число k в массив его цифр и переверните оба массива (массив num и массив цифр k).
Завести переменную carry для хранения переноса и инициализировать ее нулем.
Создать пустой массив result для хранения результата.

2⃣Сложение массивов:
Пройдите по элементам массивов num и цифр k, начиная с их конца, сложите соответствующие цифры вместе с переносом (carry).
Если сумма больше 9, сохраните последнюю цифру в текущей позиции результата, а carry установите в 1.
Если сумма меньше 10, установите carry в 0.
Добавьте результат текущего сложения в массив result

3⃣Обработка оставшихся цифр и переноса:
Если один из массивов закончился раньше, продолжайте сложение оставшихся цифр другого массива с переносом.
Если после окончания всех сложений остается перенос (carry), добавьте его в начало массива result.
Переверните массив result обратно и верните его.

😎 Решение:

def addToArrayForm(num, k):
    num = num[::-1]
    k = list(map(int, str(k)))[::-1]
    
    carry = 0
    result = []
    i = 0
    
    while i < len(num) or i < len(k) or carry:
        n = num[i] if i < len(num) else 0
        m = k[i] if i < len(k) else 0
        total = n + m + carry
        carry = total // 10
        result.append(total % 10)
        i += 1
    
    return result[::-1]

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

Задача: 1011. Capacity To Ship Packages Within D Days
Сложность: medium

На конвейерной ленте находятся пакеты, которые должны быть отправлены из одного порта в другой в течение нескольких дней. i-й пакет на конвейерной ленте имеет массу weights[i]. Каждый день мы загружаем корабль пакетами на конвейерной ленте (в порядке, заданном весами). Мы не можем загрузить больше груза, чем максимальная грузоподъемность корабля. Верните наименьшую грузоподъемность корабля, при которой все посылки на конвейере будут отправлены в течение нескольких дней.

Пример:

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15

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

1⃣Определение диапазона возможных ответов:
Минимальная грузоподъемность должна быть не меньше максимального веса одного пакета (чтобы хотя бы один пакет можно было загрузить).
Максимальная грузоподъемность - это сумма всех весов (если все пакеты будут отправлены за один день).

2⃣Использование бинарного поиска:
Примените бинарный поиск в диапазоне от минимальной до максимальной грузоподъемности, чтобы найти наименьшую грузоподъемность, при которой все пакеты можно отправить за заданное количество дней.

3⃣Проверка возможности отправки всех пакетов за заданное количество дней:
Напишите вспомогательную функцию, которая проверяет, можно ли отправить все пакеты при заданной грузоподъемности за определенное количество дней. Эта функция проходит по списку весов и считает количество необходимых дней для отправки всех пакетов при текущей грузоподъемности.

😎 Решение:

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def canShipInDays(capacity):
            days = 1
            total = 0
            for weight in weights:
                if total + weight > capacity:
                    days += 1
                    total = 0
                total += weight
            return days <= D
        
        left, right = max(weights), sum(weights)
        
        while left < right:
            mid = (left + right) // 2
            if canShipInDays(mid):
                right = mid
            else:
                left = mid + 1
        
        return left

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

Задача: 167. Two Sum II - Input Array Is Sorted
Сложность: medium

Дан массив целых чисел numbers, индексированный с 1, который уже отсортирован в неубывающем порядке. Найдите два числа так, чтобы их сумма составляла заданное целевое число. Пусть эти два числа будут numbers[index1] и numbers[index2], где 1 <= index1 < index2 <= numbers.length.

Верните индексы этих двух чисел, index1 и index2, увеличенные на один, в виде массива из двух элементов [index1, index2].

Тесты генерируются таким образом, что существует ровно одно решение. Нельзя использовать один и тот же элемент дважды.

Ваше решение должно использовать только константное дополнительное пространство.

Пример:

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

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

1️⃣Инициализация указателей:
Используйте два указателя: один (left) начинается с начала массива, а другой (right) - с конца.

2️⃣Поиск решения:
Сравните сумму элементов, на которые указывают left и right, с целевым значением target.
Если сумма равна target, верните индексы этих элементов как решение.
Если сумма меньше target, увеличьте left (так как массив отсортирован и увеличение left увеличивает сумму).
Если сумма больше target, уменьшите right (чтобы уменьшить сумму).

3️⃣Продолжение до нахождения решения:
Перемещайте указатели left и right, повторяя сравнение, пока не будет найдено решение.
Учитывая, что задача гарантирует существование ровно одного решения, этот метод всегда найдет ответ.

😎 Решение:

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

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

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

Задача: 832. Flipping an Image
Сложность: easy

Дано бинарное изображение размером n x n, необходимо перевернуть изображение по горизонтали, затем инвертировать его и вернуть результат.
Перевернуть изображение по горизонтали означает, что каждая строка изображения будет развернута.
Например, переворот строки [1,1,0] по горизонтали дает [0,1,1].
Инвертировать изображение означает, что каждый 0 заменяется на 1, а каждый 1 заменяется на 0.
Например, инверсия строки [0,1,1] дает [1,0,0].

Пример:

Input: image = [[1,1,0],[1,0,1],[0,0,0]]
Output: [[1,0,0],[0,1,0],[1,1,1]]
Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]

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

1⃣Переверните каждую строку по горизонтали, обменяв элементы слева направо и наоборот.

2⃣Инвертируйте каждую строку, заменив каждый 0 на 1 и каждый 1 на 0.

3⃣Верните преобразованное изображение.

😎 Решение:

class Solution:
    def flipAndInvertImage(self, A: List[List[int]]) -> List[List[int]]:
        C = len(A[0])

        for row in A:
            for i in range((C + 1) // 2):
                row[i], row[C - 1 - i] = row[C - 1 - i] ^ 1, row[i] ^ 1

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

Задача: 312. Burst Balloons
Сложность: hard

Дано n воздушных шаров, пронумерованных от 0 до n - 1. Каждый шарик окрашен в число, представленное массивом nums. Вам нужно лопнуть все шарики.

Если вы лопаете шарик i, вы получите nums[i - 1] * nums[i] * nums[i + 1] монет. Если i - 1 или i + 1 выходит за границы массива, то считайте, что там находится шарик с числом 1.

Верните максимальное количество монет, которое можно собрать, лопая шарики с умом.

Пример:

Input: nums = [1,5]
Output: 10

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

1⃣Инициализация и подготовка данных
Добавьте по одному шару с числом 1 в начало и конец массива nums, чтобы упростить обработку граничных случаев. Определите функцию dp(left, right), которая будет возвращать максимальное количество монет, если лопнуть все шары на интервале [left, right] включительно.

2⃣Вычисление значений для всех интервалов
Для каждого интервала [left, right] и каждого индекса i в этом интервале: Вычислите максимальные монеты, которые можно получить, сначала лопая все шары кроме i, а затем лопая i. Обновите dp(left, right) максимальной суммой этих монет.

3⃣Возврат результата
Верните значение dp(1, n - 2), которое будет содержать максимальное количество монет, которое можно собрать, лопнув все шары с умом, исключая добавленные нами шары.

😎 Решение:

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        nums = [1] + nums + [1]
        n = len(nums)
        
        @lru_cache(None)
        def dp(left: int, right: int) -> int:
            if left > right:
                return 0
            max_coins = 0
            for i in range(left, right + 1):
                coins = dp(left, i - 1) + dp(i + 1, right) + nums[left - 1] * nums[i] * nums[right + 1]
                max_coins = max(max_coins, coins)
            return max_coins
        
        return dp(1, n - 2)

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