Skip to content

Commit 94a260c

Browse files
dunwudunwu
committed
update codes
1 parent c53ebf7 commit 94a260c

File tree

10 files changed

+542
-49
lines changed

10 files changed

+542
-49
lines changed

‎assets/算法.xmind‎

552 Bytes
Binary file not shown.

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

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
package io.github.dunwu.algorithm.dfs;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
6+
/**
7+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
8+
* @since 2020-07-04
9+
* @see <a href="https://leetcode-cn.com/problems/n-queens/">51. N皇后</a>
10+
*/
11+
public class N皇后 {
12+
13+
int[] cols;
14+
int[] first;
15+
int[] second;
16+
int[] queens;
17+
List<List<String>> output = new ArrayList<>();
18+
19+
public static void main(String[] args) {
20+
N皇后 demo = new N皇后();
21+
List<List<String>> result = demo.solveNQueens(5);
22+
result.forEach(System.out::println);
23+
}
24+
25+
public List<List<String>> solveNQueens(int n) {
26+
queens = new int[n];
27+
cols = new int[n];
28+
first = new int[2 * n];
29+
second = new int[2 * n];
30+
backtrack(n, 0);
31+
return output;
32+
}
33+
34+
public void backtrack(int n, int row) {
35+
if (row >= n) { return; }
36+
for (int col = 0; col < n; col++) {
37+
if (cols[col] == 1 || first[row + col] == 1 || second[row - col + n - 1] == 1) { continue;}
38+
39+
queens[row] = col;
40+
cols[col] = 1;
41+
first[row + col] = 1;
42+
second[row - col + n - 1] = 1;
43+
44+
backtrack(n, row + 1);
45+
if (row == n - 1) {
46+
output.add(addSolution(n));
47+
}
48+
49+
queens[row] = 0;
50+
cols[col] = 0;
51+
first[row + col] = 0;
52+
second[row - col + n - 1] = 0;
53+
}
54+
}
55+
56+
public List<String> addSolution(int n) {
57+
List<String> res = new ArrayList<>();
58+
for (int i = 0; i < n; i++) {
59+
StringBuilder sb = new StringBuilder();
60+
for (int j = 0; j < n; j++) {
61+
if (i == queens[j]) {
62+
sb.append("Q");
63+
} else {
64+
sb.append(".");
65+
}
66+
}
67+
res.add(sb.toString());
68+
}
69+
return res;
70+
}
71+
72+
}

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

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
1+
package io.github.dunwu.algorithm.dfs;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
import java.util.ArrayList;
6+
import java.util.List;
7+
8+
/**
9+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
10+
* @see <a href="https://leetcode-cn.com/problems/n-queens-ii/">52. N皇后II</a>
11+
* @since 2020-07-04
12+
*/
13+
public class N皇后II {
14+
15+
int[] cols;
16+
int[] first;
17+
int[] second;
18+
int[] queens;
19+
List<List<String>> output = new ArrayList<>();
20+
21+
public static void main(String[] args) {
22+
N皇后II demo = new N皇后II();
23+
int result = demo.totalNQueens(4);
24+
Assertions.assertEquals(2, result);
25+
}
26+
27+
public int totalNQueens(int n) {
28+
List<List<String>> lists = solveNQueens(n);
29+
return lists.size();
30+
}
31+
32+
public List<List<String>> solveNQueens(int n) {
33+
queens = new int[n];
34+
cols = new int[n];
35+
first = new int[2 * n];
36+
second = new int[2 * n];
37+
backtrack(n, 0);
38+
return output;
39+
}
40+
41+
public void backtrack(int n, int row) {
42+
if (row >= n) { return; }
43+
for (int col = 0; col < n; col++) {
44+
if (cols[col] == 1 || first[row + col] == 1 || second[row - col + n - 1] == 1) { continue;}
45+
46+
queens[row] = col;
47+
cols[col] = 1;
48+
first[row + col] = 1;
49+
second[row - col + n - 1] = 1;
50+
51+
backtrack(n, row + 1);
52+
if (row == n - 1) {
53+
output.add(addSolution(n));
54+
}
55+
56+
queens[row] = 0;
57+
cols[col] = 0;
58+
first[row + col] = 0;
59+
second[row - col + n - 1] = 0;
60+
}
61+
}
62+
63+
public List<String> addSolution(int n) {
64+
List<String> res = new ArrayList<>();
65+
for (int i = 0; i < n; i++) {
66+
StringBuilder sb = new StringBuilder();
67+
for (int j = 0; j < n; j++) {
68+
if (i == queens[j]) {
69+
sb.append("Q");
70+
} else {
71+
sb.append(".");
72+
}
73+
}
74+
res.add(sb.toString());
75+
}
76+
return res;
77+
}
78+
79+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/search/x的平方根.java‎

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
package io.github.dunwu.algorithm.search;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
import java.math.BigDecimal;
6+
7+
/**
8+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
9+
* @since 2020-07-04
10+
*/
11+
public class x的平方根 {
12+
13+
public static void main(String[] args) {
14+
Assertions.assertEquals(2, mySqrt(4));
15+
Assertions.assertEquals(3, mySqrt(9));
16+
Assertions.assertEquals(2, mySqrt(8)); // 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
17+
Assertions.assertEquals(2.8285f, mySqrt2(8, 4)); // 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
18+
}
19+
20+
// 利用二分法实现求平发根
21+
public static int mySqrt(int x) {
22+
if (x == 0 || x == 1) return x;
23+
int l = 1, r = x, res = x;
24+
while (l <= r) {
25+
int m = (l + r) / 2;
26+
if (m == x / m) {
27+
return m;
28+
} else if (m > x / m) {
29+
r = m - 1;
30+
} else {
31+
l = m + 1;
32+
res = m;
33+
}
34+
}
35+
return res;
36+
}
37+
38+
// 利用二分法实现求浮点数平发根，支持指定精度 e （小数点位数）
39+
public static float mySqrt2(float x, int e) {
40+
if (x == 0 || Float.compare(x, 1f) == 0) return x;
41+
float l = 1f, r = x, res = x;
42+
while (l <= r) {
43+
float m = (l + r) / 2;
44+
if (m == x / m) {
45+
BigDecimal decimal = new BigDecimal(m).setScale(e, BigDecimal.ROUND_UP);
46+
return decimal.floatValue();
47+
} else if (m > x / m) {
48+
r = m;
49+
} else {
50+
l = m;
51+
res = m;
52+
}
53+
}
54+
BigDecimal decimal = new BigDecimal(res).setScale(e, BigDecimal.ROUND_UP);
55+
return decimal.floatValue();
56+
}
57+
58+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/tree/btree/二叉树的层次遍历.java‎

Lines changed: 12 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -3,9 +3,7 @@
33
import io.github.dunwu.algorithm.tree.TreeUtils;
44
import org.junit.jupiter.api.Assertions;
55

6-
import java.util.Arrays;
7-
import java.util.LinkedList;
8-
import java.util.List;
6+
import java.util.*;
97

108
/**
119
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
@@ -24,24 +22,27 @@ public static void main(String[] args) {
2422
Assertions.assertArrayEquals(expectList.toArray(), resultList.toArray());
2523
}
2624

25+
/**
26+
* 基于 BFS 实现二叉树层次遍历。关键在于使用一个队列存储
27+
*/
2728
public static List<List<Integer>> levelOrder(TreeNode root) {
28-
List<List<Integer>> result = new LinkedList<>();
29-
LinkedList<TreeNode> queue = new LinkedList<>();
29+
List<List<Integer>> result = new ArrayList<>();
3030
if (root == null) return result;
31+
32+
Queue<TreeNode> queue = new LinkedList<>();
3133
queue.offer(root);
3234
while (!queue.isEmpty()) {
3335
int size = queue.size();
34-
List<Integer> list = new LinkedList<>();
36+
List<Integer> list = new ArrayList<>();
3537
for (int i = 0; i < size; i++) {
3638
TreeNode node = queue.poll();
37-
if (node != null) {
38-
list.add(node.val);
39-
if (node.left != null) queue.add(node.left);
40-
if (node.right != null) queue.add(node.right);
41-
}
39+
if (node.left != null) queue.offer(node.left);
40+
if (node.right != null) queue.offer(node.right);
41+
list.add(node.val);
4242
}
4343
result.add(list);
4444
}
45+
4546
return result;
4647
}
4748

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/tree/btree/二叉树的最大深度.java‎

Lines changed: 35 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,10 @@
11
package io.github.dunwu.algorithm.tree.btree;
22

33
import io.github.dunwu.algorithm.tree.TreeUtils;
4+
import org.junit.jupiter.api.Assertions;
5+
6+
import java.util.LinkedList;
7+
import java.util.Queue;
48

59
/**
610
* <code>104. 二叉树的最大深度</code> 算法实现
@@ -11,14 +15,40 @@ public class 二叉树的最大深度 {
1115

1216
public static void main(String[] args) {
1317
TreeNode tree = TreeUtils.buildTree(3, 9, 20, null, null, 15, 7);
14-
System.out.println("result = " + maxDepth(tree));
18+
System.out.println("result = " + maxDepthInDFS(tree));
19+
Assertions.assertEquals(3, maxDepthInDFS(tree));
20+
Assertions.assertEquals(3, maxDepthInBFS(tree));
1521
}
1622

17-
public static int maxDepth(TreeNode root) {
23+
// 基于 DFS 实现
24+
// 时间复杂度 O(N)
25+
public static int maxDepthInDFS(TreeNode root) {
1826
if (root == null) return 0;
19-
int left = maxDepth(root.left);
20-
int right = maxDepth(root.right);
21-
return Math.max(left, right) + 1;
27+
return 1 + Math.max(maxDepthInDFS(root.left), maxDepthInDFS(root.right));
28+
}
29+
30+
// 基于 BFS 实现
31+
// 逐层扫描，只要每层有节点，层级数+1
32+
// 时间复杂度 O(N)
33+
public static int maxDepthInBFS(TreeNode root) {
34+
35+
if (root == null) return 0;
36+
37+
int level = 0;
38+
Queue<TreeNode> queue = new LinkedList<>();
39+
queue.offer(root);
40+
while (!queue.isEmpty()) {
41+
level++;
42+
int size = queue.size();
43+
for (int i = 0; i < size; i++) {
44+
TreeNode node = queue.poll();
45+
if (node == null) continue;
46+
if (node.left != null) queue.add(node.left);
47+
if (node.right != null) queue.add(node.right);
48+
}
49+
}
50+
51+
return level;
2252
}
2353

2454
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/tree/btree/二叉树的最小深度.java‎

Lines changed: 41 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,10 @@
11
package io.github.dunwu.algorithm.tree.btree;
22

33
import io.github.dunwu.algorithm.tree.TreeUtils;
4+
import org.junit.jupiter.api.Assertions;
5+
6+
import java.util.LinkedList;
7+
import java.util.Queue;
48

59
/**
610
* <code>二叉树的最小深度</code> 算法实现
@@ -30,18 +34,46 @@ public class 二叉树的最小深度 {
3034

3135
public static void main(String[] args) {
3236
TreeNode tree = TreeUtils.buildTree(3, 9, 20, null, null, 15, 7);
33-
System.out.println("result = " + minDepth(tree));
37+
System.out.println("result = " + minDepthInDFS(tree));
38+
Assertions.assertEquals(2, minDepthInDFS(tree));
39+
Assertions.assertEquals(2, minDepthInBFS(tree));
40+
}
41+
42+
// 基于 DFS 实现
43+
// 时间复杂度 O(N)
44+
public static int minDepthInDFS(TreeNode root) {
45+
if (root == null) return 0;
46+
if (root.left == null) return 1 + minDepthInDFS(root.right);
47+
if (root.right == null) return 1 + minDepthInDFS(root.left);
48+
return 1 + Math.min(minDepthInDFS(root.left), minDepthInDFS(root.right));
3449
}
3550

36-
// -------------------------------------------------------------------------------------------------
51+
// 基于 BFS 实现
52+
// 时间复杂度 O(N)
53+
public static int minDepthInBFS(TreeNode root) {
54+
if (root == null) return 0;
55+
int level = 0;
56+
int min = -1;
57+
Queue<TreeNode> queue = new LinkedList<>();
58+
queue.offer(root);
59+
while (!queue.isEmpty()) {
60+
level++;
61+
int size = queue.size();
62+
for (int i = 0; i < size; i++) {
63+
TreeNode node = queue.poll();
64+
if (node.left == null && node.right == null) {
65+
if (min == -1) {
66+
min = level;
67+
} else {
68+
min = Math.min(min, level);
69+
}
70+
}
71+
if (node.left != null) queue.offer(node.left);
72+
if (node.right != null) queue.offer(node.right);
73+
}
74+
}
3775

38-
// 方法一：递归
39-
public static int minDepth(TreeNode root) {
40-
if (root == null) { return 0; }
41-
int left = minDepth(root.left);
42-
int right = minDepth(root.right);
43-
if (left == 0 || right == 0) { return left + right + 1; }
44-
return Math.min(left, right) + 1;
76+
return min;
4577
}
4678

4779
}

0 commit comments

Comments
 (0)