leetcode----210. Course Schedule II

本文主要是介绍leetcode----210. Course Schedule II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：

https://leetcode.com/problems/course-schedule-ii/

大意：

给定所需要修习课程的总数numCourses，以及两门课之间的先序关系prerequisites，其中prerequisites中每个元素是一个二元组（长度为2的数组），对于任意一个二元组nums，意义为:修习nums[0]之前必须先修习nums[1]。找出一种方案可以使得满足给定的所有课程先序关系切最终修习完成numCourses门课程

思路：

这些先序关系可以看成一个一个有向图，而我们的目的是要求一个拓扑序列；如果不存在拓扑序列，则返回空数组(new int[]{})

记map[nums[0]]为一个有序关系的终点，map[nums[0]].add(nums[1])即表示有一条有序边nums[1]->nums[0]。图的关系清楚了，之后就是模拟寻找拓扑序列了

第一步：找到所有顶点中，入度为0的顶点。即若顶点k为入度为0的一个顶点，则map[k].size() == 0,因为没有其他顶点指向它。

第二步：将以这些顶点为起点的边全部删掉，并把这些顶点放入一个Set（用于记录哪些顶点是已被使用过的）

第三步：再从剩余的顶点中，循环第一步到第三步。

若在上述过程中的某一时刻，发现不存在入度为0的顶点且已选择的顶点数小于numCourses，则表示该图不存在拓扑序列，返回空数组

代码：

class Solution {public int[] findOrder(int numCourses, int[][] prerequisites) {List<Integer> res = new ArrayList<>();List<Integer>[] map = new ArrayList[numCourses];for (int i = 0; i < numCourses; i++) {map[i] = new ArrayList<>();}// 构图for (int[] nums : prerequisites) {map[nums[0]].add(nums[1]); // 表示nums[1]指向nums[0]  若map[k].size() == 0 则表明k的入度为0}LinkedList<Integer> queue = new LinkedList<>(); // 用于存储当前入度为0的节点Set<Integer> set = new HashSet<>(); // 用于存放已使用的入度为0的节点while (res.size() < numCourses) {for (int i = 0;i < numCourses;i++) {if (!set.contains(i) && !queue.contains(i) && map[i].size() == 0) {
//	                	System.out.println(i);queue.add(i);}}// 如果还未找到所有节点，但已没有入度为0的节点了 则返回nullif (queue.size() == 0) {return new int[]{};}int num = queue.removeFirst(); // 这个节点为入度为0的节点
//	            System.out.println(num);set.add(num);res.add(num); // 将入度为0的节点添加到resfor (int i = 0;i < numCourses;i++) {if (map[i].contains(num)) {map[i].remove(new Integer(num));}}}int[] a = new int[numCourses];for (int i = 0;i < numCourses;i++) {a[i] = res.get(i);   }return a;}
}

 结果：

结论：

代码效率很差。分析原因：

• 在数组（ArrayList）中用到了大量的contains操作，影响性能
• 每一次找到该轮所有入度为0的点并加入到队列后，都只是取出一个入度为0的点进行“去边”操作
• 将List的元素复制到数组的方式不够高效
• 在List中删除节点太耗时

改进：

在前一个版本：判断有向图中是否存在拓扑序列 基础上改进

class Solution {// 找到拓扑序列public int[] findOrder(int num, int[][] pre) {int[] degree = new int[num]; // 记录每个节点的入度List<Integer>[] graph = new ArrayList[num]; // 记录各个边的关系for (int i = 0; i < num; i++) {graph[i] = new ArrayList<>();}for (int[] nums : pre) {degree[nums[0]]++;graph[nums[1]].add(nums[0]); // nums[1] -> nums[0]}int[] res = new int[num];int count = 0, idx = 0;ArrayList<Integer> idxs = new ArrayList<>(); // 存储所有当前入度为0的点的位置// 记录入度为0的点for (int i = 0; i < degree.length; i++) {if (degree[i] == 0) {idxs.add(i);res[idx++] = i;} }while (!idxs.isEmpty()) {int curIdx = idxs.remove(idxs.size() - 1);for (int tail : graph[curIdx]) {if (--degree[tail] == 0) {// 又找到一个新的入度为0的点idxs.add(tail);res[idx++] = tail; }}count++;}return count == num ? res : new int[0];}
}

 

这篇关于leetcode----210. Course Schedule II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---