FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
algorithm/Week_03/id_108/LeetCode_210_108.java at master · feixiangcode/algorithm · GitHub
feixiangcode
/
algorithm
Public
forked from
algorithm001/algorithm
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
algorithm
/
Week_03
/
id_108
/
LeetCode_210_108.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
86 lines (80 loc) · 2.73 KB
Breadcrumbs
algorithm
/
Week_03
/
id_108
/
LeetCode_210_108.java
Copy path
File metadata and controls
86 lines (80 loc) · 2.73 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
import
java
.
util
.
ArrayList
;
import
java
.
util
.
LinkedList
;
import
java
.
util
.
List
;
import
java
.
util
.
Queue
;
/**
* @author zhangruihao.zhang
* @version v1.0.0
* @since 2019/05/04
*/
public
class
LeetCode_210_108
{
class
Solution
{
//拓扑排序、广度优先遍历
public
int
[]
findOrder
(
int
numCourses
,
int
[][]
prerequisites
) {
int
[][]
matrix
=
markMatrix
(
numCourses
,
prerequisites
);
int
[]
inDegree
=
inDegree
(
numCourses
,
prerequisites
);
List
<
Integer
>
starts
=
new
ArrayList
<>();
for
(
int
i
=
0
;
i
<
inDegree
.
length
;
i
++) {
if
(
inDegree
[
i
] ==
0
) {
starts
.
add
(
i
);
}
}
if
(
starts
.
isEmpty
()) {
return
new
int
[]{};
}
return
bfs
(
matrix
,
inDegree
,
starts
);
}
private
int
[]
bfs
(
int
[][]
matrix
,
int
[]
inDegree
,
List
<
Integer
>
starts
) {
Queue
<
Integer
>
queue
=
new
LinkedList
<>();
Queue
<
Integer
>
result
=
new
LinkedList
<>();
queue
.
addAll
(
starts
);
while
(!
queue
.
isEmpty
()){
Integer
poll
=
queue
.
poll
();
if
(
result
.
contains
(
poll
)){
return
new
int
[]{};
}
result
.
offer
(
poll
);
List
<
Integer
>
destinations
=
destinations
(
matrix
,
poll
);
destinations
.
forEach
(
i
->{
if
((--
inDegree
[
i
]) ==
0
){
queue
.
offer
(
i
);
}
});
}
if
(
result
.
size
() !=
matrix
.
length
){
return
new
int
[]{};
}
int
[]
orderArr
=
new
int
[
matrix
.
length
];
for
(
int
i
=
0
;
i
<
orderArr
.
length
;
i
++) {
orderArr
[
i
] =
result
.
poll
();
}
return
orderArr
;
}
private
List
<
Integer
>
destinations
(
int
[][]
matrix
,
int
start
){
List
<
Integer
>
list
=
new
ArrayList
<>();
for
(
int
i
=
0
;
i
<
matrix
[
start
].
length
;
i
++) {
if
(
matrix
[
start
][
i
] ==
1
){
list
.
add
(
i
);
}
}
return
list
;
}
private
int
[][]
markMatrix
(
int
N
,
int
[][]
trust
) {
int
[][]
matrix
=
new
int
[
N
][
N
];
for
(
int
i
=
0
;
i
<
trust
.
length
;
i
++) {
int
x
=
trust
[
i
][
1
];
int
y
=
trust
[
i
][
0
];
matrix
[
x
][
y
] =
1
;
}
return
matrix
;
}
private
int
[]
inDegree
(
int
N
,
int
[][]
trust
) {
int
[]
inDegree
=
new
int
[
N
];
for
(
int
i
=
0
;
i
<
trust
.
length
;
i
++) {
int
x
=
trust
[
i
][
0
];
inDegree
[
x
] =
inDegree
[
x
] +
1
;
}
return
inDegree
;
}
}
}
Back
|
FazBrowse Home
|
New Git URL