题目:
现在你总共有 numCourses
门课需要选,记为 0
到 numCourses - 1
。给你一个数组 prerequisites
,其中 prerequisites[i] = [ai, bi]
,表示在选修课程 ai
前 必须 先选修 bi
。
- 例如,想要学习课程
0
,你需要先完成课程1
,我们用一个匹配来表示:[0,1]
。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序,你只要返回 任意一种 就可以了。如果不可能完成所有课程,返回 一个空数组 。
示例:
示例 1:
输入:numCourses = 2, prerequisites = [[1,0]]
输出:[0,1]
解释:总共有 2 门课程。要学习课程 1,你需要先完成课程 0。因此,正确的课程顺序为 [0,1] 。
示例 2:
输入:numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] 输出:[0,2,1,3] 解释:总共有 4 门课程。要学习课程 3,你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。 因此,一个正确的课程顺序是[0,1,2,3]
。另一个正确的排序是[0,2,1,3]
。
示例 3:
输入:numCourses = 1, prerequisites = [] 输出:[0]
思路:
利用列表和栈等数据结构,通过深度优先遍历就行排列优先级。具体代码如下。文章来源:https://www.toymoban.com/news/detail-706664.html
代码:文章来源地址https://www.toymoban.com/news/detail-706664.html
class Solution {
private List<Integer>[] list;
private boolean isValid = true;
private int[] visited;
public int[] findOrder(int numCourses, int[][] prerequisites) {
visited = new int[numCourses];
Stack<Integer> stack = new Stack<>();
list = new ArrayList[numCourses];
for(int i = 0; i <numCourses; i++){
list[i] = new ArrayList<>();
}
for(int[] arr: prerequisites){
list[arr[1]].add(arr[0]);
}
//讲数据加入栈中
for(int i = 0; i < numCourses&&isValid;i++){
if(visited[i] == 0) dfs(i,stack);
}
if(!isValid){
return new int[]{};
}
int[] ans = new int[numCourses];
int i = 0;
while(!stack.isEmpty()){
ans[i++] = stack.pop();
}
return ans;
}
private void dfs(Integer node,Stack<Integer> stack){
visited[node] = -1;
List<Integer> templist = list[node];
for(Integer s: templist){
//没有访问过的节点
if(visited[s] == 0){
dfs(s,stack);
//存在环形,直接返回
} else if(visited[s] == -1){
isValid = false;
return;
}
}
//成功访问
visited[node] = 1;
stack.push(node);
}
}
到了这里,关于java实现课程表 II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!