Skip to content

Commit 5fb7476

Browse files
dunwudunwu
committed
feat: leetcode 刷题
1 parent 17047d6 commit 5fb7476

81 files changed

Lines changed: 3853 additions & 495 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: 221 additions & 79 deletions
Large diffs are not rendered by default.

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/backtrack/解数独.java‎

Lines changed: 0 additions & 44 deletions
This file was deleted.

‎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 io.github.dunwu.algorithm.tree.TreeNode;
4+
import org.junit.jupiter.api.Assertions;
5+
6+
import java.util.LinkedList;
7+
8+
/**
9+
* <a href="https://leetcode.cn/problems/complete-binary-tree-inserter/">919. 完全二叉树插入器</a>
10+
*
11+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
12+
* @date 2025-11-07
13+
*/
14+
public class 完全二叉树插入器 {
15+
16+
public static void main(String[] args) {
17+
CBTInserter c = new CBTInserter(TreeNode.buildTree(1, 2));
18+
Assertions.assertEquals(1, c.insert(3));
19+
Assertions.assertEquals(2, c.insert(4));
20+
Assertions.assertEquals(TreeNode.buildTree(1, 2, 3, 4), c.get_root());
21+
}
22+
23+
static class CBTInserter {
24+
25+
private final TreeNode root;
26+
private final LinkedList<TreeNode> candidate;
27+
28+
public CBTInserter(TreeNode root) {
29+
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();
36+
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+
}
44+
if (node.left == null || node.right == null) {
45+
candidate.offer(node);
46+
}
47+
}
48+
}
49+
}
50+
51+
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();
59+
}
60+
candidate.offer(child);
61+
return node.val;
62+
}
63+
64+
public TreeNode get_root() {
65+
return root;
66+
}
67+
68+
}
69+
70+
}

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

Lines changed: 102 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,102 @@
1+
package io.github.dunwu.algorithm.bfs;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
import java.util.HashSet;
6+
import java.util.LinkedList;
7+
import java.util.List;
8+
import java.util.Set;
9+
10+
/**
11+
* <a href="https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/">297. 二叉树的序列化与反序列化</a>
12+
*
13+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
14+
* @date 2025-11-06
15+
*/
16+
public class 打开转盘锁 {
17+
18+
public static void main(String[] args) {
19+
20+
Solution s = new Solution();
21+
22+
String[] deadends = new String[] { "0201", "0101", "0102", "1212", "2002" };
23+
Assertions.assertEquals(6, s.openLock(deadends, "0202"));
24+
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"));
30+
}
31+
32+
static class Solution {
33+
34+
public int openLock(String[] deadends, String target) {
35+
Set<String> black = new HashSet<>();
36+
for (String d : deadends) {
37+
black.add(d);
38+
}
39+
40+
int step = 0;
41+
Set<String> visited = new HashSet<>();
42+
LinkedList<String> queue = new LinkedList<>();
43+
queue.offer("0000");
44+
visited.add("0000");
45+
46+
while (!queue.isEmpty()) {
47+
int size = queue.size();
48+
System.out.printf("step: %d\n", step);
49+
for (int i = 0; i < size; i++) {
50+
51+
String node = queue.poll();
52+
53+
if (target.equals(node)) {
54+
return step;
55+
}
56+
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);
63+
}
64+
}
65+
}
66+
step++;
67+
}
68+
return -1;
69+
}
70+
71+
String plus(String s, int i) {
72+
char[] ch = s.toCharArray();
73+
if (ch[i] == '9') {
74+
ch[i] = '0';
75+
} else {
76+
ch[i] += 1;
77+
}
78+
return new String(ch);
79+
}
80+
81+
String minus(String s, int i) {
82+
char[] ch = s.toCharArray();
83+
if (ch[i] == '0') {
84+
ch[i] = '9';
85+
} else {
86+
ch[i] -= 1;
87+
}
88+
return new String(ch);
89+
}
90+
91+
List<String> getNeighbors(String s) {
92+
List<String> neighbors = new LinkedList<>();
93+
for (int i = 0; i < s.length(); i++) {
94+
neighbors.add(plus(s, i));
95+
neighbors.add(minus(s, i));
96+
}
97+
return neighbors;
98+
}
99+
100+
}
101+
102+
}

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

Lines changed: 100 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,100 @@
1+
package io.github.dunwu.algorithm.bfs;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
import java.util.Arrays;
6+
import java.util.HashSet;
7+
import java.util.LinkedList;
8+
import java.util.List;
9+
import java.util.Set;
10+
11+
/**
12+
* <a href="https://leetcode.cn/problems/minimum-genetic-mutation/">433. 最小基因变化</a>
13+
*
14+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
15+
* @date 2025-11-07
16+
*/
17+
public class 最小基因变化 {
18+
19+
public static void main(String[] args) {
20+
Solution s = new Solution();
21+
Assertions.assertEquals(1,
22+
s.minMutation("AACCGGTT", "AACCGGTA", new String[] { "AACCGGTA" }));
23+
Assertions.assertEquals(2,
24+
s.minMutation("AACCGGTT", "AAACGGTA", new String[] { "AACCGGTA", "AACCGCTA", "AAACGGTA" }));
25+
Assertions.assertEquals(3,
26+
s.minMutation("AAAAACCC", "AACCCCCC", new String[] { "AAAACCCC", "AAACCCCC", "AACCCCCC" }));
27+
Assertions.assertEquals(-1,
28+
s.minMutation("AACCGGTT", "AACCGGTA", new String[] {}));
29+
Assertions.assertEquals(-1,
30+
s.minMutation("AAAAAAAA", "CCCCCCCC",
31+
new String[] { "AAAAAAAA", "AAAAAAAC", "AAAAAACC", "AAAAACCC", "AAAACCCC", "AACACCCC", "ACCACCCC",
32+
"ACCCCCCC", "CCCCCCCA" }));
33+
}
34+
35+
static class Solution {
36+
37+
final char[] options = new char[] { 'A', 'C', 'G', 'T' };
38+
39+
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+
}
50+
51+
Set<String> visited = new HashSet<>();
52+
LinkedList<String> queue = new LinkedList<>();
53+
queue.offer(startGene);
54+
55+
int step = 0;
56+
while (!queue.isEmpty()) {
57+
int size = queue.size();
58+
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;
69+
}
70+
visited.add(str);
71+
queue.offer(str);
72+
}
73+
}
74+
step++;
75+
}
76+
return -1;
77+
}
78+
79+
public List<String> getNeighbors(String s, Set<String> bankSet) {
80+
List<String> list = new LinkedList<>();
81+
char[] ch = s.toCharArray();
82+
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+
}
92+
}
93+
ch[i] = oldChar;
94+
}
95+
return list;
96+
}
97+
98+
}
99+
100+
}

0 commit comments

Comments
 (0)