Skip to content

Commit e2b71d4

Browse files
dunwudunwu
committed
feat: leetcode 刷题
1 parent 7b0e42a commit e2b71d4

59 files changed

Lines changed: 1479 additions & 1435 deletions

File tree

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎README.md‎

Lines changed: 120 additions & 94 deletions
Large diffs are not rendered by default.

codes/algorithm/src/main/java/io/github/dunwu/algorithm/graph/所有可能的路径.java renamed to codes/algorithm/src/main/java/io/github/dunwu/algorithm/graph/dfs/所有可能的路径.java

Lines changed: 16 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,6 @@
1-
package io.github.dunwu.algorithm.graph;
1+
package io.github.dunwu.algorithm.graph.dfs;
22

3+
import cn.hutool.core.collection.CollectionUtil;
34
import org.junit.jupiter.api.Assertions;
45

56
import java.util.Arrays;
@@ -26,36 +27,40 @@ public static void main(String[] args) {
2627
for (int i = 0; i < expect.size(); i++) {
2728
Assertions.assertArrayEquals(expect.get(i).toArray(), output.get(i).toArray());
2829
}
29-
System.out.println("v = " + output);
30+
// System.out.println("v = " + output);
3031
}
3132

3233
static class Solution {
33-
34-
LinkedList<List<Integer>> res = new LinkedList<>();
34+
// 记录所有路径
35+
List<List<Integer>> res = new LinkedList<>();
3536
LinkedList<Integer> path = new LinkedList<>();
3637

3738
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
38-
if (graph == null || graph.length == 0) return res;
39-
traverse(graph, 0);
39+
dfs(graph, 0);
4040
return res;
4141
}
4242

