题目
你这个学期必须选修
numCourses门课程，记为0到numCourses - 1。在选修某些课程之前需要一些先修课程。 先修课程按数组
prerequisites给出，其中prerequisites[i] = [ai, bi]，表示如果要学习课程ai则 必须 先学习课程bi。
- 例如，先修课程对
[0, 1]表示：想要学习课程0，你需要先完成课程1。请你判断是否可能完成所有课程的学习？如果可以，返回
true；否则，返回false。
解题思路
- 以课程id进行整理数据，收集需要当前课程作为前置课程的课程；
- 从不需要前置课程的课程进行清除数据；
- 若课程数量最后清为0则可以学完所有课程，否则则不可以。
代码展示
class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { List<List<Integer>> resources = new ArrayList<>(); int[] indegrees = new int[numCourses]; for (int i = 0; i < numCourses; i++){ resources.add(new ArrayList<>()); } for (int[] nums : prerequisites){ indegrees[nums[0]]++; resources.get(nums[1]).add(nums[0]); } Queue<Integer> queue = new LinkedList<>(); for (int i = 0; i < numCourses; i++){ if(indegrees[i] == 0){ queue.add(i); } } while (!queue.isEmpty()){ int val = queue.poll(); numCourses--; for (int num : resources.get(val)){ if(--indegrees[num] == 0){ queue.add(num); } } } return numCourses == 0; } }
