Python | LeetCode

Задача: 568. Maximum Vacation Days
Сложность: hard

LeetCode хочет предоставить одному из своих лучших сотрудников возможность путешествовать по n городам для сбора задач по алгоритмам. Однако, как говорится, "делу время, потехе час". Вы можете брать отпуска в некоторых конкретных городах и неделях. Ваша задача — спланировать поездку, чтобы максимально увеличить количество дней отпуска, которые вы сможете взять, соблюдая при этом определенные правила и ограничения.

Правила и ограничения:
Вы можете путешествовать только между n городами, обозначенными индексами от 0 до n-1. Изначально вы находитесь в городе с индексом 0 в понедельник.
Города связаны рейсами. Рейсы представлены матрицей n x n, называемой flights, представляющей статус авиалинии от города i до города j. Если рейса из города i в город j нет, flights[i][j] == 0; иначе flights[i][j] == 1. Также для всех i выполняется flights[i][i] == 0.
У вас есть k недель (каждая неделя состоит из семи дней) для путешествий. Вы можете летать не более одного раза в день и можете летать только утром каждого понедельника. Время полета настолько короткое, что его влияние не учитывается.
Для каждого города у вас есть ограниченные дни отпуска в разные недели, заданные матрицей n x k, называемой days. Значение days[i][j] представляет максимальное количество дней отпуска, которые вы можете взять в городе i на неделе j.
Вы можете оставаться в городе большее количество дней, чем количество дней отпуска, но вы должны работать в дополнительные дни, которые не будут учитываться как дни отпуска.
Даны две матрицы flights и days, верните максимальное количество дней отпуска, которые вы можете взять в течение k недель.

Пример:

Input: flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]]
Output: 12
Explanation:
One of the best strategies is:
1st week : fly from city 0 to city 1 on Monday, and play 6 days and work 1 day.
(Although you start at city 0, we could also fly to and start at other cities since it is Monday.)
2nd week : fly from city 1 to city 2 on Monday, and play 3 days and work 4 days.
3rd week : stay at city 2, and play 3 days and work 4 days.
Ans = 6 + 3 + 3 = 12.

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

1⃣Использовать функцию dfs (поиск в глубину), которая возвращает количество отпускных дней, которые можно взять, начиная с текущего города cur_city и текущей недели weekno. В каждом вызове функции проходить по всем городам и находить все города, которые связаны с текущим городом. Такой город обозначен 1 в соответствующей позиции flights[cur_city][i].

2⃣Для текущего города можно либо остаться в нем, либо поехать в связанный город. Обозначим город, в который меняется расположение, как j. После смены города нужно найти количество отпускных дней, которые можно взять, начиная с нового города и с новой недели. Это количество отпускных дней можно представить как: days[j][weekno] + dfs(flights, days, j, weekno + 1).

3⃣Для текущего города необходимо найти максимальное количество отпускных дней, выбирая различные города в качестве следующего местоположения. Из всех вариантов отпускных дней выбираем максимальное значение, которое и будет возвращено для каждого вызова функции dfs.

😎 Решение:

class Solution:
    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:
        n, k = len(flights), len(days[0])
        memo = [[-1] * k for _ in range(n)]

        def dfs(cur_city, weekno):
            if weekno == k:
                return 0
            if memo[cur_city][weekno] != -1:
                return memo[cur_city][weekno]
            max_vac = 0
            for next_city in range(n):
                if cur_city == next_city or flights[cur_city][next_city] == 1:
                    max_vac = max(max_vac, days[next_city][weekno] + dfs(next_city, weekno + 1))
            memo[cur_city][weekno] = max_vac
            return max_vac

        return dfs(0, 0)

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

Задача: 638. Shopping Offers
Сложность: medium

В магазине LeetCode Store есть n предметов для продажи. Каждый товар имеет свою цену. Однако существуют специальные предложения, и специальное предложение состоит из одного или нескольких различных видов товаров с распродажной ценой. Вам дан целочисленный массив price, где price[i] - цена i-го товара, и целочисленный массив needs, где needs[i] - количество штук i-го товара, который вы хотите купить. Вам также дан массив special, где special[i] имеет размер n + 1, где special[i][j] - количество штук j-го товара в i-м предложении, а special[i][n] (т.е., Возвращает наименьшую цену, которую вы можете заплатить за определенный товар из заданных, где вы могли бы оптимально использовать специальные предложения. Вам не разрешается покупать больше товаров, чем вы хотите, даже если это снизит общую цену. Вы можете использовать любое из специальных предложений столько раз, сколько захотите.

Пример:

Input: price = [2,5], special = [[3,0,5],[1,2,10]], needs = [3,2]
Output: 14

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

1⃣Рекурсивное вычисление стоимости: Определите функцию, которая рекурсивно вычисляет минимальную стоимость для оставшихся нужд, используя динамическое программирование для запоминания уже вычисленных значений.

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

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

😎 Решение:

def shoppingOffers(price, special, needs):
    memo = {}
    
    def dfs(cur_needs):
        val = sum(cur_needs[i] * price[i] for i in range(len(needs)))
        for sp in special:
            new_needs = []
            for i in range(len(needs)):
                if sp[i] > cur_needs[i]:
                    break
                new_needs.append(cur_needs[i] - sp[i])
            if len(new_needs) == len(needs):
                val = min(val, memo.get(tuple(new_needs), dfs(new_needs)) + sp[-1])
        memo[tuple(cur_needs)] = val
        return val

    return dfs(needs)

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

⚡ Официальный релиз easyoffer 2.0 состоится уже в течение нескольких дней.

Напоминаю, что в честь релиза запускаем акцию.

Первые 500 покупателей получат:

🚀 Скидку 50% на PRO тариф на 1 год
🎁 Подарок ценностью 5000₽ для тех, кто подписан на этот канал

🔔 Подпишитесь на этот канал: https://t.me/+b2fZN17A9OQ3ZmJi
В нем мы опубликуем сообщение о релизе в первую очередь

Задача: 583. Delete Operation for Two Strings
Сложность: medium

Даны две строки word1 и word2, вернуть минимальное количество шагов, необходимых для того, чтобы сделать word1 и word2 одинаковыми.

На одном шаге можно удалить ровно один символ в любой строке.

Пример:

Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

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

1⃣ Инициализация массива:
Создайте одномерный массив dp для хранения минимального количества удалений, необходимых для уравнивания строк word1 и word2.

2⃣ Заполнение массива:
Используйте временный массив temp для обновления значений dp, представляющих текущую строку. Обновите temp с использованием значений dp предыдущей строки.

3⃣ Обновление и результат:
Скопируйте временный массив temp обратно в dp после обработки каждой строки. В конце верните значение из dp, представляющее минимальное количество удалений.

😎 Решение:

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [0] * (n + 1)

        for i in range(m + 1):
            temp = [0] * (n + 1)
            for j in range(n + 1):
                if i == 0 or j == 0:
                    temp[j] = i + j
                elif word1[i - 1] == word2[j - 1]:
                    temp[j] = dp[j - 1]
                else:
                    temp[j] = 1 + min(dp[j], temp[j - 1])
            dp = temp

        return dp[n]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

from collections import deque

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

        queue = deque([root])
        nullNodeFound = False

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

        return True

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

        return res

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

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

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

Пример:

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

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

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

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

3⃣Верните deepest_sum.

😎 Решение:

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

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

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

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

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