Skip to content

Commit 2a3ceba

Browse files
author
chenweijie
committed
代码提交
1 parent 4f4808b commit 2a3ceba

File tree

122 files changed

+4373
-20
lines changed

Some content is hidden

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

122 files changed

+4373
-20
lines changed

‎src/main/java/com/chen/algorithm/sort/InsertSort.java

Lines changed: 7 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -9,20 +9,20 @@ public class InsertSort {
99

1010
public static int[] sort(int[] array) {
1111

12-
int j;
12+
int leftIndex;
1313
//从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
1414
for (int i = 1; i < array.length; i++) {
1515
//记录要插入的数据
1616
int temp = array[i];
17-
j = i;
17+
leftIndex = i - 1;
1818
//从已经排序的序列最右边的开始比较，找到比其小的数
19-
while (j > 0 && temp < array[j - 1]) {
19+
while (leftIndex >= 0 && temp < array[leftIndex]) {
2020
//向后挪动
21-
array[j] = array[j - 1];
22-
j--;
21+
array[leftIndex + 1] = array[leftIndex];
22+
leftIndex--;
2323
}
2424
//存在比其小的数，插入
25-
array[j] = temp;
25+
array[leftIndex + 1] = temp;
2626
}
2727
return array;
2828
}
@@ -36,7 +36,7 @@ public static void display(int[] array) {
3636
}
3737

3838
public static void main(String[] args) {
39-
int[] array = {4, 2, 8, 9, 5, 7, 6, 1, 3};
39+
int[] array = {6,8,1,2,4};
4040
//未排序数组顺序为
4141
System.out.println("未排序数组顺序为：");
4242
display(array);

‎src/main/java/com/chen/algorithm/sort/study/BinInsertSort.java

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
package com.chen.algorithm.sort.study;
2+
3+
/**
4+
* @author : chen weijie
5+
* @Date: 2019-11-27 00:51
6+
*/
7+
public class BinInsertSort {
8+
9+
10+
public static int[] binInsertSort(int[] a) {
11+
12+
int low, mid, high;
13+
int temp;
14+
for (int i = 1; i < a.length; i++) {
15+
temp = a[i];
16+
low = 0;
17+
high = i - 1;
18+
19+
while (low <= high) {
20+
mid = (low + high) / 2;
21+
if (temp < a[mid]) {
22+
high = mid - 1;
23+
} else {
24+
low = mid + 1;
25+
}
26+
}
27+
//将a[low]--a[i-1]的数都想后移一位
28+
for (int j = i; j > low; j--) {
29+
a[j] = a[j - 1];
30+
}
31+
//最后将a[i]插入a[low]
32+
a[low] = temp;
33+
}
34+
return a;
35+
}
36+
37+
public static void main(String[] args) {
38+
int[] array = {6, 8, 1, 2, 4};
39+
//未排序数组顺序为
40+
System.out.println("未排序数组顺序为：");
41+
System.out.println("-----------------------");
42+
binInsertSort(array);
43+
System.out.println("-----------------------");
44+
System.out.println("经过插入排序后的数组顺序为：");
45+
}
46+
47+
48+
}

‎src/main/java/com/chen/algorithm/sort/study/InsertSort.java

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
package com.chen.algorithm.sort.study;
2+
3+
/**
4+
* @author : chen weijie
5+
* @Date: 2019-11-27 00:21
6+
*/
7+
public class InsertSort {
8+
9+
10+
public void solution(int[] array) {
11+
12+
int leftIndex;
13+
//从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
14+
for (int i = 1; i < array.length; i++) {
15+
//记录要插入的数据
16+
int temp = array[i];
17+
leftIndex = i - 1;
18+
//从已经排序的序列最右边的开始比较，找到比其小的数
19+
while (leftIndex >= 0 && temp < array[leftIndex]) {
20+
//向后挪动
21+
array[leftIndex + 1] = array[leftIndex];
22+
leftIndex--;
23+
}
24+
//存在比其小的数，插入
25+
array[leftIndex + 1] = temp;
26+
}
27+
28+
}
29+
30+
31+
}

‎src/main/java/com/chen/algorithm/study/test101/Solution.java

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
package com.chen.algorithm.study.test101;
2+
3+
import org.junit.Test;
4+
5+
/**
6+
* https://leetcode-cn.com/problems/symmetric-tree/solution/dui-cheng-er-cha-shu-by-leetcode/
7+
*
8+
* @author : chen weijie
9+
* @Date: 2019-11-01 00:02
10+
*/
11+
public class Solution {
12+
13+
14+
public boolean isSymmetric(TreeNode root) {
15+
return isMirror(root, root);
16+
}
17+
18+
19+
private boolean isMirror(TreeNode t1, TreeNode t2) {
20+
21+
if ((t1 == null) && (t2 == null)) {
22+
return true;
23+
}
24+
25+
if ((t1 == null) || (t2 == null)) {
26+
return false;
27+
}
28+
29+
return (t1.val == t2.val)
30+
&& (isMirror(t1.left, t2.right))
31+
&& (isMirror(t1.right, t2.left));
32+
}
33+
34+
35+
@Test
36+
public void testCase() {
37+
38+
TreeNode root = new TreeNode(1);
39+
TreeNode left2 = new TreeNode(2);
40+
TreeNode right2 = new TreeNode(2);
41+
42+
43+
TreeNode left3 = new TreeNode(3);
44+
TreeNode right4 = new TreeNode(4);
45+
46+
TreeNode left3_3 = new TreeNode(3);
47+
TreeNode right4_4 = new TreeNode(4);
48+
49+
root.setLeft(left2);
50+
root.setRight(right2);
51+
left2.setLeft(left3);
52+
left2.setRight(right4);
53+
right2.setLeft(right4_4);
54+
right2.setRight(left3_3);
55+
56+
System.out.println(isSymmetric(root));
57+
58+
59+
}
60+
61+
62+
}

‎src/main/java/com/chen/algorithm/study/test101/TreeNode.java

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package com.chen.algorithm.study.test101;
2+
3+
/**
4+
* @author : chen weijie
5+
* @Date: 2019-11-01 00:03
6+
*/
7+
public class TreeNode {
8+
9+
int val;
10+
11+
TreeNode left;
12+
13+
TreeNode right;
14+
15+
public TreeNode() {
16+
}
17+
18+
public TreeNode(int val) {
19+
this.val = val;
20+
}
21+
22+
public int getVal() {
23+
return val;
24+
}
25+
26+
public void setVal(int val) {
27+
this.val = val;
28+
}
29+
30+
public TreeNode getLeft() {
31+
return left;
32+
}
33+
34+
public void setLeft(TreeNode left) {
35+
this.left = left;
36+
}
37+
38+
public TreeNode getRight() {
39+
return right;
40+
}
41+
42+
public void setRight(TreeNode right) {
43+
this.right = right;
44+
}
45+
}

‎src/main/java/com/chen/algorithm/study/test104/Solution.java

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package com.chen.algorithm.study.test104;
2+
3+
import org.junit.Test;
4+
5+
/**
6+
* https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/solution/javasan-chong-jie-fa-xun-huan-ban-bfs-xun-huan-ban/
7+
* <p>
8+
* 深度优先遍历和广度优先遍历
9+
*
10+
* @author : chen weijie
11+
* @Date: 2019-11-01 00:25
12+
*/
13+
public class Solution {
14+
15+
16+
public int maxDepth(TreeNode root) {
17+
return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
18+
}
19+
20+
21+
@Test
22+
public void testCase() {
23+
24+
TreeNode root = new TreeNode(1);
25+
TreeNode left2 = new TreeNode(2);
26+
TreeNode right2 = new TreeNode(2);
27+
28+
29+
TreeNode left3_3 = new TreeNode(3);
30+
TreeNode right4_4 = new TreeNode(4);
31+
32+
root.setLeft(left2);
33+
root.setRight(right2);
34+
35+
right2.setLeft(right4_4);
36+
right2.setRight(left3_3);
37+
38+
System.out.println(maxDepth(root));
39+
40+
41+
}
42+
43+
44+
}

‎src/main/java/com/chen/algorithm/study/test104/TreeNode.java

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package com.chen.algorithm.study.test104;
2+
3+
/**
4+
* @author : chen weijie
5+
* @Date: 2019-11-01 00:03
6+
*/
7+
public class TreeNode {
8+
9+
int val;
10+
11+
TreeNode left;
12+
13+
TreeNode right;
14+
15+
public TreeNode() {
16+
}
17+
18+
public TreeNode(int val) {
19+
this.val = val;
20+
}
21+
22+
public int getVal() {
23+
return val;
24+
}
25+
26+
public void setVal(int val) {
27+
this.val = val;
28+
}
29+
30+
public TreeNode getLeft() {
31+
return left;
32+
}
33+
34+
public void setLeft(TreeNode left) {
35+
this.left = left;
36+
}
37+
38+
public TreeNode getRight() {
39+
return right;
40+
}
41+
42+
public void setRight(TreeNode right) {
43+
this.right = right;
44+
}
45+
}

‎src/main/java/com/chen/algorithm/study/test11/Solution.java

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
package com.chen.algorithm.study.test11;
2+
3+
import org.junit.Test;
4+
5+
/**
6+
* @author : chen weijie
7+
* @Date: 2019-11-08 23:19
8+
*/
9+
public class Solution {
10+
11+
public int maxArea(int[] height) {
12+
13+
int width = 0;
14+
int high = 0;
15+
int max = 0;
16+
for (int i = 0; i < height.length - 1; i++) {
17+
for (int j = i + 1; j < height.length; j++) {
18+
width = j - i;
19+
high = Math.min(height[i], height[j]);
20+
int area = width * high;
21+
max = Math.max(area, max);
22+
}
23+
}
24+
return max;
25+
}
26+
27+
28+
@Test
29+
public void testCase() {
30+
31+
int[] n = {1, 8, 6, 2, 5, 4, 8, 3, 7};
32+
33+
System.out.println(maxArea(n));
34+
35+
}
36+
37+
38+
}

‎src/main/java/com/chen/algorithm/study/test11/Solution1.java

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
package com.chen.algorithm.study.test11;
2+
3+
import org.junit.Test;
4+
5+
/**
6+
* @author : chen weijie
7+
* @Date: 2019-11-08 23:37
8+
*/
9+
public class Solution1 {
10+
11+
12+
public int maxArea(int[] height) {
13+
int maxArea = 0, l = 0, r = height.length - 1;
14+
while (r > l) {
15+
maxArea = Math.max((r - l) * Math.min(height[l], height[r]), maxArea);
16+
if (height[l] < height[r]) {
17+
l++;
18+
} else {
19+
r--;
20+
}
21+
}
22+
return maxArea;
23+
}
24+
25+
26+
@Test
27+
public void testCase() {
28+
29+
int[] n = {1, 8, 6, 2, 5, 4, 8, 3, 7};
30+
31+
System.out.println(maxArea(n));
32+
33+
}
34+
35+
36+
}

0 commit comments

Comments
 (0)