Skip to content

Commit cb702e0

Browse files
CodeWater404CodeWater404
committed
add springboot
1 parent c1fffd9 commit cb702e0

514 files changed

Lines changed: 46733 additions & 41039 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.

‎Algorithm/src/acwing/basic/chapter1/_2816JudgementSubquence.java‎

Lines changed: 13 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -14,28 +14,29 @@ public class _2816JudgementSubquence {
1414
public static int N = 100010;
1515
public static int[] a = new int[N];
1616
public static int[] b = new int[N];
17-
public static int n , m ;
17+
public static int n, m;
1818

1919
public static void main(String[] args) throws IOException {
20-
BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
21-
String[] str = br.readLine().split( " " );
22-
n = Integer.parseInt( str[0] ) ; m = Integer.parseInt( str[1] );
23-
str = br.readLine().split( " " );
24-
for( int i = 0 ; i < n ; i++ ) a[i] = Integer.parseInt( str[i] );
20+
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
21+
String[] str = br.readLine().split(" ");
22+
n = Integer.parseInt(str[0]);
23+
m = Integer.parseInt(str[1]);
2524
str = br.readLine().split(" ");
26-
for( int i = 0 ; i < m ; i++ )b[i] = Integer.parseInt( str[i] );
27-
int i = 0 , j = 0 ;
25+
for (int i = 0; i < n; i++) a[i] = Integer.parseInt(str[i]);
26+
str = br.readLine().split(" ");
27+
for (int i = 0; i < m; i++) b[i] = Integer.parseInt(str[i]);
28+
int i = 0, j = 0;
2829
// i是扫描小的序列a ； j是扫描大的序列b
29-
while( i < n && j < m ){
30+
while (i < n && j < m) {
3031
// 相等的时候，i才走。因为要判断a是否在b中。
31-
if( a[i] == b[j] ) i++;
32+
if (a[i] == b[j]) i++;
3233
/*注意这里b的指针，不管ij是否相等都要往右移动，如果加个else就是
3334
不等才移相等不移，这就错了，因为一个元素不能复用。等不等都得移
3435
*/
3536
j++;
3637
}
3738
//i=n的时候，说明子序列a已经全部在b中了;如果退出while另外一种j=m，说明a不在b中
38-
if( i == n )System.out.println( "Yes" );
39-
else System.out.println( "No" );
39+
if (i == n) System.out.println("Yes");
40+
else System.out.println("No");
4041
}
4142
}

‎Algorithm/src/acwing/basic/chapter1/_785QuickSort.java‎

Lines changed: 20 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -9,19 +9,19 @@
99
* @create ：2022-03-04-17:38
1010
* @Function Description ：快速排序
1111
* 给定你一个长度为 n 的整数数列。
12-
*
12+
* <p>
1313
* 请你使用快速排序对这个数列按照从小到大进行排序。
14-
*
14+
* <p>
1515
* 并将排好序的数列按顺序输出。
16-
*
16+
* <p>
1717
* 输入格式
1818
* 输入共两行，第一行包含整数 n。
19-
*
19+
* <p>
2020
* 第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。
21-
*
21+
* <p>
2222
* 输出格式
2323
* 输出共一行，包含 n 个整数，表示排好序的数列。
24-
*
24+
* <p>
2525
* 数据范围
2626
* 1≤n≤100000
2727
* 输入样例：
@@ -33,8 +33,9 @@
3333
public class _785QuickSort {
3434
public static int N = 100010;
3535
public static int[] q = new int[N];
36-
// public static int[N] q;
36+
// public static int[N] q;
3737
public static int n;
38+
3839
public static void main(String[] args) throws IOException {
3940
// Scanner sc = new Scanner(System.in);
4041
// n = sc.nextInt();
@@ -51,37 +52,37 @@ public static void main(String[] args) throws IOException {
5152
int n = Integer.parseInt(reader.readLine());
5253
int[] arr = new int[n];
5354
String[] strs = reader.readLine().split(" ");
54-
for(int i = 0; i < n; i++){
55+
for (int i = 0; i < n; i++) {
5556
arr[i] = Integer.parseInt(strs[i]);
5657
}
5758
quick_sort(arr, 0, n - 1);
58-
for(int i = 0; i < arr.length; i++){
59+
for (int i = 0; i < arr.length; i++) {
5960
System.out.print(arr[i] + " ");
6061
}
6162
reader.close();
6263
}
6364

64-
// 快速排序:其实参数数组写不写无所谓，因为已经静态了；如果是定义的局部数组还是需要写一下然后传入
65-
public static void quick_sort( int[] q , int l , int r){
65+
// 快速排序:其实参数数组写不写无所谓，因为已经静态了；如果是定义的局部数组还是需要写一下然后传入
66+
public static void quick_sort(int[] q, int l, int r) {
6667
//当单个区间长度为1的时候就可以不用再分了
67-
if( l >= r ) return ;
68+
if (l >= r) return;
6869
//定义2个左右遍历指针指针i j 分界点x(取区间中点) （下面的额i+j可以换成l+r，其实不影响）
69-
int i = l - 1 , j = r + 1 , x = q[(i + j ) / 2];
70-
while(i < j){
70+
int i = l - 1, j = r + 1, x = q[(i + j) / 2];
71+
while (i < j) {
7172
//当当前指针所指的元素小于分界点的时候，i往后走
72-
do i++; while( q[i] < x );
73+
do i++; while (q[i] < x);
7374
//当当前指针所指的元素大于分界点的时候，j往前走
74-
do j--; while( q[j] > x );
75+
do j--; while (q[j] > x);
7576
//如果两个指针没有相遇过，交换2个位置的元素
7677
//交换，也不知道java有没有提供直接交换的方法（C++有swap）
77-
if(i < j ) {
78+
if (i < j) {
7879
int temp = q[i];
7980
q[i] = q[j];
8081
q[j] = temp;
8182
}
8283
}
8384
//递归左右区间，下面的j不能换成i，退出while后，ij的值不一定相等！！！！！！也有i>j的情况画个图可以理解这个区间问题
84-
quick_sort( q, l , j );
85-
quick_sort( q , j + 1 , r );
85+
quick_sort(q, l, j);
86+
quick_sort(q, j + 1, r);
8687
}
8788
}

‎Algorithm/src/acwing/basic/chapter1/_786NumberK.java‎

Lines changed: 20 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -9,15 +9,15 @@
99
* https://www.acwing.com/problem/content/788/
1010
* 快排每次确定一个最小的数，所以可以用快排优化一下即可。
1111
* 给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。
12-
*
12+
* <p>
1313
* 输入格式
1414
* 第一行包含两个整数 n 和 k。
15-
*
15+
* <p>
1616
* 第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整数数列。
17-
*
17+
* <p>
1818
* 输出格式
1919
* 输出一个整数，表示数列的第 k 小数。
20-
*
20+
* <p>
2121
* 数据范围
2222
* 1≤n≤100000,
2323
* 1≤k≤n
@@ -29,9 +29,10 @@
2929
*/
3030
public class _786NumberK {
3131
public static int N = 100010;
32-
public static int n , k;
32+
public static int n, k;
3333
public static int[] q = new int[N];
34-
public static void main(String[] args) {
34+
35+
public static void main(String[] args) {
3536

3637
// 用缓冲流490ms
3738
/*BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
@@ -46,30 +47,30 @@ public static void main(String[] args) {
4647
Scanner sc = new Scanner(System.in);
4748
n = sc.nextInt();
4849
k = sc.nextInt();
49-
for( int i = 0 ; i < n ; i++ ){
50+
for (int i = 0; i < n; i++) {
5051
q[i] = sc.nextInt();
5152
}
52-
System.out.println(quickSort(q , 0 , n - 1 , k));
53+
System.out.println(quickSort(q, 0, n - 1, k));
5354
}
5455

55-
// 其实参数数组写不写无所谓，因为已经静态了；如果是定义的局部数组还是需要写一下然后传入
56-
public static int quickSort(int[] arr , int l , int r , int k){
56+
// 其实参数数组写不写无所谓，因为已经静态了；如果是定义的局部数组还是需要写一下然后传入
57+
public static int quickSort(int[] arr, int l, int r, int k) {
5758
//确定左边最小的结果返回
58-
if( l >= r ) return q[l] ;
59-
int i = l - 1 , j = r + 1 , x = q[(l + r ) / 2];
60-
while( i < j ){
61-
do i++ ; while(q[i] < x);
62-
do j-- ; while( q[j] > x ) ;
63-
if( i < j ){
59+
if (l >= r) return q[l];
60+
int i = l - 1, j = r + 1, x = q[(l + r) / 2];
61+
while (i < j) {
62+
do i++; while (q[i] < x);
63+
do j--; while (q[j] > x);
64+
if (i < j) {
6465
int temp = q[i];
6566
q[i] = q[j];
6667
q[j] = temp;
6768
}
6869
}
6970
//退出while时，排完一趟，可以确定出一个位置的数，k小于左边长度，说明在左区间内，
7071
// 继续递归左边区间；否则就在右边区间，注意右边区间传k时要减掉左边区间的长度
71-
if( k <= j - l + 1) return quickSort( q , l , j , k );
72-
else return quickSort( q , j + 1 , r , k - (j - l + 1) );
73-
72+
if (k <= j - l + 1) return quickSort(q, l, j, k);
73+
else return quickSort(q, j + 1, r, k - (j - l + 1));
74+
7475
}
7576
}

‎Algorithm/src/acwing/basic/chapter1/_787MergeSort.java‎

Lines changed: 30 additions & 30 deletions
Original file line numberDiff line numberDiff line change
@@ -8,19 +8,19 @@
88
* @create ：2022-03-10-11:13
99
* @Function Description ：归并排序
1010
* 给定你一个长度为 n 的整数数列。
11-
*
11+
* <p>
1212
* 请你使用归并排序对这个数列按照从小到大进行排序。
13-
*
13+
* <p>
1414
* 并将排好序的数列按顺序输出。
15-
*
15+
* <p>
1616
* 输入格式
1717
* 输入共两行，第一行包含整数 n。
18-
*
18+
* <p>
1919
* 第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。
20-
*
20+
* <p>
2121
* 输出格式
2222
* 输出共一行，包含 n 个整数，表示排好序的数列。
23-
*
23+
* <p>
2424
* 数据范围
2525
* 1≤n≤100000
2626
* 输入样例：
@@ -55,43 +55,43 @@ public class _787MergeSort {
5555
// }
5656

5757
// 其余：另外一种去掉传数组的,其实差不多，可能考虑到语言性能方面的原因？
58-
public static void merge_sort(int l,int r){
59-
if(l==r) return;
60-
61-
int mid=l+r>>1;
62-
merge_sort(l,mid);
63-
merge_sort(mid+1,r);
64-
65-
int[] h=new int[r-l+1];
66-
int idx=0;
67-
int i=l;
68-
int j=mid+1;
69-
while(i<=mid&&j<=r){
70-
if(q[i]<=q[j]) h[idx++]=q[i++];
71-
else h[idx++]=q[j++];
58+
public static void merge_sort(int l, int r) {
59+
if (l == r) return;
60+
61+
int mid = l + r >> 1;
62+
merge_sort(l, mid);
63+
merge_sort(mid + 1, r);
64+
65+
int[] h = new int[r - l + 1];
66+
int idx = 0;
67+
int i = l;
68+
int j = mid + 1;
69+
while (i <= mid && j <= r) {
70+
if (q[i] <= q[j]) h[idx++] = q[i++];
71+
else h[idx++] = q[j++];
7272
}
7373

74-
while(i<=mid) h[idx++]=q[i++];
75-
while(j<=r) h[idx++]=q[j++];
74+
while (i <= mid) h[idx++] = q[i++];
75+
while (j <= r) h[idx++] = q[j++];
7676

77-
for(int k=0;k<idx;k++){
78-
q[k+l]=h[k];
77+
for (int k = 0; k < idx; k++) {
78+
q[k + l] = h[k];
7979
}
8080
}
8181

8282

8383
public static void main(String[] args) throws Exception {
84-
BufferedReader br = new BufferedReader( new InputStreamReader( System.in) );
85-
int n = Integer.parseInt( br.readLine() );
84+
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
85+
int n = Integer.parseInt(br.readLine());
8686
String[] str = br.readLine().split(" ");
8787

88-
for( int i = 0 ; i < n ; i++ ) q[i] = Integer.parseInt( str[i] );
88+
for (int i = 0; i < n; i++) q[i] = Integer.parseInt(str[i]);
8989

9090
// merge_sort( q , 0 , n - 1 );
91-
merge_sort( 0 , n - 1 );
91+
merge_sort(0, n - 1);
9292
// 不能用增强for，不然会输出后面多余的
93-
for( int i = 0 ; i < n ; i++ ) System.out.print( q[i] + " " );
93+
for (int i = 0; i < n; i++) System.out.print(q[i] + " ");
94+
9495

95-
9696
}
9797
}

‎Algorithm/src/acwing/basic/chapter1/_788ReverseOrderNumber.java‎

Lines changed: 20 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -9,21 +9,21 @@
99
* @create ：2022-03-14-10:17
1010
* @Function Description ：逆序对的数量（归并）
1111
* 给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。
12-
*
12+
* <p>
1313
* 逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。
14-
*
14+
* <p>
1515
* 输入格式
1616
* 第一行包含整数 n，表示数列的长度。
17-
*
17+
* <p>
1818
* 第二行包含 n 个整数，表示整个数列。
19-
*
19+
* <p>
2020
* 输出格式
2121
* 输出一个整数，表示逆序对的个数。
22-
*
22+
* <p>
2323
* 数据范围
2424
* 1≤n≤100000，
2525
* 数列中的元素的取值范围 [1,109]。
26-
*
26+
* <p>
2727
* 输入样例：
2828
* 6
2929
* 2 3 4 5 6 1
@@ -37,35 +37,35 @@ public class _788ReverseOrderNumber {
3737
public static int n;
3838

3939
public static void main(String[] args) throws IOException {
40-
BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
40+
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
4141
String[] str = br.readLine().split(" ");
4242

43-
n = Integer.parseInt( str[0] );
43+
n = Integer.parseInt(str[0]);
4444
str = br.readLine().split(" ");
45-
for( int i = 0 ; i < n ; i++ ) q[i] = Integer.parseInt( str[i] );
45+
for (int i = 0; i < n; i++) q[i] = Integer.parseInt(str[i]);
4646

47-
System.out.println( mergeSort( q , 0 , n - 1 ) );
47+
System.out.println(mergeSort(q, 0, n - 1));
4848

4949
}
5050

51-
public static long mergeSort( int[] q , int l , int r ){
52-
if( l >= r ) return 0 ;
51+
public static long mergeSort(int[] q, int l, int r) {
52+
if (l >= r) return 0;
5353
int mid = l + r >> 1;
5454
// res答案必须定义成long，不然过不了
55-
long res = mergeSort( q , l , mid ) + mergeSort( q , mid + 1 , r );
56-
int k = 0 , i = l , j = mid + 1;
57-
while( i <= mid && j <= r ){
58-
if( q[i] <= q[j] ) temp[k++] = q[i++];
59-
else{
55+
long res = mergeSort(q, l, mid) + mergeSort(q, mid + 1, r);
56+
int k = 0, i = l, j = mid + 1;
57+
while (i <= mid && j <= r) {
58+
if (q[i] <= q[j]) temp[k++] = q[i++];
59+
else {
6060
res += mid - i + 1;
6161
temp[k++] = q[j++];
6262
}
6363
}
6464

65-
while( i <= mid ) temp[k++] = q[i++];
66-
while( j <= r ) temp[k++] = q[j++];
65+
while (i <= mid) temp[k++] = q[i++];
66+
while (j <= r) temp[k++] = q[j++];
6767

68-
for( i = l , j = 0 ; i <= r ; i++ , j++ ) q[i] = temp[j];
68+
for (i = l, j = 0; i <= r; i++, j++) q[i] = temp[j];
6969
return res;
7070
}
7171
}

0 commit comments

Comments
 (0)