Skip to content

Commit 7a08126

Browse files
coderbruiscoderbruis
committed
添加文章
1 parent ea76b0a commit 7a08126

13 files changed

Lines changed: 215 additions & 19 deletions

File tree

‎README.md‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,28 @@
11
# AlgorithmsInJava 用Java实现算法和数据结构
22

33
本项目主要用于自己在工作之余记录用Java实现的算法和数据结构的源码；同时还会记录自己刷leetcode的题解思路等；
4+
5+
# leetcode专区
6+
7+
## 1. 数组
8+
9+
题目名称 | 难度 | 地址 | 题解
10+
---|---|---|---
11+
两数之和 | 简单 | [https://leetcode-cn.com/problems/two-sum/](https://leetcode-cn.com/problems/two-sum/) | a
12+
三数之和 | 中等 | [https://leetcode-cn.com/problems/3sum/](https://leetcode-cn.com/problems/3sum/) | a
13+
乘积最大子数组 | 中等 | [https://leetcode-cn.com/problems/maximum-product-subarray/](https://leetcode-cn.com/problems/maximum-product-subarray/) | b
14+
和为K的子数组 | 中等 | [https://leetcode-cn.com/problems/subarray-sum-equals-k/](https://leetcode-cn.com/problems/subarray-sum-equals-k/) | c
15+
16+
数组类总数：4
17+
18+
## 2. 堆栈
19+
20+
题目名称 | 难度 | 地址 | 题解
21+
---|---|---|---
22+
最小栈 | 简单 | [https://leetcode-cn.com/problems/min-stack/](https://leetcode-cn.com/problems/min-stack/) | a
23+
24+
堆栈类总数：1
25+
26+
## 3. 链表
27+
28+

‎notes/algorithms/基础排序算法‎

Lines changed: 145 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,145 @@
1+
前言
2+
3+
- 深入总结八大排序算法以及相关的面试算法题
4+
- 总结其他算法
5+
6+
## 进入算法的世界
7+
8+
#### 1. 冒泡排序
9+
10+
#### 2. 选择排序
11+
12+
#### 3. 插入排序
13+
14+
#### 4. 归并排序
15+
16+
```
17+
//归并排序
18+
aux [n...mid..mid+1..m]
19+
nums [a,b,c,d,e,f,g]
20+
21+
22+
private void merge(int[] nums, int left, int mid, int right) {
23+
int[] aux = Arrays.copyOfRange(nums, left, right + 1);
24+
int i = left, j = mid + 1;
25+
for(int k = left; k <= right; k++) {
26+
if(i > mid) {
27+
nums[k] = aux[j - left];
28+
j++;
29+
} else if(j > right) {
30+
nums[k] = aux[i - left];
31+
i++;
32+
} else if(aux[i - left] < aux[j - left]) {
33+
nums[k] = aux[i - left];
34+
i++;
35+
} else {//aux[i-left] >= aux[j-left]
36+
nums[k] = aux[j - left];
37+
j++;
38+
}
39+
}
40+
}
41+
private void sort(int[] nums, int left, int right) {
42+
if(left >= right) {
43+
return;
44+
}
45+
int mid = (right - left) / 2 + left;
46+
sort(nums, left, mid);
47+
sort(nums, mid+1, right);
48+
merge(nums, left, mid, right);
49+
}
50+
public void sort(int[] nums) {
51+
sort(nums, 0, nums.length - 1);
52+
}
53+
```
54+
55+
56+
57+
#### 5. 快速排序
58+
59+
```
60+
//快速排序
61+
nums [a,b,c,d,e,f,g]
62+
p
63+
j
64+
k
65+
i
66+
private int partition2(int[] nums, int lt, int gt) {
67+
int p = nums[n];
68+
int j = lt;
69+
for(int i = lt; i <= gt; i++) {
70+
if(nums[i] < p) {
71+
swap(nums, ++j, i);
72+
}
73+
}
74+
swap(nums, lt, j);
75+
return j;
76+
}
77+
78+
private int partition(int[] nums, int n, int m) {
79+
int p = nums[n];
80+
int j = n;
81+
int k = m + 1;
82+
int i = n + 1;
83+
while(i < k) {
84+
if(nums[i] < p) {
85+
swap(nums, ++j, i++);
86+
} else if(nums[i] > p) {
87+
swap(nums, --k, i);
88+
} else {// nums[i] == p
89+
i++;
90+
}
91+
}
92+
swap(nums, n, j);
93+
return j;
94+
}
95+
private void swap(int[] nums, int n, int m) {
96+
int tmp = nums[n];
97+
nums[n] = nums[m];
98+
nums[m] = tmp;
99+
}
100+
private void sort(int[] nums, int n, int m) {
101+
if(n > m) {
102+
return;
103+
}
104+
int p = partition(nums, n, m);
105+
sort(nums, n, p - 1);
106+
sort(nums, p + 1, m);
107+
}
108+
public void sort(int[] nums) {
109+
sort(nums, 0, nums.length);
110+
}
111+
```
112+
113+
114+
115+
#### 6. 希尔排序
116+
117+
#### 7. 基数排序
118+
119+
#### 8. 桶排序
120+
121+
122+
123+
124+
125+
####经典排序
126+
127+
| 排序名 | 时间复杂度 | 空间复杂度 | 优势 | 劣势 | 适用场景 | 稳定性 |
128+
| :--: | :------: | :----------: | :--: | :--: | :-----------------------: | :--: |
129+
| 冒泡排序 | O(n^2) | O(1) | | | | 稳定 |
130+
| 插入排序 | O(n^2) | O(1) | | | | 稳定 |
131+
| 归并排序 | O(nlogn) | O(N) | | | | 稳定 |
132+
| 计数排序 | | O(M) | | | 对于用例少的数据，比如对人的年龄排序或者身高排序。 | 稳定 |
133+
| 基数排序 | | O(M) | | | | 稳定 |
134+
| 桶排序 | | | | | | 稳定 |
135+
| 选择排序 | O(n^2) | O(1) | | | | 不稳定 |
136+
| 快速排序 | O(nlogn) | O(logn)~O(n) | | | | 不稳定 |
137+
| 希尔排序 | O(nlogn) | O(1) | | | | 不稳定 |
138+
| 堆排序 | O(nlogn) | O(1) | | | | 不稳定 |
139+
140+
> 除非面试题特别说明，否则认为要排序的数据范围是均匀分布的。
141+
142+
> 快速排序之所以叫快速排序，并不代表它比堆排序和归并排序优良。在最好情况下，它的渐进复杂度与 堆排序和归并排序是相同的。知识快速排序的常量系数比较小而已。
143+
144+
> 类库上提供的排序，并不是某一种算法的实现，而是综合了多种排序的综合排序。当数组比较小时，使用插入排序；当数组较大时，选择快速排序或其他的O(nlogn)的排序。
145+

src/main/java/com/bruis/algorithminjava/algorithm/MaximumProductSubarray.java renamed to src/main/java/com/bruis/algorithminjava/algorithm/array/MaximumProductSubarray.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package com.bruis.algorithminjava.algorithm;
1+
package com.bruis.algorithminjava.algorithm.array;
22

33
/**
44
* @author LuoHaiYang

src/main/java/com/bruis/algorithminjava/algorithm/SubarraySumEqualsK.java renamed to src/main/java/com/bruis/algorithminjava/algorithm/array/SubarraySumEqualsK.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package com.bruis.algorithminjava.algorithm;
1+
package com.bruis.algorithminjava.algorithm.array;
22

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

src/main/java/com/bruis/algorithminjava/algorithm/ThreeSum.java renamed to src/main/java/com/bruis/algorithminjava/algorithm/array/ThreeSum.java

Lines changed: 28 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package com.bruis.algorithminjava.algorithm;
1+
package com.bruis.algorithminjava.algorithm.array;
22

33
import java.util.ArrayList;
44
import java.util.Arrays;
@@ -7,6 +7,9 @@
77

88
/**
99
* @author LuoHaiYang
10+
*
11+
* url: https://leetcode-cn.com/problems/3sum/
12+
*
1013
*/
1114
public class ThreeSum {
1215

@@ -47,24 +50,40 @@ public static List<List<Integer>> threeSum(int[] nums) {
4750
List<List<Integer>> ans = new ArrayList();
4851
int len = nums.length;
4952
//合法性判断
50-
if (nums == null || len < 3) return ans;
53+
if (nums == null || len < 3) {
54+
return ans;
55+
}
5156
//如果手撕算法不能使用工具类进行排序，则要可以使用QuickSort来进行排序；
52-
Arrays.sort(nums); // 排序
57+
// 排序
58+
Arrays.sort(nums);
5359
for (int i = 0; i < len; i++) {
54-
if (nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
55-
if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重
60+
// 如果当前数字大于0，则三数之和一定大于0，所以结束循环
61+
if (nums[i] > 0) {
62+
break;
63+
}
64+
// 去重
65+
if (i > 0 && nums[i] == nums[i - 1]) {
66+
continue;
67+
}
5668
int L = i + 1;
5769
int R = len - 1;
5870
while (L < R) {
5971
int sum = nums[i] + nums[L] + nums[R];
6072
if (sum == 0) {
6173
ans.add(Arrays.asList(nums[i], nums[L], nums[R]));
62-
while (L < R && nums[L] == nums[L + 1]) L++; // 去重
63-
while (L < R && nums[R] == nums[R - 1]) R--; // 去重
74+
while (L < R && nums[L] == nums[L + 1]) {
75+
L++; // 去重
76+
}
77+
while (L < R && nums[R] == nums[R - 1]) {
78+
R--; // 去重
79+
}
80+
L++;
81+
R--;
82+
} else if (sum < 0) {
6483
L++;
84+
} else if (sum > 0) {
6585
R--;
66-
} else if (sum < 0) L++;
67-
else if (sum > 0) R--;
86+
}
6887
}
6988
}
7089
//return ans;

src/main/java/com/bruis/algorithminjava/algorithm/TwoSum.java renamed to src/main/java/com/bruis/algorithminjava/algorithm/array/TwoSum.java

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,13 @@
1-
package com.bruis.algorithminjava.algorithm;
1+
package com.bruis.algorithminjava.algorithm.array;
22

33
import java.util.HashMap;
44
import java.util.Map;
55

66
/**
77
* @author LuoHaiYang
8+
*
9+
* url: https://leetcode-cn.com/problems/two-sum/
10+
*
811
*/
912
public class TwoSum {
1013

src/main/java/com/bruis/algorithminjava/algorithm/MinStack.java renamed to src/main/java/com/bruis/algorithminjava/algorithm/stack/MinStack.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package com.bruis.algorithminjava.algorithm;
1+
package com.bruis.algorithminjava.algorithm.stack;
22

33
import java.util.Stack;
44

src/main/java/com/bruis/algorithminjava/datastructures/MyArray.java renamed to src/main/java/com/bruis/algorithminjava/datastructures/array/MyArray.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package com.bruis.algorithminjava.datastructures;
1+
package com.bruis.algorithminjava.datastructures.array;
22

33
/**
44
* @author LuoHaiYang

src/main/java/com/bruis/algorithminjava/datastructures/MyLoopQueue.java renamed to src/main/java/com/bruis/algorithminjava/datastructures/queue/MyLoopQueue.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package com.bruis.algorithminjava.datastructures;
1+
package com.bruis.algorithminjava.datastructures.queue;
22

33
/**
44
* @author LuoHaiYang

src/main/java/com/bruis/algorithminjava/datastructures/MyQueue.java renamed to src/main/java/com/bruis/algorithminjava/datastructures/queue/MyQueue.java

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,6 @@
1-
package com.bruis.algorithminjava.datastructures;
1+
package com.bruis.algorithminjava.datastructures.queue;
2+
3+
import com.bruis.algorithminjava.datastructures.array.MyArray;
24

35
/**
46
* @author LuoHaiYang

0 commit comments

Comments
 (0)