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 条评论
登录 后参与评论

相关文章

来自专栏十月梦想

js二维数组遍历

1282
来自专栏码匠的流水账

聊聊hystrix的BucketedCounterStream

hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/metric/consumer/BucketedCou...

691
来自专栏小樱的经验随笔

Educational Codeforces Round 21(A.暴力,B.前缀和,C.贪心)

A. Lucky Year time limit per test:1 second memory limit per test:256 megabytes i...

2797
来自专栏HansBug's Lab

2292: 【POJ Challenge 】永远挑战

2292: 【POJ Challenge 】永远挑战 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 553 ...

2996
来自专栏后端之路

来自Google的瓜娃简介之Lists

注:以下分析均基于Guava18 背景 在很久很久以前(大概就是jdk7之前吧)没有钻石语法的我们苦逼的一遍又一遍的写着泛型 List<String> lis...

2515
来自专栏菩提树下的杨过

恶心的0.5四舍五入问题

四舍五入是财务类应用中常见的需求,按中国人的财务习惯,遇到0.5统一向上进位,但是c#与java中默认的却不是这样。 见c#代码: 1 stat...

19810
来自专栏deed博客

数学速算法

1242
来自专栏HansBug's Lab

3211: 花神游历各国

3211: 花神游历各国 Time Limit: 5 Sec  Memory Limit: 128 MB Submit: 1042  Solved: 381 ...

2665
来自专栏HansBug's Lab

3386/1752: [Usaco2004 Nov]Til the Cows Come Home 带奶牛回家

3386/1752: [Usaco2004 Nov]Til the Cows Come Home 带奶牛回家 Time Limit: 1 Sec  Memory...

36911
来自专栏小樱的经验随笔

BZOJ 3097: Hash Killer I【构造题,思维题】

3097: Hash Killer I Time Limit: 5 Sec  Memory Limit: 128 MBSec  Special Judge Su...

1916

扫码关注云+社区