Skip to content

Commit 76227df

Browse files
gjgb2312-maxgjgb2312-max
committed
备份
1 parent 91282d7 commit 76227df

109 files changed

Lines changed: 2005 additions & 717 deletions

File tree

Some content is hidden

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

‎algorithms/algorithm/src/main/java/cn/lastwhisper/bloomfilter/BloomFilter.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
* 原文：https://www.iteye.com/blog/imtinx-1290636
99
* Long类型元素的布隆过滤器
1010
*/
11-
public class BloomFilter implements Serializable {
11+
class BloomFilter implements Serializable {
1212
private static final long serialVersionUID = 1L;
1313
private static final int ELEM_NUM = 1000; // 欲容纳的元素个数
1414
private static final double PERCENTAGE = 0.001; // 希望的误差率

‎algorithms/algorithm/src/main/java/cn/lastwhisper/consistenthash/ConsistentHash.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@
99
* https://www.iteye.com/blog/imtinx-1290696
1010
*
1111
*/
12-
public class ConsistentHash<T> {
12+
class ConsistentHash<T> {
1313
/**
1414
* 计算使用的hash函数，推荐使用MD5
1515
*/

‎algorithms/algorithm/src/main/java/cn/lastwhisper/gcdlcm/Gcd1.java‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
package cn.lastwhisper.gcdlcm;
2+
3+
import org.junit.Assert;
4+
5+
/**
6+
* 最小公倍数
7+
* @author lastwhisper
8+
* @date 2020/3/12
9+
*/
10+
class Gcd1 {
11+
12+
/**
13+
* (1)辗转相除法
14+
* 有两整数a和b：
15+
* ① a%b得余数c
16+
* ② 若c=0，则b即为两数的最大公约数
17+
* ③ 若c≠0，则a=b，b=c，再回去执行①
18+
*
19+
* 例如求27和15的最大公约数过程为：
20+
* 27÷15 余12
21+
* 15÷12 余3
22+
* 12÷3 余0 因此，3即为最大公约数
23+
*/
24+
public int gcd(int a, int b) {
25+
int m=a,n=b;
26+
if (b > a) {
27+
int temp = a;a = b;b = temp;
28+
}
29+
30+
int c;
31+
while (b != 0) /* 余数不为0，继续相除，直到余数为0 */ {
32+
c = a % b;
33+
a = b;
34+
b = c;
35+
}
36+
return a;// m*n/a最小公倍数
37+
}
38+
39+
public static void main(String[] args) {
40+
Gcd1 main = new Gcd1();
41+
Assert.assertEquals(3, main.gcd(27, 15));
42+
}
43+
}

‎algorithms/algorithm/src/main/java/cn/lastwhisper/gcdlcm/Gcd2.java‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
package cn.lastwhisper.gcdlcm;
2+
3+
import org.junit.Assert;
4+
5+
/**
6+
* 相减法
7+
* @author lastwhisper
8+
* @date 2020/3/12
9+
*/
10+
class Gcd2 {
11+
12+
/**
13+
* ⑵ 相减法
14+
* 有两整数a和b：
15+
* ① 若a>b，则a=a-b
16+
* ② 若a<b，则b=b-a
17+
* ③ 若a=b，则a（或b）即为两数的最大公约数
18+
* ④ 若a≠b，则再回去执行①
19+
* 例如求27和15的最大公约数过程为：
20+
* 27－15＝12( 15>12 )
21+
* 15－12＝3( 12>3 )
22+
* 12－3＝9( 9>3 )
23+
* 9－3＝6( 6>3 )
24+
* 6－3＝3( 3==3 )
25+
*/
26+
public int gcd(int a, int b) {
27+
while (a != b) {
28+
if (a > b) a = a - b;
29+
else b = b - a;
30+
}
31+
return a;
32+
}
33+
34+
public static void main(String[] args) {
35+
Gcd2 main = new Gcd2();
36+
Assert.assertEquals(3, main.gcd(27, 15));
37+
}
38+
}

‎algorithms/algorithm/src/main/java/cn/lastwhisper/gcdlcm/Gcd3.java‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
package cn.lastwhisper.gcdlcm;
2+
3+
import org.junit.Assert;
4+
5+
/**
6+
* 穷举法
7+
* @author lastwhisper
8+
* @date 2020/3/12
9+
*/
10+
class Gcd3 {
11+
12+
// https://www.cnblogs.com/ECJTUACM-873284962/p/6679839.html
13+
public int gcd(int a, int b) {
14+
int t = 0;
15+
for (int i = 1; i <= a; i++)
16+
if (a % i == 0 && b % i == 0) t = i;
17+
return t;
18+
}
19+
20+
public static void main(String[] args) {
21+
Gcd3 main = new Gcd3();
22+
Assert.assertEquals(3, main.gcd(27, 15));
23+
}
24+
}

‎algorithms/algorithm/src/main/java/cn/lastwhisper/sort/QuickSort.java‎

Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
package cn.lastwhisper.sort;
2+
3+
4+
import cn.lastwhisper.util.ArrayUtil;
5+
6+
import java.util.Arrays;
7+
8+
/**
9+
* 快排
10+
*
11+
* 整个快速排序的核心是分区（partition），分区的目的是传入一个数组和选定的一个元素，把所有小于那个元素的其他元素放在左边，大于的放在右边。
12+
* 元素的选择一般有如下几种：
13+
* 永远选择第一个元素
14+
* 永远选择最后一个元素
15+
* 随机选择元素
16+
* 取中间值
17+
* @author lastwhisper
18+
* @date 2020/3/15
19+
*/
20+
public class QuickSort {
21+
22+
23+
public static void sort(int[] arr) {
24+
sort(arr, 0, arr.length - 1);
25+
}
26+
27+
public static void sort(int[] arr, int left, int right) {
28+
if (left >= right) return;
29+
int mid = partition(arr, left, right);
30+
sort(arr, left, mid - 1);
31+
sort(arr, mid + 1, right);
32+
}
33+
34+
/**
35+
* 选取最后的元素，把所有小于那个元素的其他元素放在左边，大于的放在右边
36+
*
37+
* 7, 3, 2, 8, 1, 9, 5, 4, 6 ==》
38+
* 4, 3, 2, 5, 1, 6, 8, 7, 9
39+
*
40+
* @param arr 待排序数组
41+
* @return int 返回数组
42+
*/
43+
private static int partition(int[] arr, int leftBound, int rightBound) {
44+
int i = leftBound;
45+
int pivot = arr[rightBound];
46+
int j = rightBound - 1;//-1是因为最后一个元素以及选择了
47+
while (i <= j) {
48+
while (i <= j && arr[i] <= pivot) {
49+
i++;
50+
}
51+
while (i <= j && arr[j] > pivot) {
52+
j--;
53+
}
54+
if (i < j) swap(arr, i, j);
55+
}
56+
swap(arr, i, rightBound);
57+
System.out.println(Arrays.toString(arr));
58+
return i;
59+
}
60+
61+
private static void swap(int[] arr, int i, int j) {
62+
int temp = arr[i];
63+
arr[i] = arr[j];
64+
arr[j] = temp;
65+
}
66+
67+
public static void main(String[] args) {
68+
int[] arr = {7, 3, 2, 8, 1, 9, 5, 4, 6};
69+
//int arr[] = {7, 3, 2, 8, 1, 9, 5, 4, 6, 0};//为什么left++和right--条件里面要加 left <= right 限定
70+
//int arr[] = {7, 3, 2, 8, 1, 9, 5, 4, 6, 10};
71+
//int arr[] = {7, 3, 2, 6, 8, 1, 9, 5, 4, 6, 10, 6, 6}; // 为什么不取等 arr[right] > pivot
72+
//int arr[] = {4, 6}; //小bug测试 // 为什么while (left <= right)里面要取等
73+
//sort(arr);
74+
sort(ArrayUtil.generateArrByRandom(10));
75+
//sort(arr,0,5);
76+
//System.err.println(Arrays.toString(arr));
77+
}
78+
}

‎algorithms/algorithm/src/main/java/cn/lastwhisper/util/ArrayUtil.java‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
package cn.lastwhisper.util;
2+
3+
/**
4+
* @author cn.lastwhisper
5+
*/
6+
public class ArrayUtil {
7+
8+
public static int[] generateArrByRandom(int max) {
9+
int[] arr = new int[max];
10+
for (int i = 0; i < max; i++) {
11+
arr[i] = (int) (Math.random() * 8000000); // 生成一个[0,8000000) 的一个数
12+
}
13+
return arr;
14+
}
15+
16+
public static int[] generateArrByOrder(int max) {
17+
int[] arr = new int[max];
18+
for (int i = 0; i < max; i++) {
19+
arr[i] = i + 1;
20+
}
21+
22+
return arr;
23+
}
24+
}

‎algorithms/datastructure/src/main/java/cn/lastwhisper/datastructure/sort/QuickSort2.java‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,7 @@
55
*/
66
public class QuickSort2 {
77
public static void main(String[] args) {
8-
int arr[] = {7, 3, 2, 8, 1, 9, 5, 4, 6};
8+
int[] arr = {7, 3, 2, 8, 1, 9, 5, 4, 6};
99
//int arr[] = {7, 3, 2, 8, 1, 9, 5, 4, 6, 0};//为什么left++和right--条件里面要加 left <= right 限定
1010
//int arr[] = {7, 3, 2, 8, 1, 9, 5, 4, 6, 10};
1111
//int arr[] = {7, 3, 2, 6, 8, 1, 9, 5, 4, 6, 10, 6, 6}; // 为什么不取等 arr[right] > pivot
@@ -44,8 +44,8 @@ private static void swap(int[] arr, int i, int j) {
4444
}
4545

4646
private static void print(int[] arr) {
47-
for (int i = 0; i < arr.length; i++) {
48-
System.out.print(arr[i] + "\t");
47+
for (int value : arr) {
48+
System.out.print(value + "\t");
4949
}
5050
}
5151
}

‎algorithms/interview/src/main/java/Main.java‎

Lines changed: 3 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,4 @@
1+
import java.util.Arrays;
12
import java.util.HashSet;
23
import java.util.Scanner;
34

@@ -24,13 +25,11 @@ public static void main(String[] args) {
2425
2526
如果没有该行，则执行第一个in.nextLine()命令时的返回值是int n = in.nextInt()的值*/
2627
sc.nextLine();
27-
HashSet<String> set = new HashSet();
28+
HashSet<String> set = new HashSet<>();
2829
for (int i = 0; i < n; i++) {
2930
String line =sc.nextLine();
3031
String[] arr = line.split(" ");
31-
for (int j = 0; j < arr.length; j++) {
32-
set.add(arr[j]);
33-
}
32+
set.addAll(Arrays.asList(arr));
3433
}
3534
System.out.println("sum:" + set.size());
3635
}

‎algorithms/interview/src/main/java/cn/lastwhisper/interview/dp/整数的分解/Solution.java‎

Lines changed: 0 additions & 45 deletions
This file was deleted.

0 commit comments

Comments
 (0)