Skip to content

Commit 76424f8

Browse files
author
chenweijie
committed
优化算法
1 parent fbe3027 commit 76424f8

File tree

99 files changed

+2042
-566
lines changed

Some content is hidden

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

99 files changed

+2042
-566
lines changed

‎pom.xml

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,8 @@
1212
<mysql-connector-java.version>5.1.40</mysql-connector-java.version>
1313
<spring.version>4.3.11.RELEASE</spring.version>
1414
<lombok.version>1.16.10</lombok.version>
15+
<mybatis.version>3.2.8</mybatis.version>
16+
<mybatis.spring.version>1.2.0</mybatis.spring.version>
1517
</properties>
1618

1719
<dependencies>
@@ -46,6 +48,17 @@
4648
<version>${spring.version}</version>
4749
</dependency>
4850

51+
<dependency>
52+
<groupId>org.mybatis</groupId>
53+
<artifactId>mybatis</artifactId>
54+
<version>${mybatis.version}</version>
55+
</dependency>
56+
<dependency>
57+
<groupId>org.mybatis</groupId>
58+
<artifactId>mybatis-spring</artifactId>
59+
<version>${mybatis.spring.version}</version>
60+
</dependency>
61+
4962
<dependency>
5063
<groupId>org.springframework</groupId>
5164
<artifactId>spring-aop</artifactId>
@@ -149,6 +162,11 @@
149162
<artifactId>fastjson</artifactId>
150163
<version>1.2.16</version>
151164
</dependency>
165+
<dependency>
166+
<groupId>com.google.guava</groupId>
167+
<artifactId>guava</artifactId>
168+
<version>28.0-jre</version>
169+
</dependency>
152170

153171

154172

‎src/main/java/com/chen/algorithm/recursion/Search.java renamed to ‎src/main/java/com/chen/algorithm/bsearch/Search.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package com.chen.algorithm.recursion;
1+
package com.chen.algorithm.bsearch;
22

33
/**
44
* 不用递归的二分查找

‎src/main/java/com/chen/algorithm/exercise/heap/Heap.java

Lines changed: 115 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,115 @@
1+
package com.chen.algorithm.exercise.heap;
2+
3+
/**
4+
*
5+
* 堆化非常简单，就是顺着节点所在的路径，向上或者向下，对比，然后交换。
6+
*
7+
* 我这里画了一张堆化的过程分解图。我们可以让新插入的节点与父节点对比大小。如果不满足子节点小于等于父节点的大小关系，我们就互换两个节点。一直重复这个过程，直到父子节点之间满足刚说的那种大小关系。
8+
*
9+
* @author : chen weijie
10+
* @Date: 2020-04-19 18:44
11+
*/
12+
public class Heap {
13+
14+
private int[] a; // 数组，从下标1开始存储数据
15+
private int n; // 堆可以存储的最大数据个数
16+
private int count; // 堆中已经存储的数据个数
17+
18+
public Heap(int capacity) {
19+
a = new int[capacity + 1];
20+
n = capacity;
21+
count = 0;
22+
}
23+
24+
public void insert(int data) {
25+
if (count >= n) {
26+
return; // 堆满了
27+
}
28+
++count;
29+
a[count] = data;
30+
int i = count;
31+
while (i / 2 > 0 && a[i] > a[i / 2]) { // 自下往上堆化
32+
swap(a, i, i / 2); // swap()函数作用：交换下标为i和i/2的两个元素
33+
i = i / 2;
34+
}
35+
}
36+
37+
38+
/**
39+
* 我们把最后一个节点放到堆顶，然后利用同样的父子节点对比方法。对于不满足父子节点大小关系的，
40+
* 互换两个节点，并且重复进行这个过程，直到父子节点之间满足大小关系为止。这就是从上往下的堆化方法
41+
*/
42+
public void removeMax() {
43+
if (count == 0) {
44+
// 堆中没有数据
45+
return;
46+
}
47+
a[1] = a[count];
48+
--count;
49+
heapify(a, count, 1);
50+
}
51+
52+
53+
/**
54+
* 建堆
55+
*
56+
* @param a
57+
* @param n
58+
*/
59+
private static void buildHeap(int[] a, int n) {
60+
for (int i = n / 2; i >= 1; --i) {
61+
heapify(a, n, i);
62+
}
63+
}
64+
65+
/**
66+
* 堆排序
67+
*
68+
* @param a
69+
* @param n
70+
*/
71+
public static void sort(int[] a, int n) {
72+
buildHeap(a, n);
73+
int k = n;
74+
while (k > 1) {
75+
swap(a, 1, k);
76+
--k;
77+
heapify(a, k, 1);
78+
}
79+
}
80+
81+
82+
83+
84+
private static void heapify(int[] a, int n, int i) { // 自上往下堆化
85+
while (true) {
86+
int maxPos = i;
87+
if (i * 2 <= n && a[i] < a[i * 2]) {
88+
maxPos = i * 2;
89+
}
90+
if (i * 2 + 1 <= n && a[maxPos] < a[i * 2 + 1]) {
91+
maxPos = i * 2 + 1;
92+
}
93+
if (maxPos == i) {
94+
break;
95+
}
96+
swap(a, i, maxPos);
97+
i = maxPos;
98+
}
99+
}
100+
101+
102+
/**
103+
*
104+
* @param a
105+
* @param i
106+
* @param j
107+
*/
108+
public static void swap(int[] a, int i, int j) {
109+
int tem = a[i];
110+
a[i] = a[j];
111+
a[j] = tem;
112+
}
113+
114+
115+
}

