LeetCode 207.课程表 Java实现

本文主要是介绍LeetCode 207.课程表 Java实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;public class Solution
{public boolean canFinish(int numCourses, int[][] prerequisites) {// 初始化图Map<Integer, List<Integer>> map = new HashMap<>();// 存储每个结点的入度int[] indegree = new int[numCourses];for (int i = 0; i < prerequisites.length; i++) {int second = prerequisites[i][0];int first = prerequ2isites[i][1];if (!map.containsKey(first))map.put(first, new ArrayList<>());map.get(first).add(second);// 入度加一，从first->secondindegree[second]++;}// 存储所有入度为0的结点Queue<Integer> q = new LinkedList<>();for (int i = 0; i < numCourses; i++) {if (indegree[i] == 0)q.offer(i);}// 用来计算拓扑排序的结点个数int count = 0;while (!q.isEmpty()) {// 获取第一格入度为0的结点int val = q.poll();count++;// 判断很关键if (!map.containsKey(val))continue;// 获取val的临结点List<Integer> tmp = map.get(val);for (int i = 0; i < tmp.size(); i++) {// 把所有的以val为开头的入度减一int idx = tmp.get(i);indegree[idx]--;// 如果入度为0，则把该结点加入队列中if (indegree[idx] == 0)q.offer(idx);}}return count == numCourses;}}

 

这篇关于LeetCode 207.课程表 Java实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---