2022-1-14图day2(2022-1-14 figure Day2)-其他

2022-1-14图day2(2022-1-14 figure Day2)

``numCourses``
``0``
``numCourses - 1``

``prerequisites``
``prerequisites[i] = [ai, bi]``
``ai``
``bi``
• 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

``true``
``false``

``````输入：numCourses = 2, prerequisites = [[1,0]]

``````输入：numCourses = 2, prerequisites = [[1,0],[0,1]]

• 1 <= numCourses <= 105
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• prerequisites[i] 中的所有课程对 互不相同
`````` 1 class Solution {
2     boolean[] node;
3     boolean[] visit;
4     boolean hascircle=false;
5     public boolean canFinish(int numCourses, int[][] prerequisites) {
6         List<List<Integer>> list=build(numCourses,prerequisites);
7         node = new boolean[numCourses];
8         visit = new boolean[numCourses];
9         for (int i=0;i<numCourses;i++) {
10             transer(i,list);
11             if (hascircle) return false;
12         }
13         return true;
14     }
15     //转化为邻接表
16     public List<List<Integer>> build(int n,int[][] prerequisites) {
17         List<List<Integer>> list=new ArrayList<>();
18         for (int i=0;i<n;i++) {
19             List<Integer> l=new ArrayList<>();
21         }
22         for (int[] x:prerequisites) {
23             int start=x[0],end=x[1];
25         }
26         return list;
27     }
28
29     public void transer(int x,List<List<Integer>> list) {
30         if (node[x]) {
31             hascircle=true;
32         }
33         if (visit[x]||hascircle) {
34             return;
35         }
36         node[x]=true;
37         //遍历过x节点
38         visit[x]=true;
39         //经过x节点
40         for (int i=0;i<list.get(x).size();i++) {
41             transer(list.get(x).get(i),list);
42         }
43         node[x]=false;
44     }
45 }``````

``numCourses``
``0``
``numCourses - 1``
``prerequisites``
``prerequisites[i] = [ai, bi]``
``ai``
``bi``
• 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。

``[0,1] 。``

``[0,1,2,3]``
``[0,2,1,3]``

``````输入：numCourses = 1, prerequisites = []

``````
• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= numCourses * (numCourses - 1)
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• ai != bi
• 所有[ai, bi] 互不相同
`````` 1 class Solution {
2     int[] in;
3     public int[] findOrder(int numCourses, int[][] prerequisites) {
4         in = new int[numCourses];
5         List<List<Integer>> graph=build(numCourses,prerequisites);
7         for (int i=0;i<numCourses;i++) {
8             if (in[i]==0) queue.offer(i);
9         }
10         int index=0;
11         int[] res=new int[numCourses];
12         while (!queue.isEmpty()) {
13             int temp=queue.poll();
14             res[index++]=temp;
15             for (int x:graph.get(temp)){
16                 in[x]--;
17                 if (in[x]==0) queue.offer(x);
18             }
19         }
20         return index==numCourses?res:new int[]{};
21     }
22
23
24     public List<List<Integer>> build(int n,int[][] prerequisites) {
25          List<List<Integer>> list=new ArrayList<>();
26         for (int i=0;i<n;i++) {
27              List<Integer> l=new ArrayList<>();
29         }
30         for (int[] x:prerequisites) {
31             int start=x[0],end=x[1];
33             in[start]++;
34         }
35         return list;
36     }
37 }``````

————————

Question 1:

You must take ， courses this semester as ， to.

``numCourses``
``0``
``numCourses - 1``

Some prerequisite courses are required before taking some courses. The prerequisite courses are given in the array ， where ， means that ， if you want to learn the course ， you must learn the course first.

``prerequisites``
``prerequisites[i] = [ai, bi]``
``ai``
``bi``
• For example, the prerequisite course pair [0, 1] indicates that if you want to learn course {0, you need to complete course} 1 first.

Please judge whether it is possible to complete all courses? If possible, return; Otherwise, return.

``true``
``false``

Example 1:

``````输入：numCourses = 2, prerequisites = [[1,0]]

Example 2:

``````输入：numCourses = 2, prerequisites = [[1,0],[0,1]]

Tips:

• 1 <= numCourses <= 105
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• prerequisites[i] 中的所有课程对 互不相同
`````` 1 class Solution {
2     boolean[] node;
3     boolean[] visit;
4     boolean hascircle=false;
5     public boolean canFinish(int numCourses, int[][] prerequisites) {
6         List<List<Integer>> list=build(numCourses,prerequisites);
7         node = new boolean[numCourses];
8         visit = new boolean[numCourses];
9         for (int i=0;i<numCourses;i++) {
10             transer(i,list);
11             if (hascircle) return false;
12         }
13         return true;
14     }
15     //转化为邻接表
16     public List<List<Integer>> build(int n,int[][] prerequisites) {
17         List<List<Integer>> list=new ArrayList<>();
18         for (int i=0;i<n;i++) {
19             List<Integer> l=new ArrayList<>();
21         }
22         for (int[] x:prerequisites) {
23             int start=x[0],end=x[1];
25         }
26         return list;
27     }
28
29     public void transer(int x,List<List<Integer>> list) {
30         if (node[x]) {
31             hascircle=true;
32         }
33         if (visit[x]||hascircle) {
34             return;
35         }
36         node[x]=true;
37         //遍历过x节点
38         visit[x]=true;
39         //经过x节点
40         for (int i=0;i<list.get(x).size();i++) {
41             transer(list.get(x).get(i),list);
42         }
43         node[x]=false;
44     }
45 }``````

< strong > idea: for the depth traversal of the graph, use the visit array to record the traversed nodes, and node to record the passed nodes

Question 2:

Now you have a total of ， courses to choose, remember ， to. I’ll give you an array, in which, means that you must # take an elective course before # taking an elective course.

``numCourses``
``0``
``numCourses - 1``
``prerequisites``
``prerequisites[i] = [ai, bi]``
``ai``
``bi``
• For example, to learn course 0, you need to complete course 1 first. We use a match to represent: [0,1].

Return to the learning sequence you arranged to complete all courses. There may be more than one correct order. You just need to return ， any one of them. If it is not possible to complete all courses, an empty array is returned.

Example 1:

``[0,1] 。``

Example 2:

``[0,1,2,3]``
``[0,2,1,3]``

Example 3:

``````输入：numCourses = 1, prerequisites = []

``````
• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= numCourses * (numCourses - 1)
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• ai != bi
• All [AI, Bi] are different from each other
`````` 1 class Solution {
2     int[] in;
3     public int[] findOrder(int numCourses, int[][] prerequisites) {
4         in = new int[numCourses];
5         List<List<Integer>> graph=build(numCourses,prerequisites);
7         for (int i=0;i<numCourses;i++) {
8             if (in[i]==0) queue.offer(i);
9         }
10         int index=0;
11         int[] res=new int[numCourses];
12         while (!queue.isEmpty()) {
13             int temp=queue.poll();
14             res[index++]=temp;
15             for (int x:graph.get(temp)){
16                 in[x]--;
17                 if (in[x]==0) queue.offer(x);
18             }
19         }
20         return index==numCourses?res:new int[]{};
21     }
22
23
24     public List<List<Integer>> build(int n,int[][] prerequisites) {
25          List<List<Integer>> list=new ArrayList<>();
26         for (int i=0;i<n;i++) {
27              List<Integer> l=new ArrayList<>();