Skip to content

Commit b85ae2e

Browse files
dunwudunwu
committed
feat: leetcode 刷题
1 parent d9cf07d commit b85ae2e

40 files changed

+1432
-610
lines changed

‎README.md‎

Lines changed: 48 additions & 44 deletions
Large diffs are not rendered by default.

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/bfs/package-info.java‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
/**
2+
* 通过 BFS 解最短路径类型问题
3+
*
4+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
5+
* @date 2025-12-15
6+
*/
7+
package io.github.dunwu.algorithm.bfs;

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/bfs/template/BFS算法模板.java‎

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
package io.github.dunwu.algorithm.bfs.template;
2+
3+
import io.github.dunwu.algorithm.graph.Edge;
4+
import io.github.dunwu.algorithm.graph.Graph;
5+
6+
import java.util.LinkedList;
7+
import java.util.Queue;
8+
9+
/**
10+
* BFS 算法模板
11+
*
12+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
13+
* @date 2025-12-15
14+
*/
15+
public class BFS算法模板 {
16+
17+
private Graph graph;
18+
19+
// 从 s 开始 BFS 遍历图的所有节点，且记录遍历的步数
20+
// 当走到目标节点 target 时，返回步数
21+
int bfs(int s, int target) {
22+
boolean[] visited = new boolean[graph.size()];
23+
Queue<Integer> q = new LinkedList<>();
24+
q.offer(s);
25+
visited[s] = true;
26+
// 记录从 s 开始走到当前节点的步数
27+
int step = 0;
28+
while (!q.isEmpty()) {
29+
int sz = q.size();
30+
for (int i = 0; i < sz; i++) {
31+
int cur = q.poll();
32+
System.out.println("visit " + cur + " at step " + step);
33+
// 判断是否到达终点
34+
if (cur == target) {
35+
return step;
36+
}
37+
// 将邻居节点加入队列，向四周扩散搜索
38+
for (Edge e : graph.neighbors(cur)) {
39+
if (!visited[e.to]) {
40+
q.offer(e.to);
41+
visited[e.to] = true;
42+
}
43+
}
44+
}
45+
step++;
46+
}
47+
// 如果走到这里，说明在图中没有找到目标节点
48+
return -1;
49+
}
50+
51+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/bfs/二进制矩阵中的最短路径.java‎

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
package io.github.dunwu.algorithm.bfs;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
import java.util.LinkedList;
6+
7+
/**
8+
* <a href="https://leetcode.cn/problems/shortest-path-in-binary-matrix/">1091. 二进制矩阵中的最短路径</a>
9+
*
10+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
11+
* @date 2025-12-15
12+
*/
13+
public class 二进制矩阵中的最短路径 {
14+
15+
public static void main(String[] args) {
16+
Solution s = new Solution();
17+
Assertions.assertEquals(2, s.shortestPathBinaryMatrix(new int[][] { { 0, 1 }, { 1, 0 } }));
18+
Assertions.assertEquals(4, s.shortestPathBinaryMatrix(new int[][] { { 0, 0, 0 }, { 1, 1, 0 }, { 1, 1, 0 } }));
19+
Assertions.assertEquals(-1, s.shortestPathBinaryMatrix(new int[][] { { 1, 0, 0 }, { 1, 1, 0 }, { 1, 1, 0 } }));
20+
}
21+
22+
static class Solution {
23+
24+
// 八个方向偏移量（上、下、左、右、左上、右下、左下、右上）
25+
private final int[][] directions = {
26+
{ -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 },
27+
{ -1, -1 }, { 1, 1 }, { -1, 1 }, { 1, -1 }
28+
};
29+
30+
public int shortestPathBinaryMatrix(int[][] grid) {
31+
32+
int m = grid.length, n = grid[0].length;
33+
if (grid[0][0] == 1 || grid[m - 1][n - 1] == 1) {
34+
return -1;
35+
}
36+
37+
// 需要记录走过的路径，避免死循环
38+
boolean[][] visited = new boolean[m][n];
39+
LinkedList<int[]> queue = new LinkedList<>();
40+
41+
// 初始化队列，从 (0, 0) 出发
42+
visited[0][0] = true;
43+
queue.offer(new int[] { 0, 0 });
44+
45+
int step = 1;
46+
while (!queue.isEmpty()) {
47+
int size = queue.size();
48+
for (int i = 0; i < size; i++) {
49+
int[] cur = queue.poll();
50+
int x = cur[0], y = cur[1];
51+
if (grid[x][y] != 0) { return -1; }
52+
// 到达底部，返回步骤数
53+
if (x == m - 1 && y == n - 1) { return step; }
54+
55+
for (int[] d : directions) {
56+
int nextX = x + d[0], nextY = y + d[1];
57+
if (nextX < 0 || nextX >= m || nextY < 0 || nextY >= n) { continue; }
58+
if (visited[nextX][nextY] || grid[nextX][nextY] != 0) { continue; }
59+
visited[nextX][nextY] = true;
60+
queue.offer(new int[] { nextX, nextY });
61+
}
62+
}
63+
step++;
64+
}
65+
return -1;
66+
}
67+
68+
}
69+
70+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/bfs/完全二叉树插入器.java‎

Lines changed: 23 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -23,46 +23,44 @@ public static void main(String[] args) {
2323
static class CBTInserter {
2424

2525
private final TreeNode root;
26-
private final LinkedList<TreeNode> candidate;
26+
// 这个队列只记录完全二叉树底部可以进行插入的节点
27+
private final LinkedList<TreeNode> queue;
2728

2829
public CBTInserter(TreeNode root) {
2930
this.root = root;
30-
this.candidate = new LinkedList<>();
31-
32-
LinkedList<TreeNode> queue = new LinkedList<>();
33-
queue.offer(root);
34-
while (!queue.isEmpty()) {
35-
int size = queue.size();
31+
this.queue = new LinkedList<>();
32+
LinkedList<TreeNode> tmp = new LinkedList<>();
33+
tmp.offer(root);
34+
while (!tmp.isEmpty()) {
35+
int size = tmp.size();
3636
for (int i = 0; i < size; i++) {
37-
TreeNode node = queue.poll();
38-
if (node.left != null) {
39-
queue.offer(node.left);
40-
}
41-
if (node.right != null) {
42-
queue.offer(node.right);
43-
}
37+
TreeNode node = tmp.poll();
38+
if (node == null) { continue; }
39+
if (node.left != null) { tmp.offer(node.left); }
40+
if (node.right != null) { tmp.offer(node.right); }
4441
if (node.left == null || node.right == null) {
45-
candidate.offer(node);
42+
// 找到完全二叉树底部可以进行插入的节点
43+
queue.offer(node);
4644
}
4745
}
4846
}
4947
}
5048

5149
public int insert(int val) {
52-
TreeNode child = new TreeNode(val);
53-
TreeNode node = candidate.peek();
54-
if (node.left == null) {
55-
node.left = child;
56-
} else {
57-
node.right = child;
58-
candidate.poll();
50+
TreeNode node = new TreeNode(val);
51+
TreeNode cur = queue.peek();
52+
queue.offer(node);
53+
if (cur.left == null) {
54+
cur.left = node;
55+
} else if (cur.right == null) {
56+
cur.right = node;
57+
queue.poll();
5958
}
60-
candidate.offer(child);
61-
return node.val;
59+
return cur.val;
6260
}
6361

6462
public TreeNode get_root() {
65-
return root;
63+
return this.root;
6664
}
6765

6866
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/bfs/打开转盘锁.java‎

Lines changed: 27 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,8 @@
22

33
import org.junit.jupiter.api.Assertions;
44

5+
import java.util.ArrayList;
6+
import java.util.Collections;
57
import java.util.HashSet;
68
import java.util.LinkedList;
79
import java.util.List;
@@ -22,44 +24,40 @@ public static void main(String[] args) {
2224
String[] deadends = new String[] { "0201", "0101", "0102", "1212", "2002" };
2325
Assertions.assertEquals(6, s.openLock(deadends, "0202"));
2426

25-
// String[] deadends2 = new String[] { "8888" };
26-
// Assertions.assertEquals(1, s.openLock(deadends2, "0009"));
27-
//
28-
// String[] deadends3 = new String[] { "8887", "8889", "8878", "8898", "8788", "8988", "7888", "9888" };
29-
// Assertions.assertEquals(-1, s.openLock(deadends3, "8888"));
27+
String[] deadends2 = new String[] { "8888" };
28+
Assertions.assertEquals(1, s.openLock(deadends2, "0009"));
29+
30+
String[] deadends3 = new String[] { "8887", "8889", "8878", "8898", "8788", "8988", "7888", "9888" };
31+
Assertions.assertEquals(-1, s.openLock(deadends3, "8888"));
3032
}
3133

3234
static class Solution {
3335

3436
public int openLock(String[] deadends, String target) {
35-
Set<String> black = new HashSet<>();
36-
for (String d : deadends) {
37-
black.add(d);
38-
}
39-
4037
int step = 0;
38+
39+
Set<String> blackSet = new HashSet<>();
40+
Collections.addAll(blackSet, deadends);
41+
42+
if (blackSet.contains("0000")) { return -1; }
43+
4144
Set<String> visited = new HashSet<>();
4245
LinkedList<String> queue = new LinkedList<>();
43-
queue.offer("0000");
4446
visited.add("0000");
47+
queue.offer("0000");
4548

4649
while (!queue.isEmpty()) {
4750
int size = queue.size();
48-
System.out.printf("step: %d\n", step);
4951
for (int i = 0; i < size; i++) {
50-
51-
String node = queue.poll();
52-
53-
if (target.equals(node)) {
52+
String cur = queue.poll();
53+
if (cur.equals(target)) {
5454
return step;
5555
}
5656

57-
List<String> neighbors = getNeighbors(node);
58-
System.out.printf("\tnode: %s, neighbors: %s\n", node, neighbors);
59-
for (String neighbor : getNeighbors(node)) {
60-
if (!visited.contains(neighbor) && !black.contains(neighbor)) {
61-
queue.offer(neighbor);
62-
visited.add(neighbor);
57+
for (String neighbour : neighbours(cur)) {
58+
if (!visited.contains(neighbour) && !blackSet.contains(neighbour)) {
59+
visited.add(neighbour);
60+
queue.offer(neighbour);
6361
}
6462
}
6563
}
@@ -68,7 +66,7 @@ public int openLock(String[] deadends, String target) {
6866
return -1;
6967
}
7068

71-
String plus(String s, int i) {
69+
public String plus(String s, int i) {
7270
char[] ch = s.toCharArray();
7371
if (ch[i] == '9') {
7472
ch[i] = '0';
@@ -78,7 +76,7 @@ String plus(String s, int i) {
7876
return new String(ch);
7977
}
8078

81-
String minus(String s, int i) {
79+
public String minus(String s, int i) {
8280
char[] ch = s.toCharArray();
8381
if (ch[i] == '0') {
8482
ch[i] = '9';
@@ -88,13 +86,13 @@ String minus(String s, int i) {
8886
return new String(ch);
8987
}
9088

91-
List<String> getNeighbors(String s) {
92-
List<String> neighbors = new LinkedList<>();
89+
public List<String> neighbours(String s) {
90+
List<String> neighbours = new ArrayList<>();
9391
for (int i = 0; i < s.length(); i++) {
94-
neighbors.add(plus(s, i));
95-
neighbors.add(minus(s, i));
92+
neighbours.add(plus(s, i));
93+
neighbours.add(minus(s, i));
9694
}
97-
return neighbors;
95+
return neighbours;
9896
}
9997

10098
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/bfs/最小基因变化.java‎

Lines changed: 20 additions & 38 deletions
Original file line numberDiff line numberDiff line change
@@ -34,65 +34,47 @@ public static void main(String[] args) {
3434

3535
static class Solution {
3636

37-
final char[] options = new char[] { 'A', 'C', 'G', 'T' };
37+
final char[] AGCT = new char[] { 'A', 'C', 'G', 'T' };
3838

3939
public int minMutation(String startGene, String endGene, String[] bank) {
40-
return bfs(startGene, endGene, bank);
41-
}
42-
43-
public int bfs(String startGene, String endGene, String[] bank) {
44-
45-
Set<String> bankSet = new HashSet<>(Arrays.asList(bank));
46-
// 最终结果不在有效基因集合中，直接返回
47-
if (!bankSet.contains(endGene)) {
48-
return -1;
49-
}
40+
if (startGene.equals(endGene)) { return 0; }
5041

42+
int step = 0;
43+
Set<String> banks = new HashSet<>(Arrays.asList(bank));
5144
Set<String> visited = new HashSet<>();
5245
LinkedList<String> queue = new LinkedList<>();
5346
queue.offer(startGene);
5447

55-
int step = 0;
5648
while (!queue.isEmpty()) {
5749
int size = queue.size();
5850
for (int i = 0; i < size; i++) {
59-
String cur = queue.poll();
60-
if (cur.equals(endGene)) {
61-
return step;
62-
}
63-
64-
List<String> neighbors = getNeighbors(cur, bankSet);
65-
System.out.printf("%s 的邻居：%s\n", cur, neighbors);
66-
for (String str : neighbors) {
67-
if (visited.contains(str)) {
68-
continue;
51+
String curGene = queue.poll();
52+
if (curGene.equals(endGene)) { return step; }
53+
for (String newGene : neighbours(curGene)) {
54+
if (!visited.contains(newGene) && banks.contains(newGene)) {
55+
queue.offer(newGene);
56+
visited.add(newGene);
6957
}
70-
visited.add(str);
71-
queue.offer(str);
7258
}
7359
}
7460
step++;
7561
}
7662
return -1;
7763
}
7864

79-
public List<String> getNeighbors(String s, Set<String> bankSet) {
80-
List<String> list = new LinkedList<>();
81-
char[] ch = s.toCharArray();
65+
// 当前基因的每个位置都可以变异为 A/G/C/T，穷举所有可能的结构
66+
public List<String> neighbours(String gene) {
67+
List<String> res = new LinkedList<>();
68+
char[] ch = gene.toCharArray();
8269
for (int i = 0; i < ch.length; i++) {
83-
char oldChar = ch[i];
84-
for (char newChar : options) {
85-
if (oldChar != newChar) {
86-
ch[i] = newChar;
87-
String str = new String(ch);
88-
if (bankSet.contains(str)) {
89-
list.add(str);
90-
}
91-
}
70+
char c = ch[i];
71+
for (char option : AGCT) {
72+
ch[i] = option;
73+
res.add(new String(ch));
9274
}
93-
ch[i] = oldChar;
75+
ch[i] = c;
9476
}
95-
return list;
77+
return res;
9678
}
9779

9880
}

0 commit comments

Comments
 (0)