作者热门文章
- 使用 Spring Initializr 创建 Spring Boot 应用程序
- 在Spring Boot中配置Cassandra
- 在 Spring Boot 上配置 Tomcat 连接池
- 将Camel消息路由到嵌入WildFly的Artemis上
一、题目
你这个学期必须选修 numCourses 门课程,记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出,其中 prerequisites[i] = [ai, bi] ,表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如,先修课程对 [0, 1] 表示:想要学习课程 0 ,你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习?如果可以,返回 true ;否则,返回 false 。
二、示例
输入:numCourses = 2, prerequisites = [[1,0]]
输出:true
解释:总共有 2 门课程。学习课程 1 之前,你需要完成课程 0 。这是可能的。
输入:numCourses = 2, prerequisites = [[1,0],[0,1]]
输出:false
解释:总共有 2 门课程。学习课程 1 之前,你需要先完成课程 0 ;并且学习课程 0 之前,你还应先完成课程 1 。这是不可能的。
三、思路
如上图所示为例:我们可以看到3依赖着0和1, 4依赖着1和2,5依赖着3和4。此时我们应该先建立一个数组来表示整个的依赖情况。并且使用map数据结构将依赖1的元素放在一起,将依赖2的元素放在一起,然后使用队列将不存在依赖关系的全部放在队列中。然后当队列中存在值的时候进行while循环。
四、代码
/**
* @param {number} numCourses
* @param {number[][]} prerequisites
* @return {boolean}
*/
var canFinish = function (numCourses, prerequisites) {
let arr = new Array(numCourses).fill(0)
let map = new Map()
let length = prerequisites.length
for (let i = 0; i < length; i++) {
arr[prerequisites[i][0]]++
if (map.has(prerequisites[i][1])) {
map.get(prerequisites[i][1]).push(prerequisites[i][0])
} else {
map.set(prerequisites[i][1], [prerequisites[i][0]])
}
}
//获取全部不需要依赖其他课程的
const queue = []
for (let i = 0; i < arr.length; i++) {
if (arr[i] === 0) {
queue.push(i)
}
}
let count = 0
while (queue.length) {
let cur = map.get(queue.shift())
count++
if (cur && cur.length) {
for (let i = 0; i < cur.length; i++) {
arr[cur[i]]--
if (arr[cur[i]] === 0) {
queue.push(cur[i])
}
}
}
}
return count === numCourses
};
五、总结
一、题目 你这个学期必须选修 numCourses 门课程,记为 0 到 numCourses - 1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出,其
题目地址: https://leetcode.com/problems/course-schedule/description/ 题目描述: There are a total of n cour
题目地址:https://leetcode-cn.com/problems/course-schedule-iv/ 题目描述 你总共需要上 n 门课,课程编号依次为 0 到 n-1 。 有的课会
题目地址:https://leetcode.com/problems/course-schedule-ii/description/ 题目描述 There are a total of n cou
我是一名优秀的程序员,十分优秀!