Skip to content

Commit b2a1c09

Browse files
author
chenweijie
committed
update
1 parent de38715 commit b2a1c09

File tree

22 files changed

+621
-114
lines changed

22 files changed

+621
-114
lines changed

‎src/main/java/com/chen/algorithm/sort/standrd/ChoiceSort.java

Lines changed: 7 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -65,17 +65,17 @@ public static int[] sort2(int[] array) {
6565

6666
for (int i = 0; i < array.length; i++) {
6767
int min = i;
68-
for (int j = i + 1; j < array.length; j++) {
69-
if (array[min] > array[j]) {
68+
for (int j = i+1; j <array.length ; j++) {
69+
if (array[j] < array[min]){
7070
min = j;
7171
}
7272
}
73-
if (min != i) {
74-
int temp = array[i];
75-
array[i] = array[min];
76-
array[min] = temp;
77-
}
7873

74+
if (min != i){
75+
int temp = array[min];
76+
array[min] = array[i];
77+
array[i] = temp;
78+
}
7979

8080
}
8181
return array;

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

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -49,13 +49,13 @@ public static void main(String[] args) {
4949
public static void sort2(int[] array) {
5050

5151
for (int i = 1; i < array.length; i++) {
52+
int left = i - 1;
5253
int temp = array[i];
53-
int leftIndex = i - 1;
54-
while (leftIndex >= 0 && array[leftIndex] > temp) {
55-
array[leftIndex + 1] = array[leftIndex];
56-
leftIndex --;
54+
while (left >= 0 && array[left] > temp) {
55+
array[left + 1] = array[left];
56+
left--;
5757
}
58-
array[leftIndex + 1] = temp;
58+
array[left + 1] = temp;
5959
}
6060

6161
}

‎src/main/java/com/chen/algorithm/sort/standrd/QuickSort.java

Lines changed: 37 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -18,7 +18,7 @@ public class QuickSort {
1818
public void quickSort() {
1919

2020
int[] nums = {3, 7, 2, 10, -1, 4};
21-
qSort(nums, 0, nums.length - 1);
21+
sort(0, nums.length - 1, nums);
2222
for (int num : nums) {
2323
System.out.println(num);
2424
}
@@ -36,6 +36,7 @@ private static void qSort(int[] arr, int low, int high) {
3636
}
3737
}
3838

39+
3940
private static int partition(int[] arr, int low, int high) {
4041
//枢轴记录
4142
int pivotValue = arr[low];
@@ -57,4 +58,39 @@ private static int partition(int[] arr, int low, int high) {
5758
return low;
5859
}
5960

61+
62+
public static void sort(int left, int right, int[] nums) {
63+
if (left < right) {
64+
int pivot = partSort(left, right, nums);
65+
sort(left, pivot - 1, nums);
66+
sort(pivot + 1, right, nums);
67+
}
68+
}
69+
70+
71+
public static int partSort(int left, int right, int[] nums) {
72+
73+
int pivotValue = nums[left];
74+
while (left < right) {
75+
while (left < right && pivotValue <= nums[right]) {
76+
right--;
77+
}
78+
nums[left] = nums[right];
79+
80+
while (left < right && pivotValue >= nums[left]) {
81+
left++;
82+
}
83+
nums[right] = nums[left];
84+
85+
}
86+
nums[left] = pivotValue;
87+
return left;
88+
}
89+
90+
6091
}
92+
93+
94+
95+
96+

‎src/main/java/com/chen/algorithm/study/offer/test57/Solution.java

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
package com.chen.algorithm.study.offer.test57;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
6+
/**
7+
* https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/solution/shi-yao-shi-hua-dong-chuang-kou-yi-ji-ru-he-yong-h/
8+
*
9+
* @author : chen weijie
10+
* @Date: 2020-09-27 01:33
11+
*/
12+
public class Solution {
13+
14+
public int[][] findContinuousSequence(int target) {
15+
int i = 1; // 滑动窗口的左边界
16+
int j = 1; // 滑动窗口的右边界
17+
int sum = 0; // 滑动窗口中数字的和
18+
List<int[]> res = new ArrayList<>();
19+
20+
while (i <= target / 2) {
21+
if (sum < target) {
22+
// 右边界向右移动
23+
sum += j;
24+
j++;
25+
} else if (sum > target) {
26+
// 左边界向右移动
27+
sum -= i;
28+
i++;
29+
} else {
30+
// 记录结果
31+
int[] arr = new int[j - i];
32+
for (int k = i; k < j; k++) {
33+
arr[k - i] = k;
34+
}
35+
res.add(arr);
36+
// 左边界向右移动
37+
sum -= i;
38+
i++;
39+
}
40+
}
41+
42+
return res.toArray(new int[res.size()][]);
43+
}
44+
45+
46+
}

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

Lines changed: 13 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -10,17 +10,22 @@ public class Solution {
1010

1111
public int maxArea(int[] height) {
1212

13-
int width = 0;
14-
int high = 0;
1513
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);
14+
15+
int i = 0, j = height.length - 1;
16+
17+
while (i < j) {
18+
19+
int d = Math.min(height[i], height[j]);
20+
max = Math.max((j - i) * d, max);
21+
if (height[i] < height[j]) {
22+
i++;
23+
} else {
24+
j--;
2225
}
2326
}
27+
28+
2429
return max;
2530
}
2631

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

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -23,14 +23,14 @@ public int calculate(String s) {
2323

2424
if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) {
2525

26-
if (c == '+') {
26+
if (sign == '+') {
2727
stack.push(num);
28-
} else if (c == '-') {
28+
} else if (sign == '-') {
2929
stack.push(-num);
30-
} else if (c == '/') {
30+
} else if (sign == '/') {
3131
Integer pre = stack.pop();
3232
stack.push(pre / num);
33-
} else if (c == '*') {
33+
} else if (sign == '*') {
3434
Integer pre = stack.pop();
3535
stack.push(pre * num);
3636
}

‎src/main/java/com/chen/algorithm/study/test227/Solution2.java

Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
package com.chen.algorithm.study.test227;
2+
3+
import org.junit.Test;
4+
5+
import java.util.Stack;
6+
7+
/**
8+
* @author : chen weijie
9+
* @Date: 2020-08-05 15:50
10+
*/
11+
public class Solution2 {
12+
13+
14+
public void vert() {
15+
String s = "458";
16+
int n = 0;
17+
for (char c : s.toCharArray()) {
18+
n = n * 10 + (c - '0');
19+
}
20+
System.out.println(n);
21+
}
22+
23+
24+
public int calculate(String s) {
25+
int res = 0;
26+
char sign = '+';
27+
28+
if (s == null || s.length() == 0){
29+
return 0;
30+
}
31+
int num = 0;
32+
Stack<Integer> stack = new Stack<>();
33+
34+
for (int i = 0; i < s.length(); i++) {
35+
char c = s.charAt(i);
36+
37+
if ( Character.isDigit(c)){
38+
num = num * 10 + (c - '0');
39+
}
40+
41+
if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1){
42+
if (sign == '+') {
43+
stack.push(num);
44+
} else if (sign == '-') {
45+
stack.push(-num);
46+
} else if (sign == '*') {
47+
int pre = stack.pop();
48+
stack.push(pre * num);
49+
} else if (sign == '/') {
50+
int pre = stack.pop();
51+
stack.push(pre / num);
52+
}
53+
sign = c;
54+
num = 0;
55+
}
56+
}
57+
58+
while (!stack.isEmpty()){
59+
res += stack.pop();
60+
}
61+
return res;
62+
}
63+
64+
65+
@Test
66+
public void testCase() {
67+
System.out.println(calculate("-30+5/2 "));
68+
}
69+
70+
71+
}

‎src/main/java/com/chen/algorithm/study/test239/Solution3.java

Lines changed: 88 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,88 @@
1+
package com.chen.algorithm.study.test239;
2+
3+
import org.junit.Test;
4+
5+
import java.util.ArrayDeque;
6+
import java.util.ArrayList;
7+
import java.util.Arrays;
8+
9+
/**
10+
* https://leetcode-cn.com/problems/sliding-window-maximum/solution/dan-diao-dui-lie-by-labuladong/
11+
*
12+
* @author : chen weijie
13+
* @Date: 2020-09-19 19:43
14+
*/
15+
public class Solution3 {
16+
17+
class SlidWindow {
18+
19+
ArrayDeque<Integer> deque;
20+
21+
public SlidWindow(){
22+
deque = new ArrayDeque<>();
23+
}
24+
25+
public Integer getMax (){
26+
return deque.peekFirst();
27+
}
28+
29+
public void push(int val){
30+
31+
while (!deque.isEmpty() && deque.peekLast() < val) {
32+
deque.pollLast();
33+
}
34+
deque.addLast(val);
35+
}
36+
37+
38+
public void pop(int val) {
39+
if (!deque.isEmpty() && deque.peekFirst() == val) {
40+
deque.pollFirst();
41+
}
42+
}
43+
44+
45+
46+
}
47+
48+
public int [] maxSlidingWindow(int [] nums, int k){
49+
50+
if (nums == null || nums.length < k){
51+
return new int[0];
52+
}
53+
ArrayList<Integer> resList = new ArrayList<>();
54+
SlidWindow slidWindow = new SlidWindow();
55+
56+
for (int i = 0; i < nums.length; i++) {
57+
if (i < k-1){
58+
slidWindow.push(nums[i]);
59+
}else {
60+
slidWindow.push(nums[i]);
61+
resList.add(slidWindow.getMax());
62+
slidWindow.pop(nums[i - k + 1]);
63+
}
64+
65+
}
66+
67+
int[] ans = new int[resList.size()];
68+
for (int i = 0; i < ans.length; i++) {
69+
ans[i] = resList.get(i);
70+
}
71+
72+
return ans;
73+
74+
}
75+
76+
@Test
77+
public void testCase() {
78+
int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
79+
int k = 3;
80+
81+
int[] res = maxSlidingWindow(nums, k);
82+
83+
System.out.println(Arrays.toString(res));
84+
85+
86+
}
87+
88+
}

0 commit comments

Comments
 (0)