欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 207.课程表

程序员文章站 2024-03-11 12:07:55
...

题目描述

你这个学期必须选修 numCourse 门课程,记为 0 到 numCourse-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。这是不可能的。

解题思路

广度优先搜索BFS

  • 模式识别:对于存在先后次序(或者有向)图的周游,可以利用入度实现拓扑排序,每次访问入度为0的节点,使相邻节点入度-1,当相邻节点入度为0时,进入队列,优点:不用单独记录节点的访问状态

ex1

  • 入度为0的节点先加入到队列中,即B,D进入队列
    LeetCode 207.课程表
  • 队首元素出队,相邻节点入度-1,节点A入度变为0,加入队列
    LeetCode 207.课程表
  • 弹出节点D,D的相邻节点入度-1
    LeetCode 207.课程表
  • 弹出队首元素A,A的相邻节点入度-1,C和F节点入度变为0,C和F进入队列
    LeetCode 207.课程表
  • 弹出C
    LeetCode 207.课程表
  • 弹出F
    LeetCode 207.课程表
  • 最后再弹出E和G就得到想要的拓扑排序
    LeetCode 207.课程表

Java实现

  • 算法思路:首先利用散列表存储节点和临近节点之间的关系,利用数组储存入度和最后的结果,利用队列进行对入度为0的节点访问,然后利用循环遍历输入构造先修关系和入度,队列中先加入入度为0的节点,之后访问队列,先从队列中的首部访问,并加入到最后的结果中,再减少相邻节点的入度,一旦有节点入度为0说明先修课程满足,可以把该课程加入队列,最后通过访问的节点个数来判断是否所有课程都学完了
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
            Map<Integer, List<Integer>> adjList = new HashMap<Integer, List<Integer>>();
            int[] indegree = new int[numCourses];
            int[] topologicalOrder = new int[numCourses];
            Queue<Integer> q = new LinkedList<Integer>();

            for (int i = 0;i < prerequisites.length;i++){
                int dest = prerequisites[i][0];
                int src = prerequisites[i][1];
                List<Integer> lst = adjList.getOrDefault(src,new ArrayList<Integer>());
                lst.add(dest);
                adjList.put(src,lst);

                indegree[dest] += 1;
            }

            for (int i = 0;i < numCourses;i++){
                if(indegree[i] == 0){
                    q.add(i);
                }
            }
            int i = 0;
            while (!q.isEmpty()){
                int node = q.remove();
                topologicalOrder[i++] = node;

                if (adjList.containsKey(node)){
                    for (Integer neighbor : adjList.get(node)){
                        indegree[neighbor]--;

                        if (indegree[neighbor] == 0){
                            q.add(neighbor);
                        }
                    }
                }
            }

            if (i == numCourses){
                return true;
            }
            return false;
    }
}

LeetCode 207.课程表

  • 时间复杂度:O(n+m)
相关标签: LeetCode