leetcode207 -- Course Schedule I

leetcode207 -- Course Schedule I

题目

avatar

意思是有一系列的课程,但是上某一门课的时候可能需要有其他的先行课,问能否把所有的课都上完。

思路

转化为图论问题,即每一门课与其先行课之间可以连接一条边,那么只要这些边不行成环,就可以把这些课都上完。 这里面也有一些DP的思想在里面,递推公式是,判断第i个node在不在一个环里面,就相当于判断与i 相连的那些节点在不在一个环里面。

解法如下

avatar

解释

visit是记录第i门课的结果的,即初始化为0,意思是还没有被check,如果是1的话,就意味着没有环通过这个结点,如果为-1的话就意味着有环通过这个结点, isInRing(i)就是判断第i个结点是不是在一个环里面,刚开始要看它的状态,即在visit里面的值, 如果是-1,说明有环通过它,返回false,如果是1,说明没有环通过它返回true, 上面两个都没有走的话,说明它是0,即它还没有被check,所以先标记它为-1,意思是正在被check,或者默认它是有环经过它的, 然后进入下面的递推公式,去check和它相连的那些边有没有环,如果都没有的话,就把它标记为1,并返回true, 所以这里面也有DFS的思想在里面。 最后返回的是所有的结点的状态的一个综合,即只要有一个结点的是false,那就意味着不能够上完所有的课。

也可以看下面的代码解释

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        
        graph = [[] for _ in range(numCourses)] # 储备创建图
        visit = [0]*numCourses   # 初始化0是表示还没有被check
        
        for x in prerequisites:
            graph[x[0]].append(x[1])    # 每一个列表保存与他相连的节点.
            
        def notInRing(i):
            if visit[i]==-1:
                return False
            
            if visit[i] ==1:
                return True
            
            # 走这条路了,说明此时visit[i]=0即还没有被check,所以把它弄成-1,因为下面只要是返回False,它的就是-1,
            visit[i] = -1
            
            for j in graph[i]:
                if not notInRing(j):
                    return False
            
            # 如果它的节点都不在环中,说明这个也不在环中,就标记它为1,并返回true.
            visit[i] = 1
            return True
        
        return all(notInRing(i) for i in range(numCourses))

打赏,谢谢~~

取消

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

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

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