Python | LeetCode

Задача: 1663. Smallest String With A Given Numeric Value Сложность: medium Числовое значение строчной буквы определяется ее позицией (начиная с 1) в алфавите, поэтому числовое значение a равно 1, числовое значение b равно 2, числовое значение c равно 3 и так далее. Числовое значение строки, состоящей из строчных букв, определяется как сумма числовых значений ее символов. Например, числовое значение строки "abe" равно 1 + 2 + 5 = 8. Вам даны два целых числа n и k. Верните лексикографически наименьшую строку длиной n с числовым значением, равным k. Обратите внимание, что строка x лексикографически меньше строки y, если x идет перед y в словарном порядке, то есть либо x является префиксом y, либо, если i - первая позиция, где x[i] != y[i], то x[i] идет перед y[i] в алфавитном порядке. Пример:

Input: n = 3, k = 27
Output: "aay"
Explanation: The numeric value of the string is 1 + 1 + 25 = 27, and it is the smallest string with such a value and length equal to 3.

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

class Solution:
    def getSmallestString(self, n: int, k: int) -> str:
        result = ['a'] * n
        
        for position in range(n):
            positionsLeft = (n - position - 1)
            if k > positionsLeft * 26:
                add = k - (positionsLeft * 26)
                result[position] = chr(ord('a') + add - 1)
                k -= add
            else:
                k -= 1
        
        return ''.join(result

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

Где чатиться с аутсорсерами и подрядчиками? Пригласите подрядчиков и клиентов в ваш рабочий мессенджер Битрикс24. Они увидят только свои чаты, задачи и звонки, а внутренние данные компании остаются закрытыми. Всё нужное для работы: • Общий чат проекта со всеми участниками • Доступ к задачам, файлам и календарю проекта • Гибкие права доступа и безопасность данных Общайтесь, созванивайтесь и согласовывайте прямо в Битрикс24, можно в мобильном приложении. Зарегистрироваться #реклама 16+ bitrix24.ru О рекламодателе

Задача: 258. Add Digits Сложность: easy Дано целое число num. Повторно складывайте все его цифры, пока результат не станет однозначным, и верните его. Пример:

Input: num = 38
Output: 2
Explanation: The process is
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2 
Since 2 has only one digit, return it.

👨‍💻 Алгоритм: 1️⃣Инициализируйте переменную digital_root значением 0. 2️⃣В цикле, пока num больше 0: Добавьте к digital_root последнюю цифру num. Уменьшите num, удалив последнюю цифру. Если num равно 0 и digital_root больше 9, присвойте num значение digital_root и сбросьте digital_root в 0. 3️⃣Верните значение digital_root. 😎 Решение:

class Solution:
    def addDigits(self, num: int) -> int:
        digital_root = 0
        while num > 0:
            digital_root += num % 10
            num //= 10
            if num == 0 and digital_root > 9:
                num = digital_root
                digital_root = 0
        return digital_root

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

Задача: 979. Distribute Coins in Binary Tree Сложность: medium Вам дан корень бинарного дерева с n узлами, где каждый узел в дереве содержит node.val монет. Всего по всему дереву распределено n монет. За один ход мы можем выбрать два смежных узла и переместить одну монету из одного узла в другой. Ход может быть как от родителя к ребенку, так и от ребенка к родителю. Верните минимальное количество ходов, необходимых для того, чтобы каждый узел имел ровно одну монету. Пример:

Input: root = [3,0,0]
Output: 2
Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.

👨‍💻 Алгоритм: 1⃣Инициализация и определение рекурсивной функции. Инициализируйте переменную moves = 0. Определите рекурсивную функцию dfs, которая считает количество перемещений монет. Базовый случай: если текущий узел равен null, верните 0. 2⃣Рекурсивный обход дерева. Внутри dfs вызовите dfs для левого и правого поддеревьев, чтобы получить количество монет, которые нужно переместить в каждом поддереве. Вычислите количество перемещений для текущего узла: добавьте абсолютные значения перемещаемых монет в moves. 3⃣Возвращение результата. Верните количество монет, которые текущий узел может передать своему родителю: значение узла плюс количество монет в левом и правом поддеревьях минус 1. Вызовите dfs от корня дерева и верните moves. 😎 Решение:

class Solution:
    def distributeCoins(self, root: Optional[TreeNode]) -> int:
        self.moves = 0
        self.dfs(root)
        return self.moves

    def dfs(self, current: Optional[TreeNode]) -> int:
        if not current:
            return 0
        leftCoins = self.dfs(current.left)
        rightCoins = self.dfs(current.right)
        self.moves += abs(leftCoins) + abs(rightCoins)
        return current.val - 1 + leftCoins + rightCoins

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

Ищу желающих заполнять карточки товаров на ВБ! Работа полностью на удаленке с зп до 150 000 рублей в месяц. Без опыта, нужен только телефон, занятость 3-6 часов в день. Всему обучат на бесплатном курсе и после возьму на работу: ✅ 3 дня уроков по 30 минут ✅ Домашки с проверкой и оплатой бонусами ✅ Плачу 10 тыс за каждую выполненную домашку Все кто пройдет курс, получат сертификат от школы с образовательной лицензией. ⚡ Набор заканчивается завтра. 👍 Для регистрации жмите кнопку "Зарегистрироваться" Зарегистрироваться #реклама 16+ course.wildmanager.ru О рекламодателе

Задача: 397. Integer Replacement Сложность: medium К положительному целому числу n можно применить одну из следующих операций: если n четное, замените n на n / 2. если n нечетное, замените n на n + 1 или n - 1. верните минимальное количество операций, необходимых для того, чтобы n стало 1. Пример:

Input: n = 8
Output: 3
Explanation: 8 -> 4 -> 2 -> 1

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

class Solution:
    def integerReplacement(self, n: int) -> int:
        def helper(n, memo):
            if n == 1:
                return 0
            if n in memo:
                return memo[n]
            
            if n % 2 == 0:
                memo[n] = 1 + helper(n // 2, memo)
            else:
                memo[n] = 1 + min(helper(n + 1, memo), helper(n - 1, memo))
                
            return memo[n]
        
        return helper(n, {})

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

Задача: 1051. Height Checker Сложность: easy Школа пытается сделать ежегодную фотографию всех учеников. Учеников просят встать в одну шеренгу в неубывающем порядке по росту. Пусть этот порядок представлен целочисленным массивом expected, где expected[i] - ожидаемый рост i-го студента в очереди. Вам дан целочисленный массив heights, представляющий текущий порядок, в котором стоят студенты. Каждый heights[i] - это высота i-го студента в очереди (с индексом 0). Верните количество индексов, в которых heights[i] != expected[i]. Пример:

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

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

def heightChecker(heights):
    expected = sorted(heights)
    count = 0
    for i in range(len(heights)):
        if heights[i] != expected[i]:
            count += 1
    return count

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

Задача: 567. Permutation in String Сложность: medium Даны две строки s1 и s2. Верните true, если s2 содержит перестановку s1, или false в противном случае. Другими словами, верните true, если одна из перестановок s1 является подстрокой s2. Пример:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

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

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        from collections import Counter
        
        s1Count = Counter(s1)
        s2Count = Counter(s2[:len(s1)])
        
        if s1Count == s2Count:
            return True
        
        for i in range(len(s1), len(s2)):
            s2Count[s2[i]] += 1
            s2Count[s2[i - len(s1)]] -= 1
            if s2Count[s2[i - len(s1)]] == 0:
                del s2Count[s2[i - len(s1)]]
            if s1Count == s2Count:
                return True
        
        return False

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

Задача: 200. Number of Islands Сложность: medium Дана двумерная бинарная сетка размером m x n, представляющая карту из '1' (земля) и '0' (вода). Верните количество островов. Остров окружён водой и образуется путём соединения соседних земель горизонтально или вертикально. Можно предположить, что все четыре края сетки окружены водой. Пример:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

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

class Solution:
    def numIslands(self, grid):
        if not grid:
            return 0

        num_islands = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == "1":
                    self.dfs(grid, i, j)
                    num_islands += 1

        return num_islands

    def dfs(self, grid, r, c):
        if (
            r < 0
            or c < 0
            or r >= len(grid)
            or c >= len(grid[0])
            or grid[r][c] != "1"
        ):
            return
        grid[r][c] = "0"

        self.dfs(grid, r - 1, c)
        self.dfs(grid, r + 1, c)
        self.dfs(grid, r, c - 1)
        self.dfs(grid, r, c + 1)

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

Задача: 1498. Number of Subsequences That Satisfy the Given Sum Condition Сложность: medium Вам дан массив целых чисел nums и целое число target. Верните количество непустых подпоследовательностей массива nums, таких что сумма минимального и максимального элемента в них меньше или равна target. Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7. Пример:

Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

👨‍💻 Алгоритм: 1⃣Инициализация и подготовка: Инициализируйте переменные answer равным 0 и n как длину массива nums. Отсортируйте массив nums. Подготовьте массив power для хранения степеней двойки до n по модулю 10^9+7. 2⃣Итерация и бинарный поиск: Для каждого индекса left от 0 до n - 1 выполните бинарный поиск, чтобы найти самый правый индекс right, где nums[right] <= target - nums[left]. Если left <= right, добавьте количество допустимых подпоследовательностей к answer. 3⃣Возврат результата: Верните answer по модулю 10^9+7. 😎 Решение:

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        mod = 10**9 + 7
        
        power = [1] * n
        for i in range(1, n):
            power[i] = power[i - 1] * 2 % mod
        
        answer = 0
        left, right = 0, n - 1
        
        while left <= right:
            if nums[left] + nums[right] <= target:
                answer = (answer + power[right - left]) % mod
                left += 1
            else:
                right -= 1
        
        return answer

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

Задача: 1101. The Earliest Moment When Everyone Become Friends Сложность: medium В социальной группе есть n человек, пронумерованных от 0 до n - 1. Вам дан массив logs, где logs[i] = [timestampi, xi, yi] указывает, что xi и yi станут друзьями в момент времени timestampi. Дружба является симметричной. Это означает, что если a является другом b, то b является другом a. Также человек a знаком с человеком b, если a является другом b или a является другом кого-то, кто знаком с b. Верните самое раннее время, когда каждый человек стал знаком с каждым другим человеком. Если такого времени не существует, верните -1. Пример:

Input: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4
Output: 3
Explanation: At timestamp = 3, all the persons (i.e., 0, 1, 2, and 3) become friends.

👨‍💻 Алгоритм: 1⃣Отсортируйте логи по времени в хронологическом порядке, так как в задаче не указано, отсортированы ли они. 2⃣Пройдитесь по отсортированным логам, применяя структуру данных "Объединение-Поиск": Для каждого лога объедините двух участников, упомянутых в логе, с помощью функции union(a, b). Каждое объединение добавляет новые связи между участниками. 3⃣Следите за количеством групп: Изначально каждый участник рассматривается как отдельная группа. Количество групп уменьшается с каждым полезным объединением. Момент, когда количество групп уменьшается до одной, является самым ранним моментом, когда все участники становятся связанными (друзьями). Верните этот момент времени. Если такого момента не существует, верните -1. 😎 Решение:

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [1] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        
        if rootX != rootY:
            if self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1
            return True
        return False

class Solution:
    def earliestAcq(self, logs: List[List[int]], n: int) -> int:
        logs.sort()
        uf = UnionFind(n)
        group_count = n
        
        for timestamp, friendA, friendB in logs:
            if uf.union(friendA, friendB):
                group_count -= 1
            if group_count == 1:
                return timestamp
        
        return -1

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

Щипцы с паром DEWAL BEAUTY – это забота о ваших волосах Укладка мечты без вреда для волос! Инновационные паровые щипцы Elite DEWAL BEAUTY дарят бережную укладку с фантастическим блеском. • Пар мягко увлажняет волосы во время укладки • Минимизирует повреждения и сухость • Делает волосы мягкими и блестящими • Сохраняет здоровье ваших волос ✨ Преимущества: • Керамико-турмалиновое покрытие • 4 температурных режима (160-220°C) • Нагрев за 30 секунд • Автоотключение через 30 минут • Легкие (всего 290 г) Забудьте о сухости и ломкости, только шелковистые и здоровые волосы❤️ Дарим скидку 10% по промокоду SALE10 на все товары! Купить #реклама dewalbeauty.ru О рекламодателе

Задача: 1351. Count Negative Numbers in a Sorted Matrix Сложность: easy Дана матрица m x n grid, которая отсортирована по убыванию как по строкам, так и по столбцам. Вернуть количество отрицательных чисел в grid. Пример:

Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.

👨‍💻 Алгоритм: 1⃣Инициализировать переменную count = 0 для подсчета общего числа отрицательных элементов в матрице. 2⃣Использовать два вложенных цикла для итерации по каждому элементу матрицы grid, и если элемент отрицательный, увеличить count на 1. 3⃣Вернуть count. 😎 Решение:

class Solution:
    def countNegatives(self, grid):
        count = 0
        for row in grid:
            for element in row:
                if element < 0:
                    count += 1
        return count

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

Задача: 936. Stamping The Sequence Сложность: hard Вам даны две строки stamp и target. Изначально имеется строка s длины target.length со всеми s[i] == '?'. За один ход вы можете поместить штамп над s и заменить каждую букву в s на соответствующую букву из штампа. Например, если штамп = "abc" и target = "abcba", то s изначально будет "?????". За один ход вы можете: поместить штамп в индекс 0 s, чтобы получить "abc??", поместить штамп в индекс 1 s, чтобы получить "?abc?", или поместить штамп в индекс 2 s, чтобы получить "??abc". Обратите внимание, что штамп должен полностью находиться в границах s, чтобы штамповать (то есть вы не можете поместить штамп в индекс 3 s). Мы хотим преобразовать s в цель, используя не более 10 * target.length ходов. Верните массив индекса самой левой буквы, которая штампуется на каждом ходу. Если мы не можем получить цель из s за 10 * target.length оборотов, верните пустой массив Пример:

Input: stamp = "abc", target = "ababc"
Output: [0,2]

👨‍💻 Алгоритм: 1⃣Инициализировать переменные: s как массив символов '?', длиной target.length. res как список для хранения результатов. done как массив булевых значений для отслеживания того, какие позиции уже штампованы. target как массив символов для удобства. 2⃣Использовать функцию canStamp для проверки, можно ли штамповать stamp в target начиная с индекса i. Использовать функцию doStamp для штампования stamp в target начиная с индекса i. Повторять шаги, пока штампы возможны или достигнут максимум ходов (10 * target.length): Перебрать все возможные начальные позиции для штампа. Проверить, можно ли штамповать в текущей позиции. Если можно, штамповать и добавить индекс в res. 3⃣Если все символы в s соответствуют символам в target, вернуть массив res в обратном порядке. Иначе, вернуть пустой массив. 😎 Решение:

def movesToStamp(stamp, target):
    s, t = list(stamp), list(target)
    m, n = len(s), len(t)
    res = []
    done = [False] * n

    def canStamp(i):
        for j in range(m):
            if t[i + j] != '?' and t[i + j] != s[j]:
                return False
        return True

    def doStamp(i):
        for j in range(m):
            t[i + j] = '?'
        res.append(i)
        done[i] = True

    changed = True
    while changed:
        changed = False
        for i in range(n - m + 1):
            if not done[i] and canStamp(i):
                doStamp(i)
                changed = True

    if all(c == '?' for c in t):
        return res[::-1]
    return []

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

Задача: 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons Сложность: hard Вам даны три целых числа n, m и k. Рассмотрим следующий алгоритм для нахождения максимального элемента в массиве положительных целых чисел:

maximum_value = -1
maximum_index = -1
search_cost = 0
n = arr.length
for (i = 0; i < n; i++){
      if (maximum_value  < arr[i]){
           maximum_value  = arr[i]
           maximum_index = i
           search_cost = search_cost + 1
      }
}
return maximum_index

Вам необходимо построить массив arr, который имеет следующие свойства: arr содержит ровно n целых чисел. 1 <= arr[i] <= m, где (0 <= i < n). После применения указанного алгоритма к arr, значение search_cost равно k. Верните количество способов построить массив arr с учетом указанных условий. Так как ответ может быть очень большим, ответ должен быть вычислен по модулю 10^9 + 7. Пример:

Input: n = 2, m = 3, k = 1
Output: 6
Explanation: The possible arrays are [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]

👨‍💻 Алгоритм: 1⃣Инициализация и базовые случаи: Инициализируем 3D массив dp размером [n+1][m+1][k+1]. Устанавливаем базовые случаи: dp[n][...][0] = 1. 2⃣Итерация и обновление массива dp: Проходим в обратном порядке по индексам i от n-1 до 0, по maxSoFar от m до 0 и по remain от 0 до k. Для каждого из этих значений обновляем dp массив, используя предыдущие результаты для вычисления текущих значений. 3⃣Возврат результата: Возвращаем значение dp[0][0][k], которое является решением исходной задачи. 😎 Решение:

class Solution:
    def numOfArrays(self, n: int, m: int, k: int) -> int:
        MOD = 10**9 + 7
        dp = [[[0] * (k + 1) for _ in range(m + 1)] for _ in range(n + 1)]
        
        for num in range(m + 1):
            dp[n][num][0] = 1
        
        for i in range(n - 1, -1, -1):
            for maxSoFar in range(m, -1, -1):
                for remain in range(k + 1):
                    ans = 0
                    for num in range(1, maxSoFar + 1):
                        ans = (ans + dp[i + 1][maxSoFar][remain]) % MOD
                    
                    if remain > 0:
                        for num in range(maxSoFar + 1, m + 1):
                            ans = (ans + dp[i + 1][num][remain - 1]) % MOD
                    
                    dp[i][maxSoFar][remain] = ans
        
        return dp[0][0][k]

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

Задача: 210. Course Schedule II Сложность: medium Всего есть numCourses курсов, которые вы должны пройти, пронумерованных от 0 до numCourses - 1. Вам дан массив prerequisites, где prerequisites[i] = [ai, bi] указывает на то, что вы должны сначала пройти курс bi, если хотите взять курс ai. Например, пара [0, 1] указывает на то, что для прохождения курса 0 сначала нужно пройти курс 1. Верните порядок курсов, которые вы должны пройти, чтобы завершить все курсы. Если существует несколько правильных ответов, верните любой из них. Если невозможно завершить все курсы, верните пустой массив. Пример 1:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Объяснение: Всего есть 4 курса, которые нужно пройти. Чтобы взять курс 3, вы должны завершить оба курса 1 и 2. Оба курса 1 и 2 должны быть взяты после того, как вы завершите курс 0.
Таким образом, один из правильных порядков курсов — [0,1,2,3]. Другой правильный порядок — [0,2,1,3].

👨‍💻 Алгоритм: 1️⃣Инициализация и построение графа: Инициализируйте стек S, который будет содержать топологически отсортированный порядок курсов в нашем графе. Постройте список смежности, используя пары ребер, указанные на входе. Важно отметить, что пара вида [a, b] указывает на то, что курс b должен быть пройден, чтобы взять курс a. Это подразумевает ребро вида b ➔ a. Учтите это при реализации алгоритма. 2️⃣Запуск поиска в глубину (DFS): Для каждого узла в нашем графе выполните поиск в глубину (DFS), если этот узел еще не был посещен во время DFS другого узла. Предположим, что мы выполняем поиск в глубину для узла N. Рекурсивно обойдите всех соседей узла N, которые еще не были обработаны. 3️⃣Обработка узлов и возвращение результата: После обработки всех соседей добавьте узел N в стек. Мы используем стек для моделирования необходимого порядка. Когда мы добавляем узел N в стек, все узлы, которые требуют узел N в качестве предшественника (среди других), уже будут в стеке. После обработки всех узлов просто верните узлы в порядке их присутствия в стеке от вершины до основания. 😎 Решение:

from collections import defaultdict

class Solution:
    WHITE = 1
    GRAY = 2
    BLACK = 3

    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        adj_list = defaultdict(list)
        for dest, src in prerequisites:
            adj_list[src].append(dest)

        topological_sorted_order = []
        is_possible = True
        color = {k: Solution.WHITE for k in range(numCourses)}

        def dfs(node: int) -> None:
            nonlocal is_possible
            if not is_possible:
                return
            color[node] = Solution.GRAY
            if node in adj_list:
                for neighbor in adj_list[node]:
                    if color[neighbor] == Solution.WHITE:
                        dfs(neighbor)
                    elif color[neighbor] == Solution.GRAY:
                        is_possible = False
            color[node] = Solution.BLACK
            topological_sorted_order.append(node)

        for vertex in range(numCourses):
            if color[vertex] == Solution.WHITE:
                dfs(vertex)

        return topological_sorted_order[::-1] if is_possible else []

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

Аукцион выделенных серверов! Серверы дешевеют у вас на глазах! Новые лоты каждый день, скидки до -35% на весь срок аренды. Успейте арендовать, пока лот не ушел другому! Получить предложение #реклама 16+ selectel.ru О рекламодателе

Сегодня последний день, когда можно приобрести пожизненный PRO тариф easyoffer Акция до 20 февраля 00:00 Покупаешь сейчас один раз — пользуешься всю жизнь без лимита, включая все будущие функции. 👉 Смотри подробности тарифа и покупай на https://easyoffer.ru/

Гранты на обучение в Центральном университете Получи грант на 4 года до 3 480 000 ₽ на учебу в бакалавриате Центрального университета. Гранты покрывают до 100% стоимости обучения. Сумма гранта не уменьшается, а может только увеличиться за дополнительные достижения и успехи в учебе. Конкурс состоит из двух этапов: тестирование и бизнес-игра. Фаст-трек: поступи по ускоренному пути, если у тебя уже есть достижения. Грант открывает доступ к мероприятиям университета: стипендиальная программа, пробные ЕГЭ и другие. Для выпускников 10–11-х классов и СПО. 💻 Участвуй в конкурсе уже сейчас! Подать заявку #реклама 16+ apply.cu.ru О рекламодателе

Завтра конец акции на возможность приобрести PRO тариф по цене одного года Доступный функционал включает базы вопросов с собеседований, задач для live-coding, реальных интервью и тестовых заданий от топ-компаний, а также аналитику требований для резюме и тренажеры с режимом симуляции собеседования под конкретную компанию. Акция до 20 февраля (включительно) на PRO-тариф. Покупаешь сейчас один раз — пользуешься всю жизнь без лимита, включая все будущие функции. 👉 Смотри подробности тарифа и покупай на https://easyoffer.ru/