Skip to content

Commit 99da757

Browse files
author
chenweijie
committed
update
1 parent abccc79 commit 99da757

File tree

103 files changed

+2682
-233
lines changed

Some content is hidden

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

103 files changed

+2682
-233
lines changed

‎src/main/java/com/chen/algorithm/bsearch/AdviceBsearch.java

Lines changed: 126 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,126 @@
1+
package com.chen.algorithm.bsearch;
2+
3+
import org.junit.Test;
4+
5+
/**
6+
* https://blog.csdn.net/bat67/article/details/72049104
7+
*
8+
* @author : chen weijie
9+
* @Date: 2020-07-03 16:45
10+
*/
11+
public class AdviceBsearch {
12+
13+
14+
/**
15+
* 获取第一个等于target的目标，当key=array[mid]时， 往左边一个一个逼近，right = mid -1; 返回left
16+
* @param array
17+
* @param target
18+
* @return
19+
*/
20+
public int bSearch(int[] array, int target) {
21+
22+
int left = 0, right = array.length - 1;
23+
24+
while (right >= left) {
25+
int mid = (right + left) / 2;
26+
if (array[mid] >= target) {
27+
right = mid - 1;
28+
} else {
29+
left = mid + 1;
30+
}
31+
}
32+
if (left < array.length && array[left] == target) {
33+
return left;
34+
}
35+
36+
37+
return -1;
38+
}
39+
40+
41+
42+
43+
44+
45+
46+
/**
47+
* 获取最后一个等于target的目标，当key=array[mid]时， 往右边一个一个逼近，left = mid + 1; 返回right
48+
* @param array
49+
* @param target
50+
* @return
51+
*/
52+
public int bSearch2(int[] array, int target) {
53+
54+
int left = 0, right = array.length - 1;
55+
56+
while (right >= left) {
57+
int mid = (right + left) / 2;
58+
if (array[mid] > target) {
59+
right = mid - 1;
60+
} else {
61+
left = mid + 1;
62+
}
63+
}
64+
65+
if (right >= 0 && array[right] == target) {
66+
return right;
67+
}
68+
69+
return -1;
70+
}
71+
72+
/**
73+
* 获取最后一个小于等于target的目标，当key=array[mid]时， 往右边一个一个逼近，left = mid + 1; 返回right
74+
* @param array
75+
* @param target
76+
* @return
77+
*/
78+
public int bSearch3(int[] array, int target) {
79+
80+
int left = 0, right = array.length - 1;
81+
82+
while (right >= left) {
83+
int mid = (right + left) / 2;
84+
if (array[mid] > target) {
85+
right = mid - 1;
86+
} else {
87+
left = mid + 1;
88+
}
89+
}
90+
return right;
91+
}
92+
93+
/**
94+
* 查找第一个等于或者大于target的目标，当key=array[mid]时， 往左边一个一个逼近，right = mid - 1; 返回left
95+
* @param array
96+
* @param target
97+
* @return
98+
*/
99+
public int bSearch4(int[] array, int target) {
100+
101+
int left = 0, right = array.length - 1;
102+
103+
while (right >= left) {
104+
int mid = (right + left) / 2;
105+
if (array[mid] >= target) {
106+
right = mid - 1;
107+
} else {
108+
left = mid + 1;
109+
}
110+
}
111+
return left;
112+
}
113+
114+
115+
116+
@Test
117+
public void test() {
118+
119+
int[] n = {3, 4, 5, 7, 8, 9, 10};
120+
int res = bSearch4(n, 6);
121+
System.out.println(res);
122+
123+
}
124+
125+
126+
}

‎src/main/java/com/chen/algorithm/bsearch/AdviceBsearch2.java

