南昌做网站优化,网站中弹出广告怎么做的,知名响应式网站企业,视频广告网站题目#xff1a;
现在你总共有 numCourses 门课需要选#xff0c;记为 0 到 numCourses - 1。给你一个数组 prerequisites #xff0c;其中 prerequisites[i] [ai, bi] #xff0c;表示在选修课程 ai 前 必须 先选修 bi 。
例如#xff0c;想要学习课程 0 #xff0c;…题目
现在你总共有 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]
提示 1 numCourses 2000 0 prerequisites.length numCourses * (numCourses - 1) prerequisites[i].length 2 0 ai, bi numCourses ai ! bi 所有[ai, bi] 互不相同
java代码
class Solution {// 存储有向图ListListInteger edges;// 标记每个节点的状态0未搜索1搜索中2已完成int[] visited;// 用数组来模拟栈下标 n-1 为栈底0 为栈顶int[] result;// 判断有向图中是否有环boolean valid true;// 栈下标int index;public int[] findOrder(int numCourses, int[][] prerequisites) {edges new ArrayListListInteger();for (int i 0; i numCourses; i) {edges.add(new ArrayListInteger());}visited new int[numCourses];result new int[numCourses];index numCourses - 1;for (int[] info : prerequisites) {edges.get(info[1]).add(info[0]);}// 每次挑选一个「未搜索」的节点开始进行深度优先搜索for (int i 0; i numCourses valid; i) {if (visited[i] 0) {dfs(i);}}if (!valid) {return new int[0];}// 如果没有环那么就有拓扑排序return result;}public void dfs(int u) {// 将节点标记为「搜索中」visited[u] 1;// 搜索其相邻节点// 只要发现有环立刻停止搜索for (int v: edges.get(u)) {// 如果「未搜索」那么搜索相邻节点if (visited[v] 0) {dfs(v);if (!valid) {return;}}// 如果「搜索中」说明找到了环else if (visited[v] 1) {valid false;return;}}// 将节点标记为「已完成」visited[u] 2;// 将节点入栈result[index--] u;}
}
