算法練習 Leetcode 力扣 207. Course Schedule 解法

這題以前覺得特別難,其實是簡化版的topological sort,也就是只需要判斷有沒有環(circular dependency)和省掉了sort部分。可以用269 alien dictionary同樣的DFS思路加以簡化而成。

這是最近寫得比較滿意的python解法。

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        edges = {c: set() for c in range(numCourses)}
        for prereq in prerequisites:
            edges[prereq[1]].add(prereq[0])
        
        seen = {}
        
        def dfs(start):
            if start in seen:
                return seen[start]
            seen[start] = False
            for nxt in edges[start]:
                if not dfs(nxt):
                    return False
            seen[start] = True
            return True
        
        if not all(dfs(start) for start in range(numCourses)):
            return False
        return True

對比一下大概半年前寫得當時比較滿意版本,其實算法差不多。有如下小改進讓code更短了:
1. seen用了Tree和False表示走通了的和當前正在走的路徑,比原來的更省事。看來2種狀態是判斷環和避免重新走原來走過的路所必要的。
2. 節點全部寫進edges裡面,edges = {c: set() for c in range(numCourses)} ,不管有沒有dependency,省了 if i not in deps: 判斷
3. 需要order的話,dfs參數start, edges, seen order。不需要的話order的話就省掉order,只要start, edges, seen。用函數內定義函數可以少寫很多用來傳遞狀態的參數。

class Solution(object):
    def __init__(self):
        self.UNKNOWN = 0
        self.VISITED = 1
        self.CANTAKE = 2
        
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        deps = {}
        for pre in prerequisites:
            if pre[0] in deps:
                deps[pre[0]].add(pre[1])
            else:
                deps[pre[0]] = {pre[1]}
                
        status = [self.UNKNOWN] * numCourses
        for i in range(numCourses):
            if self.okToTake(i, status, deps) == False:
                return False
        return True
        
    def okToTake(self, i, status, deps):
        if status[i] == self.CANTAKE:
            return True
        elif status[i] == self.VISITED:
            return False
        status[i] = self.VISITED
        if i not in deps:
            status[i] = self.CANTAKE
            return True
        for dep in deps[i]:
            if self.okToTake(dep, status, deps) == False:
                return False
        status[i] = self.CANTAKE
        return True
    

Leave a Comment

Your email address will not be published.