leetcode210 -- Course Schedule II

leetcode210 -- Course Schedule II

207的变型

avatar

这个是207题目的变形,刚才是问可不可以上完所有的课程,现在是问给出上课的方案,这就像是迷宫问题,先问能不能走出来,如果能的话,就给出一种走出来的方案。 所以这里添加了一个temp,用来记录和保存那以可以的路,这里只是给出一种方式,并不是给出所有的方式,所以这样写就可以了。

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        
        res = []
        
        graph = [[] for _ in range(numCourses)]
        visit = [0]*numCourses
        
        for i, j in prerequisites:
            graph[i].append(j)
            
        def notInRing(i, temp):
            if visit[i] == -1:
                return False
            if visit[i] == 1:
                return True
            
            visit[i] = -1
            for j in graph[i]:  # graph[i]里存的都是i的先行课程,所以最终temp就是要上课程i的一个方法.
                if not notInRing(j, temp):
                    return False
                
            visit[i] = 1
            temp.append(i)
            return True
        
        for i in range(numCourses):
            temp = []
            if not notInRing(i, temp):
                return []
            res += temp
            
        return res
        

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