Skip to content

Commit 68cb9c2

Browse files
author
chenweijie
committed
完成递归的方法
1 parent f573aa9 commit 68cb9c2

File tree

9 files changed

+684
-0
lines changed

9 files changed

+684
-0
lines changed

‎src/main/java/com/chen/algorithm/recursion/MergeSort.java

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
package com.chen.algorithm.recursion;
2+
3+
/**
4+
* 归并排序
5+
* <p>
6+
* 　归并算法的中心是归并两个已经有序的数组。归并两个有序数组A和B，就生成了第三个有序数组C。数组C包含数组A和B的所有数据项。
7+
*
8+
* @author : chen weijie
9+
* @Date: 2019-03-25 11:31 PM
10+
*/
11+
public class MergeSort {
12+
13+
14+
public static int[] sort(int[] a, int[] b) {
15+
16+
17+
int aNum = 0, bNum = 0, cNum = 0;
18+
19+
int[] c = new int[a.length + b.length];
20+
21+
while (aNum < a.length && bNum < b.length) {
22+
//将更小的复制给c数组
23+
if (a[aNum] > b[bNum]) {
24+
c[cNum++] = b[bNum++];
25+
} else {
26+
c[cNum++] = a[aNum++];
27+
}
28+
29+
//如果a数组全部赋值到c数组了，但是b数组还有元素，则将b数组剩余元素按顺序全部复制到c数组
30+
while (aNum == a.length && bNum < b.length) {
31+
c[cNum++] = b[bNum++];
32+
}
33+
//如果b数组全部赋值到c数组了，但是a数组还有元素，则将a数组剩余元素按顺序全部复制到c数组
34+
while (bNum == b.length && aNum < a.length) {
35+
c[cNum++] = a[aNum++];
36+
}
37+
}
38+
return c;
39+
}
40+
41+
42+
public static void main(String[] args) {
43+
44+
int[] a = {2, 5, 7, 8, 9, 10};
45+
int[] b = {1, 2, 3, 5, 6, 10, 29};
46+
47+
48+
int[] c = sort(a, b);
49+
50+
for (int i = 0; i < c.length - 1; i++) {
51+
System.out.println(c[i]);
52+
}
53+
System.out.println();
54+
55+
56+
}
57+
58+
59+
}

‎src/main/java/com/chen/algorithm/recursion/Recursion.java

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
package com.chen.algorithm.recursion;
2+
3+
/**
4+
* 求一个数的阶乘
5+
*
6+
* @author : chen weijie
7+
* @Date: 2019-03-14 11:53 PM
8+
*/
9+
public class Recursion {
10+
11+
12+
/**
13+
* for循环处理阶乘
14+
* @param n
15+
* @return
16+
*/
17+
public static int getFactorialFor(int n) {
18+
19+
int temp = 1;
20+
if (n < 0) {
21+
return -1;
22+
} else {
23+
for (int i = 1; i <= n; i++) {
24+
temp = temp * i;
25+
System.out.println("i===" + i + ",temp==" + temp);
26+
}
27+
}
28+
return temp;
29+
}
30+
31+
32+
public static int getFactorial(int n) {
33+
34+
if (n >= 0) {
35+
if (n == 0) {
36+
return 1;
37+
} else {
38+
return n * getFactorial(n - 1);
39+
}
40+
}
41+
42+
return -1;
43+
}
44+
45+
46+
public static void main(String[] args) {
47+
System.out.println(getFactorialFor(3));
48+
System.out.println(getFactorial(0));
49+
}
50+
51+
52+
}

‎src/main/java/com/chen/algorithm/recursion/Search.java

Lines changed: 110 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,110 @@
1+
package com.chen.algorithm.recursion;
2+
3+
/**
4+
* 不用递归的二分查找
5+
*
6+
* @author : chen weijie
7+
* @Date: 2019-03-15 12:23 AM
8+
*/
9+
public class Search {
10+
11+
12+
/**
13+
* 找到目标值返回数组下标，找不到返回-1
14+
*
15+
* @param array
16+
* @param key
17+
* @return
18+
*/
19+
public static int findTwoPoint(int[] array, int key) {
20+
21+
if (array == null || array.length == 0) {
22+
return -1;
23+
}
24+
25+
int min = 0;
26+
int max = array.length - 1;
27+
28+
while (max >= min) {
29+
30+
int mid = (max + min) / 2;
31+
32+
if (key == array[mid]) {
33+
return mid;
34+
}
35+
36+
if (key > array[mid]) {
37+
38+
min = mid + 1;
39+
}
40+
41+
if (key < array[mid]) {
42+
max = mid - 1;
43+
}
44+
}
45+
return -1;
46+
}
47+
48+
49+
/**
50+
* 递归二分查找
51+
*
52+
* @param low 低位
53+
* @param high 高位
54+
* @param array 有序数组
55+
* @param key 要查找的值
56+
* @return
57+
*/
58+
public static int sort(int low, int high, int[] array, int key) {
59+
60+
while (low < high) {
61+
int mid = (low + high) / 2;
62+
63+
if (key == array[mid]) {
64+
65+
return mid;
66+
}
67+
68+
if (key > array[mid]) {
69+
low = mid + 1;
70+
sort(low, high, array, key);
71+
}
72+
73+
if (key < array[mid]) {
74+
high = mid - 1;
75+
sort(low, high, array, key);
76+
}
77+
}
78+
return -1;
79+
}
80+
81+
82+
/**
83+
* 汉诺塔问题
84+
*
85+
* @param dish 盘子个数
86+
* @param from 初始塔数
87+
* @param temp 中介塔数
88+
* @param to 目标塔数
89+
*/
90+
public static void move(int dish, String from, String temp, String to) {
91+
92+
if (dish == 1) {
93+
System.out.println("将盘子" + dish + "从塔座" + from + "移动到目标塔座" + to);
94+
} else {
95+
//A为初始塔，B为目标塔，C为中介塔
96+
move(dish - 1, from, to, temp);
97+
System.out.println("将盘子" + dish + "从塔座" + from + "移动到目标塔座" + to);
98+
//B为初始塔，C为目标塔，A是中介塔
99+
move(dish - 1, temp, from, to);
100+
}
101+
}
102+
103+
104+
public static void main(String[] args) {
105+
106+
move(4,"A","C","B");
107+
}
108+
109+
110+
}

‎src/main/java/com/chen/api/util/event/MethodMonitorEvent.java

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
package com.chen.api.util.event;
2+
3+
import java.util.EventObject;
4+
5+
/**
6+
* 事件监听类型
7+
*
8+
* @author : chen weijie
9+
* @Date: 2019-03-20 11:06 AM
10+
*/
11+
public class MethodMonitorEvent extends EventObject {
12+
13+
14+
/**
15+
* 时间戳，用于记录方法开始执行的时间
16+
*/
17+
public long timestamp;
18+
19+
20+
/**
21+
* Constructs a prototypical Event.
22+
*
23+
* @param source The object on which the Event initially occurred.
24+
* @throws IllegalArgumentException if source is null.
25+
*/
26+
public MethodMonitorEvent(Object source) {
27+
super(source);
28+
}
29+
}

‎src/main/java/com/chen/api/util/event/MethodMonitorEventPublisher.java

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
package com.chen.api.util.event;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
import java.util.concurrent.TimeUnit;
6+
7+
/**
8+
* 事件监听器接口针对不同的事件发布实际提供相应的处理方法定义，最重要的是，
9+
* 其方法只接收MethodMonitorEvent参数，说明这个监听器类只负责监听器对应的事件并进行处理。
10+
* 有了事件和监听器，剩下的就是发布事件，然后让相应的监听器监听并处理。通常情况，我们会有一个
11+
* 事件发布者，它本身作为事件源，在合适的时机，将相应的事件发布给对应的事件监听器：
12+
*
13+
* @author : chen weijie
14+
* @Date: 2019-03-20 11:25 AM
15+
*/
16+
public class MethodMonitorEventPublisher {
17+
18+
19+
private List<MothodMonitorEventListener> listeners = new ArrayList<>();
20+
21+
22+
public void methodMonitor() {
23+
24+
MethodMonitorEvent event = new MethodMonitorEvent(this);
25+
publishEvent("begin", event);
26+
try {
27+
TimeUnit.SECONDS.sleep(5);
28+
} catch (InterruptedException e) {
29+
e.printStackTrace();
30+
}
31+
32+
publishEvent("end", event);
33+
}
34+
35+
36+
private void publishEvent(String status, MethodMonitorEvent event) {
37+
38+
39+
List<MothodMonitorEventListener> copyListeners = new ArrayList<>(listeners);
40+
41+
for (MothodMonitorEventListener listener : copyListeners) {
42+
43+
if ("begin".equals(status)) {
44+
45+
listener.onMethodBegin(event);
46+
} else {
47+
listener.onMethodEnd(event);
48+
49+
}
50+
}
51+
52+
}
53+
54+
55+
public static void main(String[] args) {
56+
57+
MethodMonitorEventPublisher publisher = new MethodMonitorEventPublisher();
58+
publisher.addEventLisner(new MothodMonitorEventListenerImpl());
59+
publisher.methodMonitor();
60+
}
61+
62+
63+
public void addEventLisner(MothodMonitorEventListener eventLister) {
64+
}
65+
66+
public void removeEventLisner(MothodMonitorEventListener eventLister) {
67+
}
68+
69+
public void removeAllEventLisner() {
70+
}
71+
72+
73+
}

‎src/main/java/com/chen/api/util/event/MothodMonitorEventListener.java

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
package com.chen.api.util.event;
2+
3+
import java.util.EventListener;
4+
5+
/**
6+
* 定义事件监听
7+
*
8+
* @author : chen weijie
9+
* @Date: 2019-03-20 11:11 AM
10+
*/
11+
public interface MothodMonitorEventListener extends EventListener {
12+
13+
14+
/**
15+
* 处理方法执行之前发布的时间
16+
*
17+
* @param event
18+
*/
19+
void onMethodBegin(MethodMonitorEvent event);
20+
21+
/**
22+
* 处理方法执行之后发布的事件
23+
*
24+
* @param event
25+
*/
26+
void onMethodEnd(MethodMonitorEvent event);
27+
28+
29+
}

‎src/main/java/com/chen/api/util/event/MothodMonitorEventListenerImpl.java

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
package com.chen.api.util.event;
2+
3+
/**
4+
* 事件监听的实现
5+
*
6+
* @author : chen weijie
7+
* @Date: 2019-03-20 11:15 AM
8+
*/
9+
public class MothodMonitorEventListenerImpl implements MothodMonitorEventListener {
10+
11+
12+
@Override
13+
public void onMethodBegin(MethodMonitorEvent event) {
14+
event.timestamp = System.currentTimeMillis();
15+
}
16+
17+
@Override
18+
public void onMethodEnd(MethodMonitorEvent event) {
19+
20+
long duration = System.currentTimeMillis() - event.timestamp;
21+
System.out.println("耗时：" + duration);
22+
}
23+
24+
}

0 commit comments

Comments
 (0)