43-
void traverse(int[][] graph, int s) {
43+
// 图的遍历框架
44+
void dfs(int[][] graph, int s) {
4445

45-
// 前序
46+
// 添加节点 s 到路径
4647
path.addLast(s);
4748

48-
if (s == graph.length - 1) {
49+
int n = graph.length;
50+
if (s == n - 1) {
51+
// 到达终点
52+
System.out.println("find path: " + CollectionUtil.join(path, "->"));
4953
res.add(new LinkedList<>(path));
5054
path.removeLast();
5155
return;
5256
}
5357

58+
// 递归每个相邻节点
5459
for (int v : graph[s]) {
55-
traverse(graph, v);
60+
dfs(graph, v);
5661
}
5762

58-
// 后序
63+
// 从路径移出节点 s
5964
path.removeLast();
6065
}
6166

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/graph/template/DFS遍历图的所有节点.java‎

Lines changed: 10 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -15,13 +15,9 @@ public class DFS遍历图的所有节点 {
1515
// 遍历图的所有节点
1616
void traverse(Graph graph, int s, boolean[] visited) {
1717
// base case
18-
if (s < 0 || s >= graph.size()) {
19-
return;
20-
}
21-
if (visited[s]) {
22-
// 防止死循环
23-
return;
24-
}
18+
if (s < 0 || s >= graph.size()) { return; }
19+
// 防止死循环
20+
if (visited[s]) { return; }
2521
// 前序位置
2622
visited[s] = true;
2723
System.out.println("visit " + s);
@@ -34,19 +30,15 @@ void traverse(Graph graph, int s, boolean[] visited) {
3430
// 图的遍历框架
3531
// 需要一个 visited 数组记录被遍历过的节点
3632
// 避免走回头路陷入死循环
37-
void traverse(Vertex s, boolean[] visited) {
33+
void traverse(Vertex v, boolean[] visited) {
3834
// base case
39-
if (s == null) {
40-
return;
41-
}
42-
if (visited[s.id]) {
43-
// 防止死循环
44-
return;
45-
}
35+
if (v == null) { return; }
36+
// 防止死循环
37+
if (visited[v.id]) { return; }
4638
// 前序位置
47-
visited[s.id] = true;
48-
System.out.println("visit " + s.id);
49-
for (Vertex neighbor : s.neighbors) {
39+
visited[v.id] = true;
40+
System.out.println("visit " + v.id);
41+
for (Vertex neighbor : v.neighbors) {
5042
traverse(neighbor, visited);
5143
}
5244
// 后序位置

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/graph/template/DFS遍历图的所有路径.java‎

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
package io.github.dunwu.algorithm.graph.template;
2+
3+
import io.github.dunwu.algorithm.graph.Edge;
4+
import io.github.dunwu.algorithm.graph.Graph;
5+
import io.github.dunwu.algorithm.tree.Node;
6+
7+
import java.util.LinkedList;
8+
9+
/**
10+
* DFS遍历图的所有路径
11+
*
12+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
13+
* @date 2025-12-02
14+
*/
15+
public class DFS遍历图的所有路径 {
16+
17+
// onPath 和 path 记录当前递归路径上的节点
18+
boolean[] onPath = null;
19+
// 多叉树的遍历框架，寻找从根节点到目标节点的路径
20+
LinkedList<String> path = new LinkedList<>();
21+
22+
void traverse(Node root, Node targetNode) {
23+
// base case
24+
if (root == null) {
25+
return;
26+
}
27+
if (root.val == targetNode.val) {
28+
// 找到目标节点
29+
System.out.println("find path: " + String.join("->", path) + "->" + targetNode);
30+
return;
31+
}
32+
// 前序位置
33+
path.addLast(String.valueOf(root.val));
34+
for (Node child : root.children) {
35+
traverse(child, targetNode);
36+
}
37+
// 后序位置
38+
path.removeLast();
39+
}
40+
41+
void traverse(Graph graph, int from, int to) {
42+
if (onPath == null) { onPath = new boolean[graph.size()]; }
43+
// base case
44+
if (from < 0 || from >= graph.size()) { return; }
45+
// 防止死循环（成环）
46+
if (onPath[from]) { return; }
47+
if (from == to) {
48+
// 找到目标节点
49+
System.out.println("find path: " + String.join("->", path) + "->" + to);
50+
return;
51+
}
52+
53+
// 前序位置
54+
onPath[from] = true;
55+
path.add(String.valueOf(from));
56+
for (Edge e : graph.neighbors(from)) {
57+
traverse(graph, e.to, to);
58+
}
59+
// 后序位置
60+
path.remove(path.size() - 1);
61+
onPath[from] = false;
62+
}
63+
64+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/graph/template/DFS遍历图的所有边.java‎

Lines changed: 24 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,7 @@
11
package io.github.dunwu.algorithm.graph.template;
22

3+
import io.github.dunwu.algorithm.graph.Edge;
4+
import io.github.dunwu.algorithm.graph.Graph;
35
import io.github.dunwu.algorithm.graph.Vertex;
46
import io.github.dunwu.algorithm.tree.Node;
57

@@ -14,32 +16,40 @@ public class DFS遍历图的所有边 {
1416
// 遍历多叉树的树枝
1517
void traverseBranch(Node root) {
1618
// base case
17-
if (root == null) {
18-
return;
19-
}
19+
if (root == null) { return; }
2020
for (Node child : root.children) {
2121
System.out.println("visit branch: " + root.val + " -> " + child.val);
2222
traverseBranch(child);
2323
}
2424
}
2525

2626
// 遍历图的边
27-
// 需要一个二维 visited 数组记录被遍历过的边，visited[u][v] 表示边 u->v 已经被遍历过
28-
void traverseEdges(Vertex s, boolean[][] visited) {
27+
// 需要一个二维 visited 数组记录被遍历过的边，visited[from][to] 表示边 from->to 已经被遍历过
28+
void traverseEdges(Vertex v, boolean[][] visited) {
2929
// base case
30-
if (s == null) {
31-
return;
32-
}
33-
for (Vertex neighbor : s.neighbors) {
30+
if (v == null) { return; }
31+
for (Vertex neighbor : v.neighbors) {
3432
// 如果边已经被遍历过，则跳过
35-
if (visited[s.id][neighbor.id]) {
36-
continue;
37-
}
33+
if (visited[v.id][neighbor.id]) { continue; }
3834
// 标记并访问边
39-
visited[s.id][neighbor.id] = true;
40-
System.out.println("visit edge: " + s.id + " -> " + neighbor.id);
35+
visited[v.id][neighbor.id] = true;
36+
System.out.println("visit edge: " + v.id + " -> " + neighbor.id);
4137
traverseEdges(neighbor, visited);
4238
}
4339
}
4440

41+
// 从起点 s 开始遍历图的所有边
42+
void traverseEdges(Graph graph, int s, boolean[][] visited) {
43+
// base case
44+
if (s < 0 || s >= graph.size()) { return; }
45+
for (Edge e : graph.neighbors(s)) {
46+
// 如果边已经被遍历过，则跳过
47+
if (visited[s][e.to]) { continue; }
48+
// 标记并访问边
49+
visited[s][e.to] = true;
50+
System.out.println("visit edge: " + s + " -> " + e.to);
51+
traverseEdges(graph, e.to, visited);
52+
}
53+
}
54+
4555
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/graph/template/邻接矩阵实现图.java‎

Lines changed: 20 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -13,26 +13,6 @@
1313
*/
1414
public class 邻接矩阵实现图 {
1515

16-
public static void main(String[] args) {
17-
WeightedDigraph graph = new WeightedDigraph(3);
18-
graph.addEdge(0, 1, 1);
19-
graph.addEdge(1, 2, 2);
20-
graph.addEdge(2, 0, 3);
21-
graph.addEdge(2, 1, 4);
22-
23-
System.out.println(graph.hasEdge(0, 1)); // true
24-
System.out.println(graph.hasEdge(1, 0)); // false
25-
26-
graph.neighbors(2).forEach(edge -> {
27-
System.out.println(2 + " -> " + edge.to + ", wight: " + edge.weight);
28-
});
29-
// 2 -> 0, wight: 3
30-
// 2 -> 1, wight: 4
31-
32-
graph.removeEdge(0, 1);
33-
System.out.println(graph.hasEdge(0, 1)); // false
34-
} // 存储相邻节点及边的权重
35-
3616
// 加权有向图的通用实现（邻接矩阵）
3717
static class WeightedDigraph {
3818

@@ -75,6 +55,26 @@ public List<Edge> neighbors(int v) {
7555
return res;
7656
}
7757

58+
public static void main(String[] args) {
59+
WeightedDigraph graph = new WeightedDigraph(3);
60+
graph.addEdge(0, 1, 1);
61+
graph.addEdge(1, 2, 2);
62+
graph.addEdge(2, 0, 3);
63+
graph.addEdge(2, 1, 4);
64+
65+
System.out.println(graph.hasEdge(0, 1)); // true
66+
System.out.println(graph.hasEdge(1, 0)); // false
67+
68+
graph.neighbors(2).forEach(edge -> {
69+
System.out.println(2 + " -> " + edge.to + ", wight: " + edge.weight);
70+
});
71+
// 2 -> 0, wight: 3
72+
// 2 -> 1, wight: 4
73+
74+
graph.removeEdge(0, 1);
75+
System.out.println(graph.hasEdge(0, 1)); // false
76+
}
77+
7878
}
7979

8080
// 无向加权图的通用实现

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/graph/topological_sort/课程表.java‎

Lines changed: 92 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,92 @@
1+
package io.github.dunwu.algorithm.graph.topological_sort;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
import java.util.LinkedList;
6+
import java.util.List;
7+
8+
/**
9+
* <a href="https://leetcode.cn/problems/course-schedule/">207. 课程表</a>
10+
*
11+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
12+
* @date 2025-11-03
13+
*/
14+
public class 课程表 {
15+
16+
public static void main(String[] args) {
17+
Solution s = new Solution();
18+
int[][] input = new int[][] { { 1, 0 } };
19+
int[][] input2 = new int[][] { { 1, 0 }, { 0, 1 } };
20+
Assertions.assertTrue(s.canFinish(2, input));
21+
Assertions.assertFalse(s.canFinish(2, input2));
22+
}
23+
24+
static class Solution {
25+
26+
// 记录递归堆栈中的节点
27+
boolean[] onPath;
28+
// 记录节点是否被遍历过
29+
boolean[] visited;
30+
// 记录图中是否有环
31+
boolean hasCycle = false;
32+
33+
public boolean canFinish(int numCourses, int[][] prerequisites) {
34+
List<Integer>[] graph = buildGraph(numCourses, prerequisites);
35+
36+
onPath = new boolean[numCourses];
37+
visited = new boolean[numCourses];
38+
39+
for (int i = 0; i < numCourses; i++) {
40+
// 遍历图中的所有节点
41+
dfs(graph, i);
42+
}
43+
// 只要没有循环依赖可以完成所有课程
44+
return !hasCycle;
45+
}
46+
47+
// 图遍历函数，遍历所有路径
48+
void dfs(List<Integer>[] graph, int s) {
49+
if (hasCycle) {
50+
// 如果已经找到了环，也不用再遍历了
51+
return;
52+
}
53+
54+
if (onPath[s]) {
55+
// s 已经在递归路径上，说明成环了
56+
hasCycle = true;
57+
return;
58+
}
59+
60+
if (visited[s]) {
61+
// 不用再重复遍历已遍历过的节点
62+
return;
63+
}
64+
65+
// 前序代码位置
66+
visited[s] = true;
67+
onPath[s] = true;
68+
for (int t : graph[s]) {
69+
dfs(graph, t);
70+
}
71+
// 后序代码位置
72+
onPath[s] = false;
73+
}
74+
75+
List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
76+
// 图中共有 numCourses 个节点
77+
List<Integer>[] graph = new LinkedList[numCourses];
78+
for (int i = 0; i < numCourses; i++) {
79+
graph[i] = new LinkedList<>();
80+
}
81+
for (int[] edge : prerequisites) {
82+
int from = edge[1], to = edge[0];
83+
// 添加一条从 from 指向 to 的有向边
84+
// 边的方向是「被依赖」关系，即修完课程 from 才能修课程 to
85+
graph[from].add(to);
86+
}
87+
return graph;
88+
}
89+
90+
}
91+
92+
}

0 commit comments

Comments
 (0)