Skip to content

Commit 17047d6

Browse files
dunwudunwu
committed
feat: leetcode 刷题
1 parent 538fa27 commit 17047d6

File tree

76 files changed

+2563
-2122
lines changed

Some content is hidden

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

76 files changed

+2563
-2122
lines changed

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/backtrack/全排列.java‎

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
package io.github.dunwu.algorithm.backtrack;
2+
3+
import java.util.LinkedList;
4+
import java.util.List;
5+
6+
/**
7+
* <a href="https://leetcode.cn/problems/permutations/">46. 全排列</a>
8+
*
9+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
10+
* @date 2025-11-03
11+
*/
12+
public class 全排列 {
13+
14+
public static void main(String[] args) {
15+
Solution s = new Solution();
16+
int[] input = new int[] { 1, 2, 3 };
17+
List<List<Integer>> output = s.permute(input);
18+
System.out.println("output: " + output);
19+
}
20+
21+
static class Solution {
22+
23+
private List<List<Integer>> res = null;
24+
25+
public List<List<Integer>> permute(int[] nums) {
26+
// 记录「路径」
27+
LinkedList<Integer> track = new LinkedList<>();
28+
// 「路径」中的元素会被标记为 true，避免重复使用
29+
boolean[] used = new boolean[nums.length];
30+
res = new LinkedList<>();
31+
backtrack(nums, track, used);
32+
return res;
33+
}
34+
35+
public void backtrack(int[] nums, LinkedList<Integer> track, boolean[] used) {
36+
if (track.size() == nums.length) {
37+
res.add(new LinkedList<>(track));
38+
return;
39+
}
40+
41+
for (int i = 0; i < nums.length; i++) {
42+
if (used[i]) {
43+
continue;
44+
}
45+
46+
// 选择
47+
track.addLast(nums[i]);
48+
used[i] = true;
49+
50+
// 进入下一层决策树
51+
backtrack(nums, track, used);
52+
53+
// 取消选择
54+
track.removeLast();
55+
used[i] = false;
56+
}
57+
}
58+
59+
}
60+
61+
}

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

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package io.github.dunwu.algorithm.backtrack;
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/sudoku-solver/">37. 解数独</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+
char[][] input = new char[][] { { '5', '3', '.', '.', '7', '.', '.', '.', '.' },
19+
{ '6', '.', '.', '1', '9', '5', '.', '.', '.' }, { '.', '9', '8', '.', '.', '.', '.', '6', '.' },
20+
{ '8', '.', '.', '.', '6', '.', '.', '.', '3' }, { '4', '.', '.', '8', '.', '3', '.', '.', '1' },
21+
{ '7', '.', '.', '.', '2', '.', '.', '.', '6' }, { '.', '6', '.', '.', '.', '.', '2', '8', '.' },
22+
{ '.', '.', '.', '4', '1', '9', '.', '.', '5' }, { '.', '.', '.', '.', '8', '.', '.', '7', '9' } };
23+
char[][] expect = new char[][] { { '5', '3', '4', '6', '7', '8', '9', '1', '2' },
24+
{ '6', '7', '2', '1', '9', '5', '3', '4', '8' }, { '1', '9', '8', '3', '4', '2', '5', '6', '7' },
25+
{ '8', '5', '9', '7', '6', '1', '4', '2', '3' }, { '4', '2', '6', '8', '5', '3', '7', '9', '1' },
26+
{ '7', '1', '3', '9', '2', '4', '8', '5', '6' }, { '9', '6', '1', '5', '3', '7', '2', '8', '4' },
27+
{ '2', '8', '7', '4', '1', '9', '6', '3', '5' }, { '3', '4', '5', '2', '8', '6', '1', '7', '9' } };
28+
s.solveSudoku(input);
29+
Assertions.assertArrayEquals(expect, input);
30+
}
31+
32+
static class Solution {
33+
34+
public void solveSudoku(char[][] board) {
35+
36+
}
37+
38+
public void backtrack(char[][] board, LinkedList<Integer> track, boolean[] used) {
39+
40+
}
41+
42+
}
43+
44+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/data_structure/LRU缓存.java‎

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
package io.github.dunwu.algorithm.data_structure;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
import java.util.Iterator;
6+
import java.util.LinkedHashMap;
7+
8+
/**
9+
* <a href="https://leetcode.cn/problems/lru-cache/">146. LRU 缓存</a>
10+
*
11+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
12+
* @date 2025-10-31
13+
*/
14+
public class LRU缓存 {
15+
16+
public static void main(String[] args) {
17+
18+
LRUCache lRUCache = new LRUCache(2);
19+
lRUCache.put(1, 1); // 缓存是 {1=1}
20+
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
21+
Assertions.assertEquals(1, lRUCache.get(1));
22+
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
23+
Assertions.assertEquals(-1, lRUCache.get(2));
24+
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
25+
Assertions.assertEquals(-1, lRUCache.get(1));
26+
Assertions.assertEquals(3, lRUCache.get(3));
27+
Assertions.assertEquals(4, lRUCache.get(4));
28+
}
29+
30+
static class LRUCache {
31+
32+
private int capacity = 0;
33+
private LinkedHashMap<Integer, Integer> cache = null;
34+
35+
public LRUCache(int capacity) {
36+
this.capacity = capacity;
37+
this.cache = new LinkedHashMap<>(capacity);
38+
}
39+
40+
public int get(int key) {
41+
Integer val = cache.get(key);
42+
if (val != null) {
43+
cache.remove(key);
44+
cache.put(key, val);
45+
}
46+
return val == null ? -1 : val;
47+
}
48+
49+
public void put(int key, int value) {
50+
if (cache.containsKey(key)) {
51+
cache.remove(key);
52+
} else {
53+
if (capacity <= cache.size()) {
54+
Iterator<Integer> iterator = cache.keySet().iterator();
55+
cache.remove(iterator.next());
56+
}
57+
}
58+
cache.put(key, value);
59+
}
60+
61+
}
62+
63+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/data_structure/我的日程安排表.java‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package io.github.dunwu.algorithm.data_structure;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
import java.util.TreeMap;
6+
7+
/**
8+
* <a href="https://leetcode.cn/problems/my-calendar-i/">729. 我的日程安排表 I</a>
9+
*
10+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
11+
* @date 2025-11-03
12+
*/
13+
public class 我的日程安排表 {
14+
15+
public static void main(String[] args) {
16+
MyCalendar s = new MyCalendar();
17+
Assertions.assertTrue(s.book(10, 20));
18+
Assertions.assertFalse(s.book(15, 25));
19+
Assertions.assertTrue(s.book(20, 30));
20+
}
21+
22+
static class MyCalendar {
23+
24+
private TreeMap<Integer, Integer> calendar = null;
25+
26+
public MyCalendar() {
27+
calendar = new TreeMap<>();
28+
}
29+
30+
public boolean book(int start, int end) {
31+
Integer earlier = calendar.floorKey(start);
32+
Integer later = calendar.ceilingKey(start);
33+
if (later != null && later < end) {
34+
return false;
35+
}
36+
if (earlier != null && start < calendar.get(earlier)) {
37+
return false;
38+
}
39+
calendar.put(start, end);
40+
return true;
41+
}
42+
43+
}
44+
45+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/data_structure/按递增顺序显示卡牌.java‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
package io.github.dunwu.algorithm.data_structure;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
import java.util.Arrays;
6+
import java.util.LinkedList;
7+
8+
/**
9+
* <a href="https://leetcode.cn/problems/reveal-cards-in-increasing-order/">950. 按递增顺序显示卡牌</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+
Assertions.assertArrayEquals(new int[] { 2, 13, 3, 11, 5, 17, 7 }
19+
, s.deckRevealedIncreasing(new int[] { 17, 13, 11, 2, 3, 5, 7 }));
20+
}
21+
22+
static class Solution {
23+
24+
public int[] deckRevealedIncreasing(int[] deck) {
25+
int n = deck.length;
26+
LinkedList<Integer> res = new LinkedList<>();
27+
Arrays.sort(deck);
28+
for (int i = n - 1; i >= 0; i--) {
29+
if (!res.isEmpty()) {
30+
res.addFirst(res.removeLast());
31+
}
32+
res.addFirst(deck[i]);
33+
}
34+
int[] arr = new int[n];
35+
for (int i = 0; i < res.size(); i++) {
36+
arr[i] = res.get(i);
37+
}
38+
return arr;
39+
}
40+
41+
}
42+
43+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/data_structure/无法吃午餐的学生数量.java‎

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
package io.github.dunwu.algorithm.data_structure;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
import java.util.Arrays;
6+
import java.util.LinkedList;
7+
8+
/**
9+
* <a href="https://leetcode.cn/problems/number-of-students-unable-to-eat-lunch/">1700. 无法吃午餐的学生数量</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+
Assertions.assertEquals(0, s.countStudents(new int[] { 1, 1, 0, 0 }, new int[] { 0, 1, 0, 1 }));
19+
Assertions.assertEquals(3, s.countStudents(new int[] { 1, 1, 1, 0, 0, 1 }, new int[] { 1, 0, 0, 0, 1, 1 }));
20+
}
21+
22+
static class Solution {
23+
24+
public int countStudents(int[] students, int[] sandwiches) {
25+
int total = students.length;
26+
LinkedList<Integer> studentQueue = new LinkedList<>();
27+
for (int s : students) {
28+
studentQueue.addLast(s);
29+
}
30+
int matchNum = 0;
31+
while (matchNum < sandwiches.length) {
32+
int notMatchNum = 0;
33+
int size = studentQueue.size();
34+
while (notMatchNum < size) {
35+
Integer s = studentQueue.removeFirst();
36+
if (s == sandwiches[matchNum]) {
37+
matchNum++;
38+
break;
39+
} else {
40+
studentQueue.addLast(s);
41+
notMatchNum++;
42+
}
43+
}
44+
if (notMatchNum == size) {
45+
break;
46+
}
47+
}
48+
return total - matchNum;
49+
}
50+
51+
}
52+
53+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/data_structure/计算器.java‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
package io.github.dunwu.algorithm.data_structure;
2+
3+
import java.util.Arrays;
4+
5+
/**
6+
* 计数器模板
7+
*
8+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
9+
* @date 2025-10-31
10+
*/
11+
public class 计算器 {
12+
13+
public static void main(String[] args) {
14+
Solution s = new Solution();
15+
System.out.println("args = " + Arrays.toString(args));
16+
}
17+
18+
static class Solution {
19+
20+
public int toNum(String s) {
21+
if (s == null || s.length() == 0) { return 0; }
22+
int num = 0;
23+
for (char c : s.toCharArray()) {
24+
num = num * 10 + (c - '0');
25+
}
26+
return num;
27+
}
28+
29+
}
30+
31+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/graph/template/图的DFS遍历框架.java‎

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
package io.github.dunwu.algorithm.graph.template;
2+
3+
/**
4+
* 图的遍历框架
5+
*
6+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
7+
* @date 2025-11-03
8+
*/
9+
public class 图的DFS遍历框架 {
10+
11+
// 图的遍历框架
12+
// 需要一个 visited 数组记录被遍历过的节点
13+
// 避免走回头路陷入死循环
14+
void traverse(Vertex s, boolean[] visited) {
15+
// base case
16+
if (s == null) {
17+
return;
18+
}
19+
if (visited[s.id]) {
20+
// 防止死循环
21+
return;
22+
}
23+
// 前序位置
24+
visited[s.id] = true;
25+
System.out.println("visit " + s.id);
26+
for (Vertex neighbor : s.neighbors) {
27+
traverse(neighbor, visited);
28+
}
29+
// 后序位置
30+
}
31+
32+
static class Vertex {
33+
34+
int id;
35+
Vertex[] neighbors;
36+
37+
}
38+
39+
}

0 commit comments

Comments
 (0)