leetcode-207-课程表

问题描述：

现在你总共有n门课需要选，记为0到n-1。

在选修某些课程之前需要一些先修课程。例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？

示例 1:

输入:2, [[1,0]]输出: true解释:总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。

示例 2:

输入:2, [[1,0],[0,1]]输出: false解释:总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。

说明:

输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。

你可以假定输入的先决条件中没有重复的边。

提示:

这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。

DFS深度优先探索是算法笔试、面试中经常遇到的问题，我觉得这道题是一个很好得例子，下面为代码

优化前：

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<ArrayList<Integer>> grah = new ArrayList<>();
        for(int i=0;i<numCourses;i++)
            grah.add(new ArrayList<>());
        
        for(int i=0;i<prerequisites.length;i++){
            grah.get(prerequisites[i][0]).add(prerequisites[i][1]);
        }
        
        int[] visited = new int[numCourses];
        
        for(int i=0;i<numCourses;i++){
            //判断是否有环
            if(dfs(grah,visited,i))
                return false;
        }
        
        //发现无环，则返回true
        return true;
    }
    
    public boolean dfs(List<ArrayList<Integer>> grah,int[] visited,int num){
        //如果已经被访问过，则发现环
        if(visited[num] == 1)
            return true;

        
        visited[num] = 1;//表示已经访问过此节点
        for(int id : grah.get(num)){
            if(dfs(grah,visited,id))
                return true;
        }
        visited[num] = 0;//去掉访问此节点标记
        
        return false;        
    }
}

测试结果：

1546595234(1).png

优化：
其实优化方式很简单，原来的标记为：0-未访问过；1-访问过
在此基础上多加一个标记：0-未访问过；1-访问过；2-曾经访问过但是当前没访问
多加这个标记可以理解为，如果曾经访问过这个节点时不存在环，那么从这节点走下去也不会存在环，直接返回false就可以了。下面为代码，改动只有一点点哦

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<ArrayList<Integer>> grah = new ArrayList<>();
        for(int i=0;i<numCourses;i++)
            grah.add(new ArrayList<>());
        
        for(int i=0;i<prerequisites.length;i++){
            grah.get(prerequisites[i][0]).add(prerequisites[i][1]);
        }
        
        int[] visited = new int[numCourses];
        
        for(int i=0;i<numCourses;i++){
            //判断是否有环
            if(dfs(grah,visited,i))
                return false;
        }
        
        //发现无环，则返回true
        return true;
    }
    
    public boolean dfs(List<ArrayList<Integer>> grah,int[] visited,int num){
        //如果已经被访问过，则发现环
        if(visited[num] == 1)
            return true;
        //曾经访问过，但从此节点走下去不存在环
        if(visited[num] == 2)
            return false;
        
        visited[num] = 1;//添加访问标记
        for(int id : grah.get(num)){

            if(dfs(grah,visited,id))
                return true;
        }
        visited[num] = 2;//去掉被访问标记
        
        return false;        
    }
}

运行结果

1546595248(1).png

优化结果是不是非常明显，哈哈

之后会更新BFS的解法~

最后编辑于：2019.01.04 17:57:01