【Hot100】LeetCode—207. 课程表

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

1- 思路

有向图+记录入度数组+出度列表

根据输入
① 构造遍历构造入度数组
② 构造出度列表
根据入度数组为 0 的数加入到队列中，进行处理

2- 实现

⭐207. 课程表——题解思路

在这里插入图片描述

class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {// 定义入度数组int[] inNums = new int[numCourses];// 出度列表List<List<Integer>> outList = new ArrayList<>();Queue<Integer> queue = new LinkedList<>();//初始化出度for(int i = 0 ; i < numCourses ;i++){outList.add(new ArrayList<>());}// 入度初始化// [1] 为 入度的 key ，value 进行 ++ 即可for(int[] num:prerequisites){inNums[num[0]]++;// 链表也要初始化outList.get(num[1]).add(num[0]);}for(int i = 0 ; i < numCourses;i++){if(inNums[i] == 0){queue.add(i);}}// 处理 0 while(!queue.isEmpty()){int pre = queue.poll();// 先对课程减减numCourses--;// 处理链表for(int num: outList.get(pre)){inNums[num]--;if(inNums[num]==0){queue.add(num);}}}return numCourses==0;}
}

3- ACM 实现

public class canFinish {public static boolean canFinish(int numCourses, int[][] prerequisites){// 1. 数据结构// 入度、出度、队列int[] inNums = new int[numCourses];List<List<Integer>> outList = new ArrayList<>();Queue<Integer> queue = new LinkedList<>();// 2. 初始化出度for(int i = 0 ; i < numCourses;i++){outList.add(new ArrayList<>());}// 3. 遍历数组，初始化入度和出度for(int[] num:prerequisites){// 入度inNums[num[0]] ++;// 出度outList.get(num[1]).add(num[0]);}// 4. 初始化队列for(int i = 0 ; i < numCourses;i++){if(inNums[i]==0){queue.add(i);}}// 遍历 queuewhile(!queue.isEmpty()){int pre = queue.poll();numCourses--;for (int num:outList.get(pre)){inNums[num]--;if(inNums[num] == 0){queue.add(num);}}}return numCourses==0;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("输入课程数");int numCourses = sc.nextInt();String konge = sc.nextLine();System.out.println("输入二维数组");String input = sc.nextLine();input = input.substring(2,input.length()-2);String[] rows = input.split("],\\[");int m = rows.length;int n = rows[0].split(",").length;int[][] prerequisites = new int[m][n];for(int i = 0 ; i < m;i++){String[] row = rows[i].split(",");for(int j = 0 ; j < n;j++){prerequisites[i][j] = Integer.parseInt(row[j]);}}System.out.println("结果是"+canFinish(numCourses,prerequisites));}
}