Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitdbacdf4

Browse files
committed
add: Course Schedule II
1 parent09b5f38 commitdbacdf4

File tree

3 files changed

+95
-0
lines changed

3 files changed

+95
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -50,6 +50,7 @@ This is the solutions collection of my LeetCode submissions, most of them are pr
5050
|197|[Rising Temperature](https://leetcode.com/problems/rising-temperature/)|[SQL](./src/rising-temperature/res.txt)|Easy|
5151
|206|[Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/)|[JavaScript](./src/reverse-linked-list/res.js)|Easy|
5252
|207|[Course Schedule](https://leetcode.com/problems/course-schedule/)|[JavaScript](./src/course-schedule/res.js)|Medium|
53+
|210|[Course Schedule II](https://leetcode.com/problems/course-schedule-ii/)|[JavaScript](./src/course-schedule-ii/res.js)|Medium|
5354
|240|[Search a 2D Matrix II](https://leetcode.com/problems/search-a-2d-matrix-ii/)|[JavaScript](./src/search-a-2d-matrix-ii/res.js)|Medium|
5455
|307|[Range Sum Query - Mutable](https://leetcode.com/problems/range-sum-query-mutable/)|[JavaScript](./src/range-sum-query-mutable/res.js)|Medium|
5556
|342|[Power of Four](https://leetcode.com/problems/power-of-four/)|[JavaScript](./src/power-of-four/res.js)|Easy|

‎src/course-schedule-ii/res.js

Lines changed: 92 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,92 @@
1+
/**
2+
* res.js
3+
*@authors Joe Jiang (hijiangtao@gmail.com)
4+
*@date 2017-04-17 10:46:36
5+
*
6+
* There are a total of n courses you have to take, labeled from 0 to n - 1.
7+
*
8+
* Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
9+
*
10+
* Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
11+
*
12+
* For example:
13+
*
14+
* 2, [[1,0]]
15+
* There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
16+
*
17+
* 4, [[1,0],[2,0],[3,1],[3,2]]
18+
* There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].
19+
*
20+
* Tips: Otherwise, you should return []
21+
*
22+
*@param {number} numCourses
23+
*@param {number[][]} prerequisites
24+
*@return {number[]}
25+
*/
26+
letfindOrder=function(numCourses,prerequisites){
27+
letprelen=prerequisites.length,
28+
maxNoCircle=numCourses*(numCourses-1)/2;
29+
// 当所有点都有边连接时, 最大的无环边数
30+
if(prelen>maxNoCircle){
31+
return[];
32+
}
33+
34+
letqueue=[],// 存储 BFS 待访问节点序列
35+
flags=[],// 存储节点是否被访问过的标记
36+
res=[],//结果
37+
nodedegree=newArray(numCourses),// 存储node的连边总数
38+
edges=newArray(numCourses);// 存储连边信息, 每个元素中存储的数组表示自己的后续课程
39+
for(leti=0;i<numCourses;i++){
40+
flags[i]=false;
41+
nodedegree[i]=0;
42+
edges[i]=[];
43+
}
44+
45+
for(leti=0;i<prelen;i++){
46+
letsource=prerequisites[i][0],
47+
target=prerequisites[i][1];
48+
49+
edges[target].push(source);
50+
nodedegree[source]++;
51+
nodedegree[target]++;
52+
}
53+
54+
for(leti=0;i<numCourses;i++){
55+
if(nodedegree[i]===edges[i].length){
56+
queue.push(i);
57+
}
58+
}
59+
60+
if(bfsVisit()){
61+
returnres;
62+
}else{
63+
return[];
64+
}
65+
66+
functionbfsVisit(){
67+
while(queue.length){
68+
letcurrent=queue.shift(),//当前访问节点
69+
elen=edges[current].length;// 边数
70+
71+
res.push(current);
72+
// console.log(current, res);
73+
flags[current]=true;
74+
for(leti=0;i<elen;i++){
75+
lettarget=edges[current][i];
76+
if(flags[target]){
77+
returnfalse;// 有回路,返回 false
78+
}
79+
if(--nodedegree[target]===edges[target].length){
80+
queue.push(target);
81+
}
82+
}
83+
edges[current]=[];
84+
nodedegree[current]-=elen;
85+
}
86+
87+
if(res.length<numCourses){
88+
returnfalse;
89+
}
90+
returntrue;
91+
}
92+
};

‎src/course-schedule/res.js

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,8 @@
22
* res.js
33
*@authors Joe Jiang (hijiangtao@gmail.com)
44
*@date 2017-04-17 00:09:34
5+
*
6+
* Topological sorting: https://en.wikipedia.org/wiki/Topological_sorting
57
*
68
* There are a total of n courses you have to take, labeled from 0 to n - 1.
79
*

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp