Skip to content

Commit 44f3c13

Browse files
GeekUniversityGeekUniversity
authored
Merge pull request algorithm001#622 from yuqiu-pp/master
Week03-006
2 parents bab54b2 + 5a426bb commit 44f3c13

8 files changed

Lines changed: 752 additions & 0 deletions

‎Week_03/id_6/LeetCode_104_6.java‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
2+
3+
// LeetCode 104
4+
5+
// [ 1. DFS ]
6+
7+
8+
// maxDepth = max(left, right) + 1
9+
public int maxDepth(TreeNode root) {
10+
if (root == null){
11+
return 0;
12+
}
13+
14+
int left = maxDepth(root.left);
15+
int right = maxDepth(root.right);
16+
17+
return 1 + Math.max(left, right);
18+
}
19+

‎Week_03/id_6/LeetCode_210_6.java‎

Lines changed: 118 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,118 @@
1+
2+
3+
// LeetCode 210
4+
5+
// [ 2. Kahn 算法. 入度减1在独立的数组上操作 ]
6+
public int[] findOrder(int numCourses, int[][] prerequisites){
7+
// 邻接表--图。 第一个元素是顶点本身
8+
LinkedList<Integer>[] graph = createGraphLink(numCourses, prerequisites);
9+
// 统计顶点的入度
10+
int[] inDegree = new int[numCourses];
11+
for (int i = 0; i < numCourses; i++) {
12+
for (int j = 1; j < graph[i].size(); j++) {
13+
// 链表上包含一次该顶点，就有一个入度
14+
int w = graph[i].get(j);
15+
// 索引即顶点
16+
inDegree[w] ++;
17+
}
18+
}
19+
20+
// 入度为0的顶点入队列
21+
Queue<Integer> queue = new LinkedList<>();
22+
for (int i = 0; i < numCourses; i++) {
23+
if (inDegree[i] == 0){
24+
queue.add(i);
25+
}
26+
}
27+
// 栈，按顺序保存遍历过的顶点(不重复)
28+
Stack<Integer> stack = new Stack<>();
29+
// 去除入度为0的点
30+
while (!queue.isEmpty()){
31+
int m = queue.poll();
32+
stack.push(m);
33+
// 与该点有关的入度 - 1
34+
for (int i = 1; i < graph[m].size(); i++) {
35+
int n = graph[m].get(i);
36+
inDegree[n] --;
37+
if (inDegree[n] == 0){
38+
queue.add(n);
39+
}
40+
}
41+
}
42+
43+
if (stack.size() == numCourses){
44+
int[] rst = new int[stack.size()];
45+
for (int i = 0; !stack.isEmpty(); i++) {
46+
rst[i] = stack.pop();
47+
}
48+
return rst;
49+
}
50+
51+
return new int[0];
52+
}
53+
54+
// [ 1. 逆邻接表. 入度减1在逆邻接表上操作 ]
55+
public int[] findOrder(int numCourses, int[][] prerequisites){
56+
// 逆邻接表--图
57+
LinkedList<Integer>[] graph = createInverseGraphLink(numCourses, prerequisites);
58+
// 栈，按顺序保存遍历过的顶点
59+
Stack<Integer> stack = new Stack<>();
60+
// 散列表，记录点是否被访问过
61+
HashMap<Integer, Integer> map = new HashMap<>();
62+
63+
// 遍历总次数=顶点数，每次选出入度为0的点
64+
for (int i = 0; i < numCourses; i++) {
65+
// 选出入度为0的点
66+
for (LinkedList<Integer> g : graph){
67+
// 入度为0的顶点
68+
if (g.size() == 1){
69+
int n = g.get(0);
70+
stack.push(n);
71+
map.put(n, 1);
72+
// 包含该点的顶点入度都减1
73+
for (LinkedList<Integer> h : graph){
74+
for (int j = 0; j < h.size(); j++) {
75+
if (h.get(j) == n){
76+
h.remove(j);
77+
}
78+
}
79+
}
80+
}
81+
}
82+
}
83+
if (stack.size() == numCourses){
84+
int[] rst = new int[stack.size()];
85+
for (int i = 0; !stack.isEmpty(); i++) {
86+
rst[i] = stack.pop();
87+
}
88+
return rst;
89+
}
90+
91+
return new int[0];
92+
}
93+
94+
95+
// 创建图 逆邻接表存储
96+
public LinkedList<Integer>[] createInverseGraphLink(int num, int[][] src){
97+
LinkedList<Integer>[] graph = new LinkedList[num];
98+
99+
for (int j = 0; j < num; j++){
100+
graph[j] = new LinkedList<>();
101+
graph[j].add(j);
102+
}
103+
104+
int len = src.length;
105+
for (int i = 0; i < len; i++) {
106+
// [0,1] 1索引
107+
// 逆邻接表，索引是前序课程
108+
int p = src[i][1];
109+
int q = src[i][0];
110+
graph[p].add(q);
111+
}
112+
113+
return graph;
114+
}
115+
116+
117+
118+

‎Week_03/id_6/LeetCode_310_6.java‎

Lines changed: 160 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,160 @@
1+
2+
3+
// LeetCode 310
4+
5+
// [2. 广度优先遍历 ]
6+
// 叶子节点做root，必然不会是最小高度树
7+
// 一次一次的删除叶子节点，直到最后剩余1或2个点
8+
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
9+
List<Integer> rst = new ArrayList<>();
10+
if (n == 0) {
11+
return rst;
12+
}
13+
if (n == 1) {
14+
rst.add(0);
15+
return rst;
16+
}
17+
if (n == 2) {
18+
rst.add(0);
19+
rst.add(1);
20+
return rst;
21+
}
22+
23+
// 邻接矩阵表示的无向图
24+
LinkedList<Integer>[] graph = createGraphLink(n, edges);
25+
26+
List<Integer> currList = new ArrayList<>();
27+
// 记录删除叶子节点后剩余的节点，map.size<=2作为循环结束条件
28+
HashMap<Integer,Integer> map = new HashMap<>();
29+
// 顶点度值表. 索引作为顶点
30+
int[] inDegree = new int[n];
31+
for (int i = 0; i < n; i++) {
32+
inDegree[i] = graph[i].size();
33+
map.put(i, 1);
34+
// 度为1的点入队
35+
if (inDegree[i] == 1){
36+
currList.add(i);
37+
}
38+
}
39+
40+
// 删除叶子节点
41+
while (currList.size() > 0) {
42+
List<Integer> nextList = new ArrayList<>();
43+
for (Integer nd : currList){
44+
map.remove(nd);
45+
for (int j : graph[nd]){
46+
inDegree[j] --;
47+
if (inDegree[j] == 1){
48+
nextList.add(j);
49+
50+
}
51+
}
52+
53+
}
54+
if (map.size() <= 2){
55+
break;
56+
}
57+
currList = nextList;
58+
}
59+
60+
for (int k : map.keySet()){
61+
rst.add(k);
62+
}
63+
return rst;
64+
}
65+
66+
67+
// [1. 广度优先遍历 BFS ] 超时
68+
// 题目要求的是，整棵树有最小高度，然后返回根节点
69+
// 相当于求树的最大高度，然后选最小的情况时的root
70+
// 让每一个顶点做root，求出最大高度
71+
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
72+
List<Integer> rst = new ArrayList<>();
73+
if (n == 0) {
74+
return rst;
75+
}
76+
if (n == 1) {
77+
rst.add(0);
78+
return rst;
79+
}
80+
81+
// 邻接矩阵表示的无向图
82+
LinkedList<Integer>[] graph = createGraphLink(n, edges);
83+
84+
int[] hashMap = new int[n];
85+
// 已找到的最小深度
86+
int minDeep = 0;
87+
// 每个顶点i做为root广度遍历，找出最大深度
88+
for (int i = 0; i < n; i++) {
89+
// 记录已经访问的点
90+
HashMap<Integer, Integer> map = new HashMap<>();
91+
int deep = 0;
92+
93+
List<Integer> currLayer = new ArrayList<>();
94+
currLayer.add(i);
95+
map.put(i, 1);
96+
97+
while (currLayer.size() > 0){
98+
List<Integer> nextLayer = new ArrayList<>();
99+
for (int curr : currLayer){
100+
// 当前点的link
101+
List<Integer> tmp = new ArrayList<>(graph[curr].size());
102+
for (int nd : graph[curr]){
103+
if (!map.containsKey(nd)){
104+
map.put(nd, 1);
105+
tmp.add(nd);
106+
nextLayer.add(nd);
107+
}
108+
}
109+
}
110+
currLayer = nextLayer;
111+
deep ++;
112+
// 优化：如果已经大于当前的最小高度，不再遍历
113+
if (deep > minDeep && minDeep != 0){
114+
break;
115+
}
116+
}
117+
hashMap[i] = deep;
118+
if (minDeep == 0){
119+
minDeep = deep;
120+
}else {
121+
if (deep < minDeep){
122+
minDeep = deep;
123+
}
124+
}
125+
}
126+
127+
int len = hashMap.length;
128+
for (int i = 0; i < len; i ++){
129+
if (hashMap[i] == minDeep){
130+
rst.add(i);
131+
}
132+
}
133+
134+
return rst;
135+
}
136+
137+
138+
// 创建图 邻接表存储
139+
public LinkedList<Integer>[] createGraphLink(int num, int[][] src){
140+
LinkedList<Integer>[] graph = new LinkedList[num];
141+
142+
for (int i = 0; i < num; i++){
143+
graph[i] = new LinkedList<>();
144+
// graph[i].add(i);
145+
}
146+
147+
int len = src.length;
148+
// 无向图
149+
for (int i = 0; i < len; i++) {
150+
// [0,1]
151+
int p = src[i][0];
152+
int q = src[i][1];
153+
graph[p].add(q);
154+
graph[q].add(p);
155+
}
156+
157+
return graph;
158+
}
159+
160+

0 commit comments

Comments
 (0)