Skip to content

Commit 5678fae

Browse files
GeekUniversityGeekUniversity
authored
Merge pull request algorithm001#638 from ajun-victor/master
016_ week_03 homework
2 parents d5226af + 8d4fad9 commit 5678fae

2 files changed

Lines changed: 191 additions & 0 deletions

File tree

‎Week_03/id_16/LeetCode_210_16.java‎

Lines changed: 126 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,126 @@
1+
/**[图][中等]
2+
现在你总共有 n 门课需要选，记为 0 到 n-1。
3+
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
4+
给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。
5+
可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
6+
7+
示例 1:
8+
输入: 2, [[1,0]]
9+
输出: [0,1]
10+
解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
11+
12+
示例 2:
13+
输入: 4, [[1,0],[2,0],[3,1],[3,2]]
14+
输出: [0,1,2,3] or [0,2,1,3]
15+
解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
16+
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
17+
18+
说明:
19+
输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
20+
你可以假定输入的先决条件中没有重复的边。
21+
22+
提示:
23+
1.这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
24+
2.通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。
25+
3.拓扑排序也可以通过 BFS 完成。
26+
*/
27+
28+
/*
29+
思路1：
30+
拓扑排序，BFS：与DFS比需要记录顶点入度
31+
先将边缘列表，转化为邻接表表示图，并记录每个顶点的入度，即学习本门课前需要学习其他的课程数量。
32+
将入度为零的顶点加入结果集中，并将本顶点指向的顶点入度减一，在查找入度为零的顶点，以此循环。
33+
最后如果，结果集能覆盖所有顶点即得解，否则无解。
34+
*/
35+
class Solution {
36+
public int[] findOrder(int numCourses, int[][] prerequisites) {
37+
//用邻接表表示图，并记录每个顶点的入度
38+
LinkedList<Integer>[] neighborList = new LinkedList[numCourses];
39+
int[] indegree = new int[numCourses];
40+
41+
for(int[] pair : prerequisites){
42+
if(neighborList[pair[1]] == null)
43+
neighborList[pair[1]] = new LinkedList<Integer>();
44+
neighborList[pair[1]].add(pair[0]);
45+
indegree[pair[0]]++;
46+
}
47+
48+
//优先学习入度为0的课
49+
int[] res = new int[numCourses];
50+
int cur = 0;
51+
for(int i = 0; i < numCourses; i++){
52+
if(indegree[i] == 0)
53+
res[cur++] = i;
54+
}
55+
56+
for(int j = 0; j < cur; j++){//巧妙的写法:指针cur会随循环不断向后移动
57+
if(neighborList[res[j]] != null){
58+
for(int neb : neighborList[res[j]]){
59+
indegree[neb] -= 1;
60+
if(indegree[neb] == 0)
61+
res[cur++] = neb;
62+
}
63+
}
64+
}
65+
66+
return cur == numCourses ? res : new int[0];
67+
}
68+
}
69+
70+
/*
71+
思路2：
72+
拓扑排序，DFS
73+
先将边缘列表，转化为邻接表表示图，并记录每个顶点的入度，即学习本门课前需要学习其他的课程数量。
74+
将入度为零的顶点加入结果集中，并将本顶点指向的顶点入度减一，在查找入度为零的顶点，以此循环。
75+
最后如果，结果集能覆盖所有顶点即得解，否则无解。
76+
77+
思考：DFS一般需要用到递归，需要将存储数据的容器放在方法外声明，变量才能正常工作。
78+
*/
79+
class Solution {
80+
private LinkedList<Integer>[] neighborList;
81+
private boolean[] isVisited;
82+
private boolean[] onStack; //用来判断成环的栈
83+
private int[] res;
84+
private int cnt;
85+
private boolean hasCycle;
86+
87+
public int[] findOrder(int numCourses, int[][] prerequisites) {
88+
neighborList = new LinkedList[numCourses];
89+
isVisited = new boolean[numCourses];
90+
onStack = new boolean[numCourses];
91+
res = new int[numCourses];
92+
cnt = numCourses - 1;
93+
94+
//用邻接表表示图
95+
for(int[] pair : prerequisites){
96+
if(neighborList[pair[1]] == null)
97+
neighborList[pair[1]] = new LinkedList<Integer>();
98+
neighborList[pair[1]].add(pair[0]);
99+
}
100+
101+
//dfs查找环
102+
for(int node = 0; node < numCourses; node++){
103+
if(!isVisited[node])
104+
dfs(node);
105+
}
106+
107+
return hasCycle ? new int[0] : res;
108+
}
109+
110+
private void dfs(int node){
111+
onStack[node] = true;
112+
isVisited[node] = true;
113+
if(neighborList[node] != null){
114+
for(int neb : neighborList[node]){
115+
if(!isVisited[neb]){
116+
dfs(neb);
117+
}else if(onStack[neb]){
118+
hasCycle = true;
119+
return;
120+
}
121+
}
122+
}
123+
res[cnt--] = node;
124+
onStack[node] = false;
125+
}
126+
}

‎Week_03/id_16/LeetCode_997_16.java‎

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
/**[图][简单]
2+
在一个小镇里，按从 1 到 N 标记了 N 个人。传言称，这些人中有一个是小镇上的秘密法官。
3+
如果小镇的法官真的存在，那么：
4+
小镇的法官不相信任何人。
5+
每个人（除了小镇法官外）都信任小镇的法官。
6+
只有一个人同时满足属性 1 和属性 2 。
7+
给定数组 trust，该数组由信任对 trust[i] = [a, b] 组成，表示标记为 a 的人信任标记为 b 的人。
8+
如果小镇存在秘密法官并且可以确定他的身份，请返回该法官的标记。否则，返回 -1。
9+
10+
示例 1：
11+
输入：N = 2, trust = [[1,2]]
12+
输出：2
13+
14+
示例 2：
15+
输入：N = 3, trust = [[1,3],[2,3]]
16+
输出：3
17+
18+
示例 3：
19+
输入：N = 3, trust = [[1,3],[2,3],[3,1]]
20+
输出：-1
21+
22+
示例 4：
23+
输入：N = 3, trust = [[1,2],[2,3]]
24+
输出：-1
25+
26+
示例 5：
27+
输入：N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
28+
输出：3
29+
30+
提示：
31+
1 <= N <= 1000
32+
trust.length <= 10000
33+
trust[i] 是完全不同的
34+
trust[i][0] != trust[i][1]
35+
1 <= trust[i][0], trust[i][1] <= N
36+
*/
37+
38+
/*
39+
思路1：
40+
每个人看成图的一个顶点，组成有向图，出度是信任别人的人数，入度是被人信任的人数。
41+
由题可知，法官的出度是0，入度是N-1
42+
43+
总结：本题只需要关注每个顶点的出入度即可，不要关注各顶点之间的关系。
44+
*/
45+
class Solution {
46+
public int findJudge(int N, int[][] trust) {
47+
//1.得到每个人的出度和入度
48+
int[][] people = new int[N][2];//int数组默认值为0
49+
int in,out;
50+
for(int[] person : trust){
51+
out = person[0];
52+
in = person[1];
53+
people[out-1][0]++;//出度+1
54+
people[in-1][1]++;//入度+1
55+
}
56+
57+
//2.找到出度为0，入度为N-1的人
58+
for(int i = 0; i < N; i++){
59+
if(people[i][0] == 0 && people[i][1] == N-1){//符合条件的人必然不多于1个
60+
return i + 1;
61+
}
62+
}
63+
return -1;
64+
}
65+
}

0 commit comments

Comments
 (0)