‎src/main/java/com/chen/algorithm/exercise/tree/BinarySearchTree.java

Lines changed: 142 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,142 @@
1+
package com.chen.algorithm.exercise.tree;
2+
3+
/**
4+
* @author : chen weijie
5+
* @Date: 2020-04-18 19:35
6+
*/
7+
public class BinarySearchTree {
8+
9+
Node tree;
10+
11+
/**
12+
* 二叉树查找操作
13+
*
14+
* @param data
15+
* @return
16+
*/
17+
public Node serach(int data) {
18+
19+
Node p = tree;
20+
while (p != null) {
21+
if (data > p.data) {
22+
p = p.right;
23+
} else if (data < p.data) {
24+
p = p.left;
25+
} else {
26+
return p;
27+
}
28+
}
29+
return null;
30+
}
31+
32+
/**
33+
* 二叉树的插入操作
34+
*
35+
* @param data
36+
*/
37+
public void insert(int data) {
38+
if (tree == null) {
39+
tree = new Node(data);
40+
return;
41+
}
42+
43+
Node p = tree;
44+
while (p != null) {
45+
if (data > p.data) {
46+
if (p.right == null) {
47+
p.right = new Node(data);
48+
return;
49+
}
50+
p = p.right;
51+
} else { // data < p.data
52+
if (p.left == null) {
53+
p.left = new Node(data);
54+
return;
55+
}
56+
p = p.left;
57+
}
58+
}
59+
}
60+
61+
62+
/**
63+
* 二叉查找树的查找、插入操作都比较简单易懂，但是它的删除操作就比较复杂了 。针对要删除节点的子节点个数的不同，我们需要分三种情况来处理。
64+
*
65+
* 第一种情况是，如果要删除的节点没有子节点，我们只需要直接将父节点中，指向要删除节点的指针置为null。比如图中的删除节点55。
66+
*
67+
* 第二种情况是，如果要删除的节点只有一个子节点（只有左子节点或者右子节点），我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。比如图中的删除节点13。
68+
*
69+
* 第三种情况是，如果要删除的节点有两个子节点，这就比较复杂了。我们需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，
70+
* 因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，我们可以应用上面两条规则来删除这个最小节点。比如图中的删除节点18。
71+
* @param data
72+
*/
73+
public void delete (int data){
74+
75+
Node p = tree; // p指向要删除的节点，初始化指向根节点
76+
Node pp = null; // pp记录的是p的父节点
77+
while (p != null && p.data != data) {
78+
pp = p;
79+
if (data > p.data) {
80+
p = p.right;
81+
} else {
82+
p = p.left;
83+
}
84+
}
85+
if (p == null) {
86+
return; // 没有找到
87+
}
88+
89+
// 要删除的节点有两个子节点
90+
if (p.left != null && p.right != null) { // 查找右子树中最小节点
91+
Node minP = p.right;
92+
Node minPP = p; // minPP表示minP的父节点
93+
while (minP.left != null) {
94+
minPP = minP;
95+
minP = minP.left;
96+
}
97+
p.data = minP.data; // 将minP的数据替换到p中
98+
p = minP; // 下面就变成了删除minP了
99+
pp = minPP;
100+
}
101+
102+
// 删除节点是叶子节点或者仅有一个子节点
103+
Node child; // p的子节点
104+
if (p.left != null) {
105+
child = p.left;
106+
} else if (p.right != null) {
107+
child = p.right;
108+
} else {
109+
child = null;
110+
}
111+
112+
if (pp == null) {
113+
tree = child; // 删除的是根节点
114+
} else if (pp.left == p) {
115+
pp.left = child;
116+
} else {
117+
pp.right = child;
118+
}
119+
120+
121+
}
122+
123+
124+
125+
126+
private static class Node {
127+
128+
private Integer data;
129+
130+
private Node left;
131+
132+
private Node right;
133+
134+
public Node(int data) {
135+
this.data = data;
136+
}
137+
138+
139+
}
140+
141+
142+
}

