LeetCode第207题--Course Schedule

LeetCode第207题–Course Schedule

原题

给出课程总数,用不同整数编号表示不同课程,用一个二维数组表示多组先修课程的顺序对。

比如:有2门课,要学课程1必须先学课程0,这是有效的。

2, [[1,0]]

如果有2门课,要学课程1必须先学课程0,要学课程0必须先学课程1,这是无效的。

2, [[1,0],[0,1]]

需要完成的就是这个方法:

    public boolean canFinish(int numCourses, int[][] prerequisites) {

    }   

测试数据:

8, [[1,0],[2,6],[1,7],[5,1],[6,4],[7,0],[0,5],[5,1],[6,4]]

解题思路

由课程的编号构成一幅有向图,方向为先修顺序,构造完成后只要判断图是否有环。

有向图数据结构

初始化时构造一张图,但只有顶点个事,顶点之间没有边相连。

用邻接表表示有向图。

调用addEdge()方法可以将课程之间先修关系写到图中。

    private class Digraph {

        private final int V;
        private ArrayList<Integer>[] adj;

        public Digraph(int V) {
            this.V = V;
            adj = (ArrayList<Integer>[]) new ArrayList[V];
            for (int v = 0; v < V; v++) {
                adj[v] = new ArrayList<Integer>();
            }
        }

        public void addEdge(int v, int w) {
            adj[v].add(w);
        }

        public int V() {
            return V;
        }

        public Iterable<Integer> adj(int v) {
            return adj[v];
        }

    }

判断有向图中是否有环

用一个数组boolean[] onStack保存递归调用期间栈上的所有顶点.

onStack[v]=true,记录顶点v出现在这次dfs中,在这次dfs结束后,是onStack[v]=false

在递归执行dfs的过程中,记录当前下当前顶点在递归调用栈中,这样以后的递归调用栈只要判断它的相连点是否在之前的递归调用栈中出现过,就能判断是否有环。

    private class DirectedCycle {
        private boolean[] marked;        // marked[v] 顶点v是否被访问过
        private boolean[] onStack;       //保存递归调用期间栈上的所有顶点。 onStack[v] = ?顶点v是否在栈中
        private boolean hasCycle;       // 有向图中是否环

        public DirectedCycle(Digraph G) {
            marked = new boolean[G.V()];
            onStack = new boolean[G.V()];
            hasCycle = false;
            for (int v = 0; v < G.V(); v++)   //对图中每一个没有被访问过的点做深度优先遍历
                if (!marked[v]) dfs(G, v);
        }


        /**
         * 从v顶点开始做深度优先遍历
         */
        private void dfs(Digraph G, int v) {
            onStack[v] = true;
            marked[v] = true;
            for (int w : G.adj(v)) {        //遍历所有顶点v的相连点
                if (hasCycle) return;       //如果已经找到一个环就不再dfs
                else if (!marked[w]) {      //对每一个未访问过的点继续dfs
                    dfs(G, w);
                } else if (onStack[w]) {    //顶点w在之前的递归调用栈中,并且已经被访问过,构成环
                    hasCycle = true;
                }
            }
            onStack[v] = false;             //顶点v所有的相连点遍历结束,顶点v退出当前调用栈
        }

        public boolean hasCycle() {
            return hasCycle;
        }
    }

主方法

     public boolean canFinish(int numCourses, int[][] prerequisites) {
        Digraph G = new Digraph(numCourses);
        for (int i = 0; i < prerequisites.length; i++) {
            for (int j = 0; j < prerequisites[i].length; j++) {
                G.addEdge(prerequisites[i][j], prerequisites[i][++j]);
            }
        }
        DirectedCycle dag = new DirectedCycle(G);

        return !dag.hasCycle();

    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序生活

hdu-1098 Ignatius's puzzle(费马小定理)费马小定理同余式证明应用Ignatius's puzzle运行结果

费马小定理 费马小定理是数论中的一个定理:假如a是一个整数,p是一个质数,那么 ? 是p的倍数,可以表示为 ? 如果a不是p的倍数,这个定理也可以写成(同余式...

3494
来自专栏PPV课数据科学社区

【学习】深度解析中文分词器算法(最大正向/逆向匹配)

中文分词算法概述: 1:非基于词典的分词(人工智能领域) 相当于人工智能领域计算。一般用于机器学习,特定领域等方法,这种在特定领域的分词可以让计算机在...

2796
来自专栏nnngu

数据结构10 图

这一篇我们要总结的是图(Graph),图可能比我们之前学习的线性结构和树形结构都要复杂,不过没关系,我们一点一点地来总结。那么关于图,我将从以下几点进行总结: ...

3297
来自专栏后端技术探索

常见算法面试题

这几天在网上看到一篇关于算法面试题的博客,归纳的很好,有不少经典的题目,大部分来自《编程珠玑》、《编程之美》、《代码之美》三本书。这里给出书上的解答以及一些思考...

742
来自专栏数据结构与算法

P3818 小A和uim之大逃离 II

题目背景 话说上回……还是参见 https://www.luogu.org/problem/show?pid=1373 吧 小a和uim再次来到雨林中探险。突然...

2907
来自专栏小狼的世界

利用JS实现的根据经纬度计算地球上两点之间的距离

第一种是默认地球是一个光滑的球面,然后计算任意两点间的距离,这个距离叫做大圆距离(The Great Circle Distance)。

722
来自专栏程序生活

图的广度优先搜索和深度优先搜索(邻接链表表示)邻接链表广度优先搜索深度优先搜索运行结果

邻接链表 邻接表表示法将图以邻接表(adjacency lists)的形式存储在计算机中。所谓图的邻接表,也就是图的所有节点的邻接表的集合;而对每个节点,它...

3954
来自专栏数据结构与算法

20:反反复复

20:反反复复 总时间限制: 1000ms 内存限制: 65536kB描述 Mo和Larry发明了一种信息加密方法。他们首先决定好列数,然后将信息(只包含字...

3408
来自专栏青枫的专栏

css属性与js中style对象的属性对应表

583
来自专栏mathor

floyd算法

 floyd算法解决的问题是在图中找到从i号结点到j号结点最短路径值(边的权值)的问题,核心代码就下面四行

401

扫码关注云+社区