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

Commit76c96b9

Browse files
committed
210 (1) BFS version solution
1 parente47947e commit76c96b9

File tree

4 files changed

+241
-2
lines changed

4 files changed

+241
-2
lines changed
Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
/**
2+
***************************************************************************
3+
* Description:
4+
*
5+
* There are a total of n courses you have to take, labeled from 0 to n - 1.
6+
*
7+
* Some courses may have prerequisites, for example to take course 0 you have
8+
* 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, return
11+
* the ordering of courses you should take to finish all courses.
12+
*
13+
* There may be multiple correct orders, you just need to return one of them.
14+
* If it is impossible to finish all courses, return an empty array.
15+
*
16+
17+
*
18+
* For example: 2, [[1,0]]
19+
* There are a total of 2 courses to take. To take course 1 you should have
20+
* finished course 0. So the correct course order is [0,1]
21+
*
22+
* 4, [[1,0],[2,0],[3,1],[3,2]]
23+
* There are a total of 4 courses to take. To take course 3 you should have
24+
* finished both courses 1 and 2. Both courses 1 and 2 should be taken after
25+
* you finished course 0. So one correct course order is [0,1,2,3].
26+
* Another correct ordering is[0,2,1,3].
27+
*
28+
* Note: The input prerequisites is a graph represented by a list of edges,
29+
* not adjacency matrices. Read more about how a graph is represented.
30+
*
31+
***************************************************************************
32+
* @tag : Breadth-first Search; Depth-first Search; Graph; Topological Sort
33+
* {@link https://leetcode.com/problems/course-schedule-ii/ }
34+
*/
35+
package_210_CourseScheduleII;
36+
37+
/** see test {@link _210_CourseScheduleII.PracticeTest } */
38+
publicclassPractice {
39+
40+
publicint[]findOrder(intnumCourses,int[][]prerequisites) {
41+
// TODO Auto-generated method stub
42+
returnnull;
43+
}
44+
45+
46+
}

‎src/_210_CourseScheduleII/Solution.java

Lines changed: 27 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,36 @@
11
/**
22
* Time : O() ; Space: O()
3-
* @tag :
3+
* @tag :Breadth-first Search; Depth-first Search; Graph; Topological Sort
44
* @by : Steven Cooks
55
* @date: Sep 14, 2015
66
***************************************************************************
77
* Description:
8-
*
8+
*
9+
* There are a total of n courses you have to take, labeled from 0 to n - 1.
10+
*
11+
* Some courses may have prerequisites, for example to take course 0 you have
12+
* to first take course 1, which is expressed as a pair: [0,1]
13+
*
14+
* Given the total number of courses and a list of prerequisite pairs, return
15+
* the ordering of courses you should take to finish all courses.
16+
*
17+
* There may be multiple correct orders, you just need to return one of them.
18+
* If it is impossible to finish all courses, return an empty array.
19+
*
20+
21+
*
22+
* For example: 2, [[1,0]]
23+
* There are a total of 2 courses to take. To take course 1 you should have
24+
* finished course 0. So the correct course order is [0,1]
25+
*
26+
* 4, [[1,0],[2,0],[3,1],[3,2]]
27+
* There are a total of 4 courses to take. To take course 3 you should have
28+
* finished both courses 1 and 2. Both courses 1 and 2 should be taken after
29+
* you finished course 0. So one correct course order is [0,1,2,3].
30+
* Another correct ordering is[0,2,1,3].
31+
*
32+
* Note: The input prerequisites is a graph represented by a list of edges,
33+
* not adjacency matrices. Read more about how a graph is represented.
934
*
1035
***************************************************************************
1136
* {@link https://leetcode.com/problems/course-schedule-ii/ }
Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
package_210_CourseScheduleII;
2+
3+
importstaticorg.junit.Assert.*;
4+
5+
importjava.util.ArrayList;
6+
importjava.util.Arrays;
7+
importjava.util.HashSet;
8+
importjava.util.List;
9+
importjava.util.Set;
10+
11+
importorg.junit.After;
12+
importorg.junit.Before;
13+
importorg.junit.Rule;
14+
importorg.junit.Test;
15+
importorg.junit.rules.Timeout;
16+
17+
publicclassPracticeTest {
18+
19+
/** Test method for {@link _210_CourseScheduleII.Practice } */
20+
Practicesolution;
21+
22+
@Rule
23+
publicTimeoutglobalTimeout =newTimeout(200);
24+
25+
@Before
26+
publicvoidsetUp()throwsException {
27+
solution =newPractice();
28+
}
29+
30+
@After
31+
publicvoidtearDown()throwsException {
32+
solution =null;
33+
}
34+
35+
@Test
36+
publicvoidTest1() {
37+
intnumCourses =2;
38+
int[][]prerequisites = {
39+
{1,0 }
40+
};
41+
int[]actuals =solution.findOrder(numCourses,prerequisites);
42+
int[]expecteds = {0,1 };
43+
assertArrayEquals(expecteds,actuals);
44+
}
45+
46+
@Test
47+
publicvoidTest2() {
48+
intnumCourses =4;
49+
int[][]prerequisites = {
50+
{1,0 },
51+
{2,0 },
52+
{3,1 },
53+
{3,2 }
54+
};
55+
int[]actuals =solution.findOrder(numCourses,prerequisites);
56+
List<Integer>actual =toList(actuals);
57+
Set<List<Integer>>expecteds =newHashSet<>();
58+
expecteds.add(Arrays.asList(0,1,2,3));
59+
expecteds.add(Arrays.asList(0,2,1,3));
60+
assertTrue(expecteds.contains(actual));
61+
}
62+
63+
@Test
64+
publicvoidTest3() {
65+
intnumCourses =3;
66+
int[][]prerequisites = {
67+
{1,0 },
68+
{2,1 },
69+
{0,2 },
70+
};
71+
int[]actuals =solution.findOrder(numCourses,prerequisites);
72+
int[]expecteds = { };
73+
assertArrayEquals(expecteds,actuals);
74+
}
75+
76+
privateList<Integer>toList(int[]nums) {
77+
List<Integer>res =newArrayList<>();
78+
for (intnum :nums) {
79+
res.add(num);
80+
}
81+
returnres;
82+
}
83+
84+
}
Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
package_210_CourseScheduleII;
2+
3+
importstaticorg.junit.Assert.*;
4+
5+
importjava.util.ArrayList;
6+
importjava.util.Arrays;
7+
importjava.util.HashSet;
8+
importjava.util.List;
9+
importjava.util.Set;
10+
11+
importorg.junit.After;
12+
importorg.junit.Before;
13+
importorg.junit.Rule;
14+
importorg.junit.Test;
15+
importorg.junit.rules.Timeout;
16+
17+
publicclassSolutionTest {
18+
19+
/** Test method for {@link _210_CourseScheduleII.Solution } */
20+
Solutionsolution;
21+
22+
@Rule
23+
publicTimeoutglobalTimeout =newTimeout(200);
24+
25+
@Before
26+
publicvoidsetUp()throwsException {
27+
solution =newSolution();
28+
}
29+
30+
@After
31+
publicvoidtearDown()throwsException {
32+
solution =null;
33+
}
34+
35+
@Test
36+
publicvoidTest1() {
37+
intnumCourses =2;
38+
int[][]prerequisites = {
39+
{1,0 }
40+
};
41+
int[]actuals =solution.findOrder(numCourses,prerequisites);
42+
int[]expecteds = {0,1 };
43+
assertArrayEquals(expecteds,actuals);
44+
}
45+
46+
@Test
47+
publicvoidTest2() {
48+
intnumCourses =4;
49+
int[][]prerequisites = {
50+
{1,0 },
51+
{2,0 },
52+
{3,1 },
53+
{3,2 }
54+
};
55+
int[]actuals =solution.findOrder(numCourses,prerequisites);
56+
List<Integer>actual =toList(actuals);
57+
Set<List<Integer>>expecteds =newHashSet<>();
58+
expecteds.add(Arrays.asList(0,1,2,3));
59+
expecteds.add(Arrays.asList(0,2,1,3));
60+
assertTrue(expecteds.contains(actual));
61+
}
62+
63+
@Test
64+
publicvoidTest3() {
65+
intnumCourses =3;
66+
int[][]prerequisites = {
67+
{1,0 },
68+
{2,1 },
69+
{0,2 },
70+
};
71+
int[]actuals =solution.findOrder(numCourses,prerequisites);
72+
int[]expecteds = { };
73+
assertArrayEquals(expecteds,actuals);
74+
}
75+
76+
privateList<Integer>toList(int[]nums) {
77+
List<Integer>res =newArrayList<>();
78+
for (intnum :nums) {
79+
res.add(num);
80+
}
81+
returnres;
82+
}
83+
84+
}

0 commit comments

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