‎src/main/java/com/chen/algorithm/exercise/tree/RedBlackTree.java

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
package com.chen.algorithm.exercise.tree;
2+
3+
/**
4+
*
5+
*
6+
* 我们学习数据结构和算法，要学习它的由来、特性、适用的场景以及它能解决的问题
7+
*
8+
* 红黑树是一种平衡二叉查找树。它是为了解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的。红黑树的高度近似log2n，
9+
* 所以它是近似平衡，插入、删除、查找操作的时间复杂度都是O(logn)。
10+
*
11+
* @author : chen weijie
12+
* @Date: 2020-04-18 21:12
13+
*/
14+
public class RedBlackTree {
15+
16+
17+
18+
19+
}

‎src/main/java/com/chen/algorithm/exercise/tree/二叉查找树.jpg

71.6 KB
Loading

‎src/main/java/com/chen/algorithm/permutations/Permutations.java

Lines changed: 14 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -13,33 +13,33 @@ public class Permutations {
1313
//字符数组组成的所有字符串
1414

1515
@Test
16-
public void test(){
16+
public void test() {
1717
//char[] cs = {'a','b','c','d','e'};
18-
char[] cs = {'a','b','c'};
18+
char[] cs = {'a', 'b', 'c'};
1919
int length = cs.length;
20-
recursionSwap(cs,0,length);
20+
recursionSwap(cs, 0, length);
2121
}
2222

23-
public void swap(char[] cs,int index1,int index2){
23+
public void swap(char[] cs, int index1, int index2) {
2424
char temp = cs[index1];
25-
cs[index1]=cs[index2];
26-
cs[index2]=temp;
25+
cs[index1] = cs[index2];
26+
cs[index2] = temp;
2727
}
2828

29-
public void recursionSwap(char[] cs,int start,int length){
30-
if(start>=length-1){
29+
public void recursionSwap(char[] cs, int start, int length) {
30+
if (start >= length - 1) {
3131
print(cs);
3232
return;
3333
}
34-
for(int i=start;i<length;i++){
35-
swap(cs,start,i);
36-
recursionSwap(cs,start+1,length);
37-
swap(cs,start,i);
34+
for (int i = start; i < length; i++) {
35+
swap(cs, start, i);
36+
recursionSwap(cs, start + 1, length);
37+
swap(cs, start, i);
3838
}
3939
}
4040

41-
public void print(char[] cs){
42-
for(int i=0;i<cs.length;i++){
41+
public void print(char[] cs) {
42+
for (int i = 0; i < cs.length; i++) {
4343
System.out.print(cs[i]);
4444
}
4545
System.out.println();

0 commit comments

Comments
 (0)