Skip to content

Latest commit

 

History

History
120 lines (84 loc) · 4.93 KB

02.06.02-Exercises.md

File metadata and controls

120 lines (84 loc) · 4.93 KB

02.06.02 练习题目(第 15 天)

1.1 题目大意

描述:给定一个整数 $numCourses$,代表这学期必须选修的课程数量,课程编号为 $0 \sim numCourses - 1$。再给定一个数组 $prerequisites$ 表示先修课程关系,其中 $prerequisites[i] = [ai, bi]$ 表示如果要学习课程 $ai$ 则必须要先完成课程 $bi$

要求:判断是否可能完成所有课程的学习。如果可以,返回 True,否则,返回 False

说明

  • $1 \le numCourses \le 10^5$
  • $0 \le prerequisites.length \le 5000$
  • $prerequisites[i].length == 2$
  • $0 \le ai, bi < numCourses$
  • $prerequisites[i]$ 中所有课程对互不相同。

示例

  • 示例 1:
输入numCourses = 2, prerequisites = [[1,0]]
输出true
解释总共有 2 门课程学习课程 1 之前你需要完成课程 0这是可能的
  • 示例 2:
输入numCourses = 2, prerequisites = [[1,0],[0,1]]
输出false
解释总共有 2 门课程学习课程 1 之前你需要先完成课程 0并且学习课程 0 之前你还应先完成课程 1这是不可能的

2.1 题目大意

描述:给定一个整数 $numCourses$,代表这学期必须选修的课程数量,课程编号为 $0 \sim numCourses - 1$。再给定一个数组 $prerequisites$ 表示先修课程关系,其中 $prerequisites[i] = [ai, bi]$ 表示如果要学习课程 $ai$ 则必须要先完成课程 $bi$

要求:返回学完所有课程所安排的学习顺序。如果有多个正确的顺序,只要返回其中一种即可。如果无法完成所有课程,则返回空数组。

说明

  • $1 \le numCourses \le 2000$
  • $0 \le prerequisites.length \le numCourses \times (numCourses - 1)$
  • $prerequisites[i].length == 2$
  • $0 \le ai, bi < numCourses$
  • $ai \ne bi$
  • 所有$[ai, bi]$ 互不相同。

示例

  • 示例 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.1 题目大意

描述:给定一个有向图 $graph$,其中 $graph[i]$ 是与节点 $i$ 相邻的节点列表,意味着从节点 $i$ 到节点 $graph[i]$ 中的每个节点都有一条有向边。

要求:找出图中所有的安全节点,将其存入数组作为答案返回,答案数组中的元素应当按升序排列。

说明

  • 终端节点:如果一个节点没有连出的有向边,则它是终端节点。或者说,如果没有出边,则节点为终端节点。
  • 安全节点:如果从该节点开始的所有可能路径都通向终端节点,则该节点为安全节点。
  • $n == graph.length$
  • $1 \le n \le 10^4$
  • $0 \le graph[i].length \le n$
  • $0 \le graph[i][j] \le n - 1$
  • $graph[i]$ 按严格递增顺序排列。
  • 图中可能包含自环。
  • 图中边的数目在范围 $[1, 4 \times 10^4]$ 内。

示例

  • 示例 1:

输入graph = [[1,2],[2,3],[5],[0],[5],[],[]]
输出:[2,4,5,6]
解释示意图如上节点 5 和节点 6 是终端节点因为它们都没有出边从节点 245  6 开始的所有路径都指向节点 5  6
  • 示例 2:
输入graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
输出:[4]
解释:
只有节点 4 是终端节点从节点 4 开始的所有路径都通向节点 4

习题解析

  1. 0207. 课程表」习题解析:网页链接Github 链接
  2. 0210. 课程表 II」习题解析:网页链接Github 链接
  3. 0802. 找到最终的安全状态」习题解析:网页链接Github 链接