Lines changed: 125 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,125 @@
1+
package com.chen.algorithm.bsearch;
2+
3+
import org.junit.Test;
4+
5+
/**
6+
* https://blog.csdn.net/bat67/article/details/72049104
7+
*
8+
* @author : chen weijie
9+
* @Date: 2020-07-03 16:45
10+
*/
11+
public class AdviceBsearch2 {
12+
13+
14+
/**
15+
* 获取第一个等于target的目标，当key=array[mid]时， 往左边一个一个逼近，right = mid -1; 返回left
16+
*
17+
* @param array
18+
* @param target
19+
* @return
20+
*/
21+
public int bSearch(int[] array, int target) {
22+
23+
int start = 0, end = array.length - 1;
24+
while (end >= start) {
25+
int mid = start + (end - start) / 2;
26+
27+
if (array[mid] >= target) {
28+
end = mid - 1;
29+
} else {
30+
start = mid + 1;
31+
}
32+
}
33+
34+
if (start < array.length - 1 && array[start] == target) {
35+
return start;
36+
}
37+
return -1;
38+
}
39+
40+
41+
/**
42+
* 获取最后一个等于target的目标，当key=array[mid]时， 往右边一个一个逼近，left = mid + 1; 返回right
43+
*
44+
* @param array
45+
* @param target
46+
* @return
47+
*/
48+
public int bSearch2(int[] array, int target) {
49+
50+
int left = 0, right = array.length - 1;
51+
52+
while (right >= left) {
53+
int mid = left + (right - left) / 2;
54+
if (array[mid] > target) {
55+
right = mid - 1;
56+
} else {
57+
left = mid + 1;
58+
}
59+
}
60+
61+
if (right >= 0 && array[right] == target) {
62+
return right;
63+
}
64+
return -1;
65+
}
66+
67+
/**
68+
* 获取最后一个小于等于target的目标，当key=array[mid]时， 往右边一个一个逼近，left = mid + 1; 返回right
69+
*
70+
* @param array
71+
* @param target
72+
* @return
73+
*/
74+
public int bSearch3(int[] array, int target) {
75+
int left = 0, right = array.length - 1;
76+
while (right >= left) {
77+
int mid = left + (right - left) / 2;
78+
if (array[mid] > target) {
79+
right = mid - 1;
80+
} else {
81+
left = mid + 1;
82+
}
83+
}
84+
85+
return right;
86+
}
87+
88+
/**
89+
* 查找第一个等于或者大于target的目标，当key=array[mid]时， 往左边一个一个逼近，right = mid - 1; 返回left
90+
*
91+
* @param array
92+
* @param target
93+
* @return
94+
*/
95+
public int bSearch4(int[] array, int target) {
96+
97+
int left = 0, right = array.length - 1;
98+
99+
while (right >= left) {
100+
101+
int mid = left + (right - left) / 2;
102+
103+
if (array[mid] >= target) {
104+
right = mid - 1;
105+
} else {
106+
left = mid + 1;
107+
}
108+
}
109+
110+
111+
return left;
112+
}
113+
114+
115+
@Test
116+
public void test() {
117+
118+
int[] n = {3, 4, 5, 7, 8, 9, 10};
119+
int res = bSearch4(n, 6);
120+
System.out.println(res);
121+
122+
}
123+
124+
125+
}

‎src/main/java/com/chen/algorithm/exercise/exercise4/TwoBranchTree.java

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -15,6 +15,7 @@ public static class TreeNode {
1515

1616
TreeNode rightNode;
1717

18+
1819
}
1920

2021

‎src/main/java/com/chen/algorithm/linklist/LinkedHashMapSample.java

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
package com.chen.algorithm.linklist;
2+
3+
import java.util.LinkedHashMap;
4+
import java.util.Map;
5+
6+
/**
7+
* @author : chen weijie
8+
* @Date: 2020-06-01 17:24
9+
*/
10+
public class LinkedHashMapSample {
11+
12+
public static void main(String[] args) {
13+
LinkedHashMap<String, String> accessOrderedMap = new LinkedHashMap<String, String>(16, 0.75F, false) {
14+
// 实现自定义删除策略，否则行为就和普遍 Map 没有区别
15+
@Override
16+
protected boolean removeEldestEntry(Map.Entry<String, String> entry) {
17+
return size() > 3;
18+
}
19+
};
20+
accessOrderedMap.put("Project1", "Valhalla");
21+
accessOrderedMap.put("Project2", "Panama");
22+
accessOrderedMap.put("Project3", "Loom");
23+
accessOrderedMap.forEach((k, v) -> {
24+
System.out.println(k + ":" + v);
25+
});
26+
// 模拟访问
27+
accessOrderedMap.get("Project1");
28+
accessOrderedMap.get("Project2");
29+
accessOrderedMap.get("Project1");
30+
System.out.println("Iterate over should be not affected:");
31+
accessOrderedMap.forEach((k, v) -> {
32+
System.out.println(k + ":" + v);
33+
});
34+
// 触发删除
35+
accessOrderedMap.put("Project4", "Mission Control");
36+
System.out.println("Oldest entry should be removed:");
37+
// 遍历顺序不变
38+
accessOrderedMap.forEach((k, v) -> {
39+
System.out.println(k + ":" + v);
40+
});
41+
}
42+
}

‎src/main/java/com/chen/api/util/map/CacheMap.java renamed to ‎src/main/java/com/chen/algorithm/lru/CacheMap.java

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

33
import java.util.LinkedHashMap;
44
import java.util.Map;

‎src/main/java/com/chen/algorithm/mergeArray/ArraySort.java

Lines changed: 0 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -15,9 +15,7 @@ public static int[] mergeList(int[] a, int[] b) {
1515
int result[];
1616

1717
if (checkSort(a) && checkSort(b)) {
18-
1918
result = new int[a.length + b.length];
20-
2119
//i:用于标示a数组 j：用来标示b数组 k：用来标示传入的数组
2220
int i = 0, j = 0, k = 0;
2321
while (i < a.length && j < b.length) {
@@ -26,7 +24,6 @@ public static int[] mergeList(int[] a, int[] b) {
2624
} else {
2725
result[k++] = b[j++];
2826
}
29-
3027
}
3128

3229
// 后面连个while循环是用来保证两个数组比较完之后剩下的一个数组里的元素能顺利传入

‎src/main/java/com/chen/algorithm/mergeArray/MergeTowLinkList.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -28,7 +28,7 @@ public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
2828

2929
while (l1 != null && l2 != null) {
3030

31-
if (l1.val >= l2.val) {
31+
if (l1.val <= l2.val) {
3232
prev.next = l1;
3333
l1 = l1.next;
3434
} else {

‎src/main/java/com/chen/algorithm/rectangle/Test.java

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
package com.chen.algorithm.rectangle;
2+
3+
/**
4+
* @author : chen weijie
5+
* @Date: 2020-06-26 00:57
6+
*/
7+
public class Test {
8+
9+
@org.junit.Test
10+
public void test() {
11+
int[][] num = new int[4][4];
12+
int n = 4;
13+
int count = 1;
14+
for (int i = 0; i < n; i++) {
15+
for (int j = 0; j < n; j++) {
16+
num[i][j] = count++;
17+
}
18+
}
19+
spiralOrder(num);
20+
}
21+
22+
public int[] spiralOrder(int[][] matrix) {
23+
24+
int left = 0, right = matrix[0].length, ceil = 0, floor = matrix.length;
25+
int[] n = new int[right * floor];
26+
int x = 0;
27+
28+
print(matrix, n, left, right, ceil, floor, x);
29+
return n;
30+
}
31+
32+
public void print(int[][] matrix, int[] n, int left, int right, int ceil, int floor, int x) {
33+
if (left > right || ceil > floor) {
34+
return;
35+
}
36+
37+
for (int i = left; i < right; i++) {
38+
n[x++] = matrix[ceil][i];
39+
}
40+
41+
for (int j = ceil + 1; j < floor; j++) {
42+
n[x++] = matrix[j][right - 1];
43+
}
44+
45+
if (left != right) {
46+
for (int k = right - 2; k >= left; k--) {
47+
n[x++] = matrix[floor - 1][k];
48+
}
49+
}
50+
if (ceil != floor) {
51+
for (int z = floor - 2; z > ceil; z--) {
52+
n[x++] = matrix[z][left];
53+
}
54+
}
55+
56+
left++;
57+
right--;
58+
ceil++;
59+
floor--;
60+
print(matrix, n, left, right, ceil, floor, x);
61+
}
62+
}

0 commit comments

Comments
 (0)