Skip to content

Commit 59fc909

Browse files
dunwudunwu
committed
temp
1 parent cc88a5b commit 59fc909

File tree

11 files changed

+362
-276
lines changed

11 files changed

+362
-276
lines changed

‎README.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -42,6 +42,7 @@
4242
- 分治算法
4343
- 回溯算法
4444
- 动态规划
45+
- [算法代码模板](docs/algorithm-template.md)
4546

4647
## 刷题
4748

‎assets/算法.xmind‎

-19.6 KB
Binary file not shown.

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/recursive/反转字符串.java‎

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
package io.github.dunwu.algorithm.recursive;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
/**
6+
* https://leetcode-cn.com/problems/reverse-string/
7+
*
8+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
9+
* @since 2020-07-08
10+
*/
11+
public class 反转字符串 {
12+
13+
public static void main(String[] args) {
14+
char[] str = { 'h', 'e', 'l', 'l', 'o' };
15+
reverseString(str);
16+
Assertions.assertArrayEquals(new char[] { 'o', 'l', 'l', 'e', 'h' }, str);
17+
18+
char[] str2 = { 'H', 'a', 'n', 'n', 'a', 'h' };
19+
reverseString(str2);
20+
Assertions.assertArrayEquals(new char[] { 'h', 'a', 'n', 'n', 'a', 'H' }, str2);
21+
}
22+
23+
public static void reverseString(char[] s) {
24+
if (s == null || s.length == 0) return;
25+
int l = 0, r = s.length - 1;
26+
recursive(s, l, r);
27+
}
28+
29+
private static void recursive(char[] s, int l, int r) {
30+
if (l >= r) return;
31+
char temp = s[l];
32+
s[l] = s[r];
33+
s[r] = temp;
34+
recursive(s, l + 1, r - 1);
35+
}
36+
37+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/tree/TreeNode.java‎

Lines changed: 18 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,7 @@
11
package io.github.dunwu.algorithm.tree;
22

3+
import java.util.Objects;
4+
35
/**
46
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
57
* @since 2020-01-28
@@ -22,9 +24,22 @@ public TreeNode(int val, TreeNode left, TreeNode right) {
2224

2325
@Override
2426
public String toString() {
25-
return "TreeNode{" +
26-
"val=" + val +
27-
'}';
27+
return String.valueOf(val);
28+
}
29+
30+
@Override
31+
public boolean equals(Object o) {
32+
if (this == o) return true;
33+
if (!(o instanceof TreeNode)) return false;
34+
TreeNode treeNode = (TreeNode) o;
35+
return val == treeNode.val &&
36+
Objects.equals(left, treeNode.left) &&
37+
Objects.equals(right, treeNode.right);
38+
}
39+
40+
@Override
41+
public int hashCode() {
42+
return Objects.hash(val, left, right);
2843
}
2944

3045
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/tree/TreeUtils.java‎

Lines changed: 41 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -77,7 +77,7 @@ public static void depthOrderTraverse(TreeNode root) {
7777
}
7878
}
7979

80-
public static List<TreeNode> levelTraverse(TreeNode root) {
80+
public static List<TreeNode> toBfsList(TreeNode root) {
8181
List<TreeNode> list = new ArrayList<>();
8282
if (root == null) {
8383
return list;
@@ -88,10 +88,46 @@ public static List<TreeNode> levelTraverse(TreeNode root) {
8888
while (!queue.isEmpty()) {
8989
TreeNode node = queue.poll();
9090
list.add(node);
91-
if (node.left != null) queue.add(node.left);
92-
if (node.right != null) queue.add(node.right);
91+
if (node == null) continue;
92+
queue.add(node.left);
93+
queue.add(node.right);
9394
}
94-
return list;
95+
96+
// 删除队列尾部的所有 null
97+
int last = list.size() - 1;
98+
while (last > 0 && list.get(last) == null) {
99+
last--;
100+
}
101+
return list.subList(0, last + 1);
102+
}
103+
104+
public static List<Integer> toBfsValueList(TreeNode root) {
105+
List<Integer> list = new ArrayList<>();
106+
if (root == null) {
107+
return list;
108+
}
109+
110+
Queue<TreeNode> queue = new LinkedList<>();
111+
queue.add(root);
112+
while (!queue.isEmpty()) {
113+
TreeNode node = queue.poll();
114+
if (node == null) {
115+
list.add(null);
116+
continue;
117+
} else {
118+
list.add(node.val);
119+
}
120+
121+
queue.add(node.left);
122+
queue.add(node.right);
123+
}
124+
125+
// 删除队列尾部的所有 null
126+
int last = list.size() - 1;
127+
while (last > 0 && list.get(last) == null) {
128+
last--;
129+
}
130+
return list.subList(0, last + 1);
95131
}
96132

97133
public static String rserialize(TreeNode root, String str) {
@@ -171,7 +207,7 @@ public static TreeNode deserialize(String data) {
171207
public static void main(String[] args) {
172208
Integer[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
173209
TreeNode head = TreeUtils.asTree(array);
174-
levelTraverse(head);
210+
toBfsList(head);
175211
}
176212

177213
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/tree/bstree/二叉搜索树中的插入操作.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,7 @@ public class 二叉搜索树中的插入操作 {
1515
public static void main(String[] args) {
1616
TreeNode tree = TreeUtils.asTree(4, 2, 7, 1, 3);
1717
insertIntoBST(tree, 5);
18-
List<TreeNode> treeNodes = TreeUtils.levelTraverse(tree);
18+
List<TreeNode> treeNodes = TreeUtils.toBfsList(tree);
1919
System.out.println(treeNodes);
2020
}
2121

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/tree/btree/从中序与后序遍历序列构造二叉树.java‎

Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
package io.github.dunwu.algorithm.tree.btree;
2+
3+
import io.github.dunwu.algorithm.tree.TreeNode;
4+
import io.github.dunwu.algorithm.tree.TreeUtils;
5+
import org.junit.jupiter.api.Assertions;
6+
7+
import java.util.Arrays;
8+
import java.util.HashMap;
9+
import java.util.List;
10+
import java.util.Map;
11+
12+
/**
13+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
14+
* @since 2020-07-07
15+
*/
16+
public class 从中序与后序遍历序列构造二叉树 {
17+
18+
public static void main(String[] args) {
19+
int[] postorder = { 9, 15, 7, 20, 3 };
20+
int[] inorder = { 9, 3, 15, 20, 7 };
21+
从中序与后序遍历序列构造二叉树 demo = new 从中序与后序遍历序列构造二叉树();
22+
TreeNode root = demo.buildTree(inorder, postorder);
23+
List<Integer> list = TreeUtils.toBfsValueList(root);
24+
System.out.println(list);
25+
Assertions.assertArrayEquals(Arrays.asList(3, 9, 20, null, null, 15, 7).toArray(), list.toArray());
26+
}
27+
28+
private Map<Integer, Integer> map;
29+
30+
public TreeNode backtrack(int[] postorder, int[] inorder, int postLeft, int postRight, int inLeft, int inRight) {
31+
if (postLeft > postRight) return null;
32+
33+
// 后序遍历中的最后一个节点就是根节点
34+
// 在中序遍历中定位根节点
35+
int inRoot = map.get(postorder[postRight]);
36+
37+
// 先把根节点建立出来
38+
TreeNode root = new TreeNode(postorder[postRight]);
39+
40+
// 得到右子树中的节点数目
41+
int rightTreeSize = inRight - inRoot;
42+
43+
// System.out.printf("左子树：postLeft = %s, postRight = %s, inLeft = %s, inRight = %s\n",
44+
// postorder[postLeft], postorder[postRight - rightTreeSize - 1], inorder[inLeft], inorder[inRoot - 1]);
45+
// System.out.printf("右子树：postLeft = %s, postRight = %s, inLeft = %s, inRight = %s\n",
46+
// postorder[postRight - rightTreeSize], postorder[postRight - 1], inorder[inRoot + 1], inorder[inRight]);
47+
48+
// 递归地构造左子树，并连接到根节点
49+
// 先序遍历中「从 左边界+1 开始的 leftTreeSize」个元素就对应了
50+
// 中序遍历中「从 左边界 开始到 根节点定位-1」的元素
51+
root.left = backtrack(postorder, inorder, postLeft, postRight - rightTreeSize - 1, inLeft, inRoot - 1);
52+
53+
// 递归地构造右子树，并连接到根节点
54+
// 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了
55+
// 中序遍历中「从 根节点定位+1 到 右边界」的元素
56+
root.right = backtrack(postorder, inorder, postRight - rightTreeSize, postRight - 1, inRoot + 1, inRight);
57+
58+
return root;
59+
}
60+
61+
public TreeNode buildTree(int[] inorder, int[] postorder) {
62+
if (postorder == null || inorder == null) { return null;}
63+
int n = inorder.length;
64+
map = new HashMap<>(n);
65+
for (int i = 0; i < n; i++) {
66+
map.put(inorder[i], i);
67+
}
68+
return backtrack(postorder, inorder, 0, n - 1, 0, n - 1);
69+
}
70+
71+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/tree/btree/从先序遍历还原二叉树.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -13,7 +13,7 @@ public class 从先序遍历还原二叉树 {
1313

1414
public static void main(String[] args) {
1515
TreeNode result = recoverFromPreorder("1-2--3--4-5--6--7");
16-
System.out.println(TreeUtils.levelTraverse(result));
16+
System.out.println(TreeUtils.toBfsList(result));
1717
}
1818

1919
public static TreeNode recoverFromPreorder(String S) {

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/tree/btree/从前序与中序遍历序列构造二叉树.java‎

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
package io.github.dunwu.algorithm.tree.btree;
2+
3+
import io.github.dunwu.algorithm.tree.TreeNode;
4+
import io.github.dunwu.algorithm.tree.TreeUtils;
5+
import org.junit.jupiter.api.Assertions;
6+
7+
import java.util.Arrays;
8+
import java.util.HashMap;
9+
import java.util.List;
10+
import java.util.Map;
11+
12+
/**
13+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
14+
* @since 2020-07-07
15+
*/
16+
public class 从前序与中序遍历序列构造二叉树 {
17+
18+
public static void main(String[] args) {
19+
int[] preorder = { 3, 9, 20, 15, 7 };
20+
int[] inorder = { 9, 3, 15, 20, 7 };
21+
从前序与中序遍历序列构造二叉树 demo = new 从前序与中序遍历序列构造二叉树();
22+
TreeNode root = demo.buildTree(preorder, inorder);
23+
List<Integer> list = TreeUtils.toBfsValueList(root);
24+
System.out.println(list);
25+
Assertions.assertArrayEquals(Arrays.asList(3, 9, 20, null, null, 15, 7).toArray(), list.toArray());
26+
}
27+
28+
// 中序遍历结构，key 是值，value 是索引
29+
private Map<Integer, Integer> map;
30+
31+
public TreeNode backtrack(int[] preorder, int preLeft, int preRight, int inLeft, int inRight) {
32+
if (preLeft > preRight) {
33+
return null;
34+
}
35+
36+
// 前序遍历中的第一个节点就是根节点
37+
// 在中序遍历中定位根节点
38+
int inRoot = map.get(preorder[preLeft]);
39+
40+
// 先把根节点建立出来
41+
TreeNode root = new TreeNode(preorder[preLeft]);
42+
43+
// 得到左子树中的节点数目
44+
int leftTreeSize = inRoot - inLeft;
45+
46+
// 递归地构造左子树，并连接到根节点
47+
// 先序遍历中「从 左边界+1 开始的 leftTreeSize」个元素就对应了
48+
// 中序遍历中「从 左边界 开始到 根节点定位-1」的元素
49+
root.left = backtrack(preorder, preLeft + 1, preLeft + leftTreeSize, inLeft, inRoot - 1);
50+
51+
// 递归地构造右子树，并连接到根节点
52+
// 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了
53+
// 中序遍历中「从 根节点定位+1 到 右边界」的元素
54+
root.right = backtrack(preorder, preLeft + leftTreeSize + 1, preRight, inRoot + 1, inRight);
55+
return root;
56+
}
57+
58+
public TreeNode buildTree(int[] preorder, int[] inorder) {
59+
if (preorder == null || inorder == null) { return null;}
60+
int n = preorder.length;
61+
// 构造哈希映射，帮助我们快速定位根节点
62+
map = new HashMap<>(n);
63+
for (int i = 0; i < n; i++) {
64+
map.put(inorder[i], i);
65+
}
66+
return backtrack(preorder, 0, n - 1, 0, n - 1);
67+
}
68+
69+
}

0 commit comments

Comments
 (0)