Skip to content

Commit d9cf07d

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

52 files changed

Lines changed: 1898 additions & 1055 deletions

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: 66 additions & 63 deletions
Large diffs are not rendered by default.

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/dfs/N皇后.java‎

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

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/dfs/N皇后II.java‎

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

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

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
/**
2+
* 通过回溯算法解决排列、组合、子集类型的问题
3+
*
4+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
5+
* @date 2025-12-13
6+
*/
7+
package io.github.dunwu.algorithm.dfs.permutation_combination;

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

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
package io.github.dunwu.algorithm.dfs.permutation_combination;
2+
3+
import cn.hutool.core.collection.CollectionUtil;
4+
import io.github.dunwu.algorithm.util.ArrayUtil;
5+
import org.junit.jupiter.api.Assertions;
6+
7+
import java.util.LinkedList;
8+
import java.util.List;
9+
10+
/**
11+
* <a href="https://leetcode.cn/problems/permutations/">46. 全排列</a>
12+
*
13+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
14+
* @date 2025-11-03
15+
*/
16+
public class 全排列 {
17+
18+
public static void main(String[] args) {
19+
Solution s = new Solution();
20+
int[][] expect = { { 1, 2, 3 }, { 1, 3, 2 }, { 2, 1, 3 }, { 2, 3, 1 }, { 3, 1, 2 }, { 3, 2, 1 } };
21+
int[][] expect2 = { { 0, 1 }, { 1, 0 } };
22+
Assertions.assertArrayEquals(expect, ArrayUtil.toIntMatrixArray(s.permute(new int[] { 1, 2, 3 })));
23+
Assertions.assertArrayEquals(expect2, ArrayUtil.toIntMatrixArray(s.permute(new int[] { 0, 1 })));
24+
Assertions.assertArrayEquals(new int[][] { { 1 } }, ArrayUtil.toIntMatrixArray(s.permute(new int[] { 1 })));
25+
}
26+
27+
static class Solution {
28+
29+
// 「路径」中的元素会被标记为 true，避免重复使用
30+
boolean[] visited;
31+
// 记录「路径」
32+
LinkedList<Integer> path;
33+
List<List<Integer>> res;
34+
35+
// 主函数，输入一组不重复的数字，返回它们的全排列
36+
List<List<Integer>> permute(int[] nums) {
37+
visited = new boolean[nums.length];
38+
path = new LinkedList<>();
39+
res = new LinkedList<>();
40+
backtrack(nums);
41+
return res;
42+
}
43+
44+
// 路径：记录在 path 中
45+
// 选择列表：nums 中不存在于 path 的那些元素（visited[i] 为 false）
46+
// 结束条件：nums 中的元素全都在 path 中出现
47+
void backtrack(int[] nums) {
48+
// 【结束】【前序】到达决策树叶子节点，可以记录结果
49+
if (path.size() == nums.length) {
50+
res.add(new LinkedList<>(path));
51+
System.out.printf("【结果】 %s\n\n", CollectionUtil.join(path, " -> "));
52+
return;
53+
}
54+
55+
for (int i = 0; i < nums.length; i++) {
56+
57+
// 排除不合法的选择
58+
// nums[i] 已经在 path 中，跳过
59+
if (visited[i]) { continue; }
60+
61+
// 【选择】
62+
path.add(nums[i]);
63+
visited[i] = true;
64+
System.out.printf("\t\t%s\n", CollectionUtil.join(path, " -> "));
65+
66+
// 【回溯】
67+
backtrack(nums);
68+
69+
// 【取消选择】
70+
path.removeLast();
71+
visited[i] = false;
72+
}
73+
}
74+
75+
}
76+
77+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/dfs/permutation_combination/全排列2.java‎

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
package io.github.dunwu.algorithm.dfs.permutation_combination;
2+
3+
import cn.hutool.core.collection.CollectionUtil;
4+
import io.github.dunwu.algorithm.util.ArrayUtil;
5+
import org.junit.jupiter.api.Assertions;
6+
7+
import java.util.Arrays;
8+
import java.util.LinkedList;
9+
import java.util.List;
10+
11+
/**
12+
* <a href="https://leetcode.cn/problems/permutations-ii/">47. 全排列 II</a>
13+
* <a href="https://leetcode.cn/problems/7p8L0Z/">LCR 084. 全排列 II </a>
14+
*
15+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
16+
* @date 2025-11-03
17+
*/
18+
public class 全排列2 {
19+
20+
public static void main(String[] args) {
21+
Solution s = new Solution();
22+
23+
int[][] expect = { { 1, 1, 2 }, { 1, 2, 1 }, { 2, 1, 1 } };
24+
Assertions.assertArrayEquals(expect, ArrayUtil.toIntMatrixArray(s.permuteUnique(new int[] { 1, 1, 2 })));
25+
26+
int[][] expect2 = { { 1, 2, 3 }, { 1, 3, 2 }, { 2, 1, 3 }, { 2, 3, 1 }, { 3, 1, 2 }, { 3, 2, 1 } };
27+
Assertions.assertArrayEquals(expect2, ArrayUtil.toIntMatrixArray(s.permuteUnique(new int[] { 1, 2, 3 })));
28+
}
29+
30+
static class Solution {
31+
32+
private boolean[] visited;
33+
private List<Integer> path;
34+
private List<List<Integer>> res;
35+
36+
public List<List<Integer>> permuteUnique(int[] nums) {
37+
visited = new boolean[nums.length];
38+
path = new LinkedList<>();
39+
res = new LinkedList<>();
40+
Arrays.sort(nums);
41+
backtrack(nums);
42+
return res;
43+
}
44+
45+
public void backtrack(int[] nums) {
46+
47+
// 【结束】【前序】到达决策树叶子节点，可以记录结果
48+
if (path.size() == nums.length) {
49+
res.add(new LinkedList<>(path));
50+
System.out.printf("【结果】 %s\n\n", CollectionUtil.join(path, " -> "));
51+
}
52+
53+
for (int i = 0; i < nums.length; i++) {
54+
55+
// 排除不合法的选择
56+
if (visited[i]) { continue; }
57+
// 剪枝逻辑，固定相同的元素在排列中的相对位置
58+
if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) { continue; }
59+
60+
// 【选择】
61+
visited[i] = true;
62+
path.add(nums[i]);
63+
System.out.printf("\t\t%s\n", CollectionUtil.join(path, " -> "));
64+
65+
// 【回溯】
66+
backtrack(nums);
67+
68+
// 【取消选择】
69+
path.remove(path.size() - 1);
70+
visited[i] = false;
71+
}
72+
}
73+
74+
}
75+
76+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/dfs/permutation_combination/子集.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.dfs.permutation_combination;
2+
3+
import cn.hutool.core.collection.CollectionUtil;
4+
import io.github.dunwu.algorithm.util.ArrayUtil;
5+
import org.junit.jupiter.api.Assertions;
6+
7+
import java.util.Arrays;
8+
import java.util.LinkedList;
9+
import java.util.List;
10+
11+
/**
12+
* <a href="https://leetcode.cn/problems/subsets/">78. 子集</a>
13+
*
14+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
15+
* @date 2025-11-04
16+
*/
17+
public class 子集 {
18+
19+
public static void main(String[] args) {
20+
Solution s = new Solution();
21+
int[][] expect = { {}, { 1 }, { 1, 2 }, { 1, 2, 3 }, { 1, 3 }, { 2 }, { 2, 3 }, { 3 } };
22+
Assertions.assertArrayEquals(expect, ArrayUtil.toIntMatrixArray(s.subsets(new int[] { 1, 2, 3 })));
23+
Assertions.assertArrayEquals(new int[][] { {}, { 0 } }, ArrayUtil.toIntMatrixArray(s.subsets(new int[] { 0 })));
24+
}
25+
26+
static class Solution {
27+
28+
private boolean[] visited;
29+
private List<Integer> path;
30+
private List<List<Integer>> res;
31+
32+
// 主函数
33+
public List<List<Integer>> subsets(int[] nums) {
34+
visited = new boolean[nums.length];
35+
path = new LinkedList<>();
36+
res = new LinkedList<>();
37+
Arrays.sort(nums);
38+
backtrack(nums, 0);
39+
return res;
40+
}
41+
42+
// 回溯算法核心函数，遍历子集问题的回溯树
43+
public void backtrack(int[] nums, int start) {
44+
45+
// 【结束】【前序】到达决策树叶子节点，可以记录结果
46+
res.add(new LinkedList<>(path));
47+
System.out.printf("【结果】 %s\n\n", CollectionUtil.join(path, " -> "));
48+
49+
for (int i = start; i < nums.length; i++) {
50+
51+
// 排除不合法的选择
52+
if (visited[i]) { continue; }
53+
54+
// 【选择】
55+
visited[i] = true;
56+
path.add(nums[i]);
57+
System.out.printf("\t\t%s\n", CollectionUtil.join(path, " -> "));
58+
59+
// 【回溯】
60+
backtrack(nums, i + 1);
61+
62+
// 【取消选择】
63+
path.remove(path.size() - 1);
64+
visited[i] = false;
65+
}
66+
}
67+
68+
}
69+
70+
}

0 commit comments

Comments
 (0)