Планирование курса от Leetcode - PullRequest
Новая
       31

Планирование курса от Leetcode

0 голосов
/ 06 июля 2018

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

Вот вопрос:

Всего вам нужно пройти n курсов, помеченных от 0 до n-1.

Некоторые курсы могут иметь предпосылки, например, чтобы пройти курс 0, сначала нужно пройти курс 1, который выражается в виде пары: [0,1]

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

Может быть несколько правильных заказов, вам просто нужно вернуть один из них. Если невозможно закончить все курсы, верните пустой массив.

Пример 1:

Ввод: 2, [[1,0]] Выход: [0,1] Объяснение: Всего есть 2 курса. Чтобы пройти курс 1, вы должны были закончить курс 0. Таким образом, правильный порядок курса - [0,1]. Пример 2:

Ввод: 4, [[1,0], [2,0], [3,1], [3,2]] Выход: [0,1,2,3] или [0,2,1,3] Пояснение: Всего есть 4 курса. Чтобы пройти курс 3, вы должны были закончить оба курса 1 и 2. Оба курса 1 и 2 должны быть пройдены после того, как вы закончили курс 0. Таким образом, один правильный порядок курсов - [0,1,2,3]. Другой правильный порядок - [0,2,1,3].

Вот мое решение: Решение класса: def findOrder (self, numCourses, пререквизиты): 

    """
    :type numCourses: int
    :type prerequisites: List[List[int]]
    :rtype: bool
    """
    #Convert prerequisites into an adjacency list
    adj = []
    for i in range(numCourses):
        adj.append(set())
    for pair in prerequisites:
        adj[pair[0]].add(pair[1])

    def DFSHelper(s):
        visited.add(s)
        stack.add(s)
        for neighbor in adj[s]:
            # if neighbor vertex has never been visted before, there is no way it could be a backedge.
            # visit this unvisited vertex
            if(neighbor not in visited):
                if(not DFSHelper(neighbor)):
                    return False
                Sorted.append(neighbor)
            else:
                if(neighbor in stack):
                    return False  
        stack.remove(s)
        return True

    visited = set()
    stack = set()
    Sorted = []
    for j in range(len(adj)):
        if(j not in visited):
            if(not DFSHelper(j)):
                print(j)
                return []
            Sorted.append(j)
    return Sorted

Сначала я преобразовал данный список предварительных условий в представление графа в списке смежности, а затем провел топологическую сортировку графа. Я использовал DFS рекурсивно, чтобы топологически отсортировать график. В отсортированном списке хранится результат сортировки. При выполнении DFS я также проверял, содержит ли граф какой-либо цикл, если он просто возвращает []. В целях проверки цикла я поддерживал набор, называемый стеком, в котором хранятся все вершины, которые в данный момент находятся в стеке вызовов.

...