Задача: 205. Isomorphic Strings
Сложность: easy

Даны две строки s и t, определите, являются ли они изоморфными.

Две строки s и t являются изоморфными, если символы в s могут быть заменены для получения t.

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

Пример:

Input: s = "egg", t = "add"
Output: true

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

1️⃣Определите два словаря: mapping_s_t для отображения символов из строки s в символы строки t, и mapping_t_s для отображения символов из строки t в символы строки s.

2️⃣Итеративно пройдитесь по символам строк s и t. Для каждого символа c1 из s и соответствующего c2 из t, если c1 нет в mapping_s_t и c2 нет в mapping_t_s, добавьте соответствующие отображения; если одно из отображений существует, проверьте, соответствует ли оно ожидаемому значению.

3️⃣Если в процессе проверки какое-либо отображение неверно, верните false. Если все проверки пройдены успешно, верните true после окончания итерации по строкам.

😎 Решение:

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:

        mapping_s_t = {}
        mapping_t_s = {}

        for c1, c2 in zip(s, t):
            if (c1 not in mapping_s_t) and (c2 not in mapping_t_s):
                mapping_s_t[c1] = c2
                mapping_t_s[c2] = c1
            elif mapping_s_t.get(c1) != c2 or mapping_t_s.get(c2) != c1:
                return False

        return True

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

Задача: 201. Bitwise AND of Numbers Range
Сложность: medium

Даны два целых числа left и right, которые представляют диапазон [left, right], верните побитовое И всех чисел в этом диапазоне включительно.

Пример:

Input: left = 5, right = 7
Output: 4

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

1️⃣Сдвигать left и right вправо, пока они не станут равными.

2️⃣Подсчитать количество сдвигов.

3️⃣Сдвинуть left влево на количество сдвигов и вернуть результат.

😎 Решение:

class Solution:
    def rangeBitwiseAnd(self, m: int, n: int) -> int:
        shift = 0
        while m < n:
            m = m >> 1
            n = n >> 1
            shift += 1
        return m << shift

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

Задача: 1041. Robot Bounded In Circle
Сложность: medium

На бесконечной плоскости робот изначально стоит в точке (0, 0) и обращен лицом на север. Обратите внимание, что: северное направление - это положительное направление оси y. южное направление - это отрицательное направление оси y. восточное направление - это положительное направление оси x. западное направление - это отрицательное направление оси x. робот может получить одну из трех команд: "G": идти прямо 1 единицу. "L": повернуть на 90 градусов влево (т.е, "R": повернуть на 90 градусов вправо (т. е. по часовой стрелке). Робот выполняет данные инструкции по порядку и повторяет их до бесконечности. Возвращается true тогда и только тогда, когда в плоскости существует окружность, такая, что робот никогда не покидает ее.

Пример:

Input: instructions = "GGLLGG"
Output: true

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

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

2⃣Изменение направления:
Робот может двигаться на север (0), восток (1), юг (2), или запад (3). Эти направления можно моделировать с помощью векторов (dx, dy): север (0, 1), восток (1, 0), юг (0, -1), запад (-1, 0).

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

😎 Решение:

def isRobotBounded(instructions):
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    x = y = 0
    direction = 0
    
    for instruction in instructions:
        if instruction == 'G':
            x += directions[direction][0]
            y += directions[direction][1]
        elif instruction == 'L':
            direction = (direction + 3) % 4
        elif instruction == 'R':
            direction = (direction + 1) % 4
    
    return (x == 0 and y == 0) or direction != 0

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

Задача: 309. Best Time to Buy and Sell Stock with Cooldown
Сложность: medium

Дан массив prices, где prices[i] — цена данной акции в i-й день.

Найдите максимальную прибыль, которую можно получить. Вы можете совершить любое количество транзакций (т. е. купить и продать одну акцию несколько раз) с следующими ограничениями:

После продажи акции вы не можете покупать акции на следующий день (т. е. необходимо один день подождать).

Пример:

Input: prices = [1]
Output: 0

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

1⃣Инициализация состояний
Используйте три состояния для отслеживания максимальной прибыли: hold: максимальная прибыль на данный день, если у вас есть акция. sold: максимальная прибыль на данный день, если вы продали акцию. cooldown: максимальная прибыль на данный день, если вы находитесь в периоде ожидания после продажи.

2⃣Обновление состояний
Итерируйте по каждому дню, обновляя состояния: hold: максимальная прибыль, если у вас есть акция на текущий день. sold: максимальная прибыль, если вы продаете акцию на текущий день. cooldown: максимальная прибыль, если вы находитесь в периоде ожидания на текущий день.

3⃣Определение максимальной прибыли
В конце итерации максимальная прибыль будет максимальным значением между состояниями sold и cooldown, так как hold состояние не может быть конечным состоянием для получения максимальной прибыли.

😎 Решение:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        
        n = len(prices)
        hold = -prices[0]
        sold = 0
        cooldown = 0
        
        for i in range(1, n):
            new_hold = max(hold, cooldown - prices[i])
            new_sold = hold + prices[i]
            new_cooldown = max(cooldown, sold)
            
            hold = new_hold
            sold = new_sold
            cooldown = new_cooldown
        
        return max(sold, cooldown)

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

Задача: 599. Minimum Index Sum of Two Lists
Сложность: easy

Даны два массива строк list1 и list2, необходимо найти общие строки с наименьшей суммой индексов.

Общая строка - это строка, которая появляется и в list1, и в list2.

Общая строка с наименьшей суммой индексов - это общая строка, такая, что если она появилась в list1[i] и list2[j], то i + j должно быть минимальным значением среди всех других общих строк.

Верните все общие строки с наименьшей суммой индексов. Верните ответ в любом порядке.

Пример:

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]
Output: ["Shogun"]
Explanation: The only common string is "Shogun".

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

1⃣Для каждой строки из list1, сравниваем её с каждой строкой из list2, обходя весь список list2. Используем хэш-таблицу map, которая содержит элементы в виде (сумма: список строк). Здесь сумма относится к сумме индексов совпадающих элементов, а список строк соответствует списку совпадающих строк, чья сумма индексов равна этой сумме.

2⃣Во время сравнений, когда находится совпадение строки на i-м индексе из list1 и j-м индексе из list2, создаём запись в map, соответствующую сумме i + j, если такая запись ещё не существует. Если запись с этой суммой уже существует, добавляем текущую строку в список строк, соответствующих сумме i + j.

3⃣В конце обходим ключи в map и находим список строк, соответствующих ключу с минимальной суммой.

😎 Решение:

class Solution:
    def findRestaurant(self, list1, list2):
        map = {}
        for i in range(len(list1)):
            for j in range(len(list2)):
                if list1[i] == list2[j]:
                    if i + j not in map:
                        map[i + j] = []
                    map[i + j].append(list1[i])
        min_index_sum = min(map.keys())
        return map[min_index_sum]

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

Задача: 33. Search in Rotated Sorted Array
Сложность: medium

Есть массив целых чисел nums, отсортированный в порядке возрастания (с уникальными значениями).

Перед передачей в вашу функцию массив nums может быть повёрнут в неизвестном индексе поворота k (1 <= k < nums.length), так что результирующий массив будет иметь вид [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (с индексацией с нуля). Например, [0,1,2,4,5,6,7] может быть повёрнут в индексе поворота 3 и стать [4,5,6,7,0,1,2].

Для данного массива nums после возможного поворота и целого числа target, верните индекс target, если он есть в массиве, или -1, если его нет в массиве.

Вы должны написать алгоритм с временной сложностью O(log n).

Пример:

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

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

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

2️⃣По завершении двоичного поиска мы имеем индекс поворота, обозначенный как pivot = left.
nums состоит из двух отсортированных подмассивов, nums[0 ~ left - 1] и nums[left ~ n - 1].

3️⃣Выполните двоичный поиск по подмассиву nums[0 ~ left - 1] для поиска target. Если target находится в этом подмассиве, верните его индекс.
В противном случае выполните двоичный поиск по подмассиву nums[left ~ n - 1] для поиска target. Если target находится в этом подмассиве, верните его индекс. В противном случае верните -1.

😎 Решение:

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

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

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

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

        return binarySearch(lef

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

Задача: 1057. Campus Bikes
Сложность: medium

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

Пример:

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

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

1⃣Для каждой пары (работник, велосипед) вычисли Манхэттенское расстояние и сохрани все пары вместе с расстоянием в список.

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

3⃣Заполни и верни массив назначений.

😎 Решение:

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

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

Задача: 299. Bulls and Cows
Сложность: medium

Вы играете в игру "Быки и коровы" со своим другом.

Вы записываете секретное число и просите своего друга угадать, что это за число. Когда ваш друг делает предположение, вы даете ему подсказку со следующей информацией:

Количество "быков", то есть цифры в предположении, которые находятся на правильной позиции.
Количество "коров", то есть цифры в предположении, которые есть в вашем секретном числе, но находятся на неправильной позиции. Конкретно, это не-бычьи цифры в предположении, которые можно переставить так, чтобы они стали быками.
Дано секретное число secret и предположение вашего друга guess, верните подсказку для предположения вашего друга.

Подсказка должна быть в формате "xAyB", где x — количество быков, а y — количество коров. Обратите внимание, что и secret, и guess могут содержать повторяющиеся цифры.

Пример:

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

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

1⃣Инициализация счетчиков:
Инициализируйте количество быков и коров значениями ноль. Создайте хеш-таблицу для хранения символов строки secret и их частот.

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

3⃣Возврат результата:
Верните количество быков и коров в формате "xAyB".

😎 Решение:

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

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

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

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

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

Задача: 1302. Deepest Leaves Sum
Сложность: medium

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

Пример:

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

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

1⃣Поместите корень в стек.

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

3⃣Верните deepest_sum.

😎 Решение:

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

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

Задача: 239. Sliding Window Maximum
Сложность: hard

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

Верните максимальные значения скользящего окна.

Пример:

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

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

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

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

3⃣Возвращение результата:
Верните список res, содержащий максимальные элементы для каждого скользящего окна.

😎 Решение:

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

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

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

        return res

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

Задача: 958. Check Completeness of a Binary Tree
Сложность: medium

Дан корень бинарного дерева, определите, является ли оно полным бинарным деревом.

В полном бинарном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно левее. На последнем уровне h может быть от 1 до 2^h узлов включительно.

Пример:

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

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

1⃣Если корень дерева равен null, верните true.

2⃣Инициализируйте переменную nullNodeFound как false для отслеживания того, встречался ли уже null-узел. Создайте очередь и поместите в неё корень дерева.

3⃣Пока очередь не пуста:
Извлеките первый элемент из очереди.
Если элемент равен null, установите nullNodeFound в true.
Если элемент не равен null, проверьте, встречался ли уже null-узел. Если nullNodeFound равен true, верните false. В противном случае добавьте в очередь левого и правого потомков текущего узла.

😎 Решение:

from collections import deque

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

        queue = deque([root])
        nullNodeFound = False

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

        return True

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

Задача: 869. Reordered Power of 2
Сложность: medium

Дано целое число n. Мы можем переставить цифры числа в любом порядке (включая исходный порядок), при этом ведущая цифра не должна быть нулем.

Верните true, если и только если мы можем сделать это так, чтобы полученное число было степенью двойки.

Пример:

Input: n = 1
Output: true

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

1⃣Сгенерируйте все перестановки цифр числа, размещая любую цифру на первой позиции (start = 0), затем любую из оставшихся цифр на второй позиции (start = 1) и так далее. В Python можно использовать встроенную функцию itertools.permutations.

2⃣Проверьте, что перестановка представляет собой степень двойки, убедившись, что в перестановке нет ведущего нуля, и удаляя все множители 2. Если результат равен 1 (то есть, он не содержал других множителей, кроме 2), то это была степень двойки. В Python можно использовать проверку bin(N).count('1') == 1.

3⃣Верните true, если хотя бы одна перестановка является степенью двойки, иначе верните false.

😎 Решение:

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

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

Задача: 1039. Minimum Score Triangulation of Polygon
Сложность: medium

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

Пример:

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

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

1⃣Инициализация:
Создаем двумерный массив dp, где dp[i][j] будет хранить минимальный возможный общий балл триангуляции многоугольника, состоящего из вершин от i до j.

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

3⃣Возврат результата:
Ответ будет в dp[0][n-1], который хранит минимальный возможный общий балл триангуляции для всего многоугольника.

😎 Решение:

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

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

Задача: 1037. Valid Boomerang
Сложность: easy

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

Пример:

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

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

1⃣Проверка уникальности точек:
Убедитесь, что все три точки уникальны. Если любые две точки совпадают, то это не бумеранг.

2⃣Проверка на коллинеарность:
Используйте определитель (или площадь параллелограмма) для проверки, находятся ли три точки на одной прямой. Если площадь параллелограмма, образованного тремя точками, равна нулю, то точки коллинеарны.

3⃣Результат:
Если точки уникальны и не коллинеарны, верните true. В противном случае, верните false.

😎 Решение:

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

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

Задача: 302. Smallest Rectangle Enclosing Black Pixels
Сложность: hard

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

Пример:

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

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

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

2⃣Обход всех пикселей: Пройдите по всем координатам (x, y) матрицы. Если текущий пиксель является черным (image[x][y] == 1), обновите границы прямоугольника:
left = min(left, x)
right = max(right, x + 1)
top = min(top, y)
bottom = max(bottom, y + 1)

3⃣Вычисление и возврат площади: После завершения обхода матрицы, верните площадь прямоугольника, используя формулу (right - left) * (bottom - top).

😎 Решение:

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

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

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

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

Задача: 1514. Path with Maximum Probability
Сложность: medium

Вам дан неориентированный взвешенный граф из n узлов (индексация с нуля), представленный списком ребер, где edges[i] = [a, b] является неориентированным ребром, соединяющим узлы a и b с вероятностью успешного прохождения этого ребра succProb[i].

Даны два узла start и end, найдите путь с максимальной вероятностью успеха, чтобы перейти от start к end, и верните его вероятность успеха.

Если пути от start до end не существует, верните 0. Ваш ответ будет принят, если он отличается от правильного ответа не более чем на 1e-5.

Пример:

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

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

1⃣Инициализируйте массив maxProb как максимальную вероятность достижения каждого узла из начального узла, установите maxProb[start] равным 1.

2⃣Расслабьте все ребра: для каждого ребра (u, v), если найдена более высокая вероятность достижения u через это ребро, обновите max_prob[u] как max_prob[u] = max_prob[v] * path_prob. Если найдена более высокая вероятность достижения v через это ребро, обновите max_prob[v].

3⃣Если нам не удается обновить какой-либо узел с более высокой вероятностью, мы можем остановить итерацию, перейдя к шагу 4. В противном случае повторяйте шаг 2, пока все ребра не будут расслаблены n - 1 раз.
Верните max_prob[end].

😎 Решение:

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

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

        return maxProb[end]

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

Задача: 203. Remove Linked List Elements
Сложность: easy

Для заданного начала связного списка и целого числа val удалите все узлы связного списка, у которых Node.val равно val, и верните новое начало списка.

Пример:

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

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

1️⃣Инициализируйте сторожевой узел как ListNode(0) и установите его новым началом: sentinel.next = head. Инициализируйте два указателя для отслеживания текущего узла и его предшественника: curr и prev.

2️⃣Пока curr не является нулевым указателем, сравните значение текущего узла со значением для удаления. Если значения равны, удалите текущий узел: prev.next = curr.next, иначе установите предшественника равным текущему узлу. Переместитесь к следующему узлу: curr = curr.next.

3️⃣Верните sentinel.next.

😎 Решение:

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        sentinel = ListNode(0)
        sentinel.next = head
        
        prev, curr = sentinel, head
        while curr:
            if curr.val == val:
                prev.next = curr.next
            else:
                prev = curr
            curr = curr.next
        
        return sentinel.next

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

Задача: 895. Maximum Frequency Stack
Сложность: hard

Разработайте структуру данных, похожую на стек, чтобы заталкивать элементы в стек и вытаскивать из него самый частый элемент. Реализуйте класс FreqStack: FreqStack() строит пустой стек частот. void push(int val) заталкивает целое число val на вершину стека. int pop() удаляет и возвращает самый частый элемент в стеке. Если есть равенство в выборе самого частого элемента, то удаляется и возвращается элемент, который ближе всего к вершине стека.

Пример:

Input
["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"]
[[], [5], [7], [5], [7], [4], [5], [], [], [], []]
Output
[null, null, null, null, null, null, null, 5, 7, 5, 4]

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

1⃣Создать два словаря: freq для хранения частоты каждого элемента и group для хранения стека элементов для каждой частоты.

2⃣При добавлении элемента увеличивать его частоту в freq и добавлять его в стек соответствующей частоты в group.

3⃣При извлечении элемента найти максимальную частоту, удалить элемент из стека соответствующей частоты и уменьшить его частоту в freq. Если стек для данной частоты становится пустым, удалить его.

😎 Решение:

class FreqStack:
    def __init__(self):
        self.freq = {}
        self.group = {}
        self.maxfreq = 0

    def push(self, val: int) -> None:
        f = self.freq.get(val, 0) + 1
        self.freq[val] = f
        if f > self.maxfreq:
            self.maxfreq = f
            self.group[f] = []
        self.group[f].append(val)

    def pop(self) -> int:
        val = self.group[self.maxfreq].pop()
        self.freq[val] -= 1
        if not self.group[self.maxfreq]:
            self.maxfreq -= 1

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

Задача: 1370. Increasing Decreasing String
Сложность: easy

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

Выберите наименьший символ из s и добавьте его к результату.
Выберите наименьший символ из s, который больше последнего добавленного символа, и добавьте его.
Повторяйте шаг 2, пока не сможете выбрать больше символов.
Выберите наибольший символ из s и добавьте его к результату.
Выберите наибольший символ из s, который меньше последнего добавленного символа, и добавьте его.
Повторяйте шаг 5, пока не сможете выбрать больше символов.
Повторяйте шаги с 1 по 6, пока не выберете все символы из s.
На каждом этапе, если наименьший или наибольший символ появляется более одного раза, вы можете выбрать любое его вхождение и добавить его к результату.

Верните результирующую строку после сортировки s с помощью этого алгоритма.

Пример:

Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

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

1⃣Инициализация и сортировка:
Создайте словарь для подсчета количества каждого символа в строке s. Создайте результирующую строку result.

2⃣Перебор и добавление символов:
Используйте два цикла: первый для добавления символов в возрастающем порядке, второй — в убывающем. В каждом цикле добавляйте символы к результату, обновляя их количество в словаре.

3⃣Проверка завершения:
Повторяйте шаги 2 и 3, пока не будут добавлены все символы из строки s в result.

😎 Решение:

class Solution:
    def sortString(self, s: str) -> str:
        from collections import Counter
        char_count = Counter(s)
        result = []
        
        while len(result) < len(s):
            for char in "abcdefghijklmnopqrstuvwxyz":
                if char_count[char] > 0:
                    result.append(char)
                    char_count[char] -= 1
            for char in "zyxwvutsrqponmlkjihgfedcba":
                if char_count[char] > 0:
                    result.append(char)
                    char_count[char] -= 1
        
        return ''.join(result)

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

Задача: 753. Cracking the Safe
Сложность: medium

Имеется сейф, защищенный паролем. Пароль представляет собой последовательность из n цифр, каждая из которых может находиться в диапазоне [0, k - 1]. Сейф имеет особый способ проверки пароля. Например, правильный пароль - "345", а вы вводите "012345": после ввода 0 последние 3 цифры - "0", что неверно. После ввода 1 последние 3 цифры - "01", что неверно. После ввода 2 последние 3 цифры - "012", что неверно.
После ввода 3 последние 3 цифры - "123", что неверно. После ввода 4 последние 3 цифры - "234", что неверно. После ввода 5 последние 3 цифры - "345", что верно, и сейф разблокируется. Верните любую строку минимальной длины, которая разблокирует сейф на определенном этапе ввода.

Пример:

Input: n = 1, k = 2
Output: "10"

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

1⃣Создайте граф, где каждая вершина представляет собой строку длины n-1, а каждое ребро между двумя вершинами представляет собой добавление одной из цифр из диапазона [0, k-1].

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

3⃣Составьте итоговую строку, которая включает начальную вершину и все добавленные цифры.

😎 Решение:

def crackSafe(n, k):
    seen = set()
    result = []

    def dfs(node):
        for x in range(k):
            neighbor = node + str(x)
            if neighbor not in seen:
                seen.add(neighbor)
                dfs(neighbor[1:])
                result.append(str(x))

    start_node = '0' * (n - 1)
    dfs(start_node)
    return start_node + ''.join(result)

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