AcWing刷题

# 1.基础算法

# 1.排序

# 785.快速排序

给定你一个长度为 n 的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在 1∼1091∼109 范围内），表示整个数列。

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

数据范围

1≤n≤100000

输入样例：

5
3 1 2 4 5

1
2

输出样例：

1 2 3 4 5

package com.ep.AcWing;

import java.sql.SQLOutput;
import java.util.Arrays;
import java.util.Scanner;

/***
 * @author dep
 * @version 1.0
 * @date 2023-02-24 11:42
 */
public class AcWing785_快速排序 {

    public static void main(String[] args) {
        int n;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        // 30
        // 128 294 133 295 175 8 232 248 241 164 11 60 238 133 291 116 6 67 98 67 196 260 181 160 83 160 90 153 233 216
        quick_sort2(nums, 0, n - 1);
//        System.out.println(Arrays.toString(nums));
        for (int i = 0; i < n; i++) {
            if (i != n-1) {
                System.out.print(nums[i] + " ");
            }else {
                System.out.println(nums[i]);
            }
        }
    }
    // 平均复杂度o(nlogn),超出时间限制
    public static void quick_sort(int[] arr, int left, int right) {
        if (right >= left) {
            // 保存基数
            int basic = arr[left];
            //定义左右指针
            int i = left;
            int j = right;
            while (i < j) { // 左指针小于右指针
                while (i < j && basic < arr[j]) { // 操作右指针找到小于基数的下标
                    j--;
                }
                if (i < j) {
                    arr[i] = arr[j]; // 将右指针对应小于基数的值放在左指针的位置
                    i++; // 左指针自加
                }
                while (i < j && basic > arr[i]) { // 操作左指针找到大于基数的下标
                    i++;
                }
                if (i < j) {
                    arr[j] = arr[i]; // 将左指针大于基数的值放在右指针的位置
                    j--;
                }
            }
            arr[i] = basic; // 将基数放在指针重合的位置
            quick_sort(arr, left, i - 1); // 对左半部分进行快速排序
            quick_sort(arr, i+1, right); // 对右半部分进行快速排序
        }
    }
    // 平均复杂度o(nlogn)
    public static void quick_sort2(int[] arr, int l, int r) {
        if(l >= r){
            return;
        }
        int x = arr[l + r >> 1],i = l - 1,j = r + 1;
        while(i < j){
            do{
                i++;
            }while(arr[i] < x);
            do{
                j--;
            }while(arr[j] > x);
            if(i < j){
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
        quick_sort(arr,l,j);
        quick_sort(arr,j+1,r);
    }
    public static void quickSort(int[] arr, int l, int r){
        if (l < r) {
            int q = partiotion(arr,l, r);
            quickSort(arr,l,q-1); // 左侧快速排序
            quickSort(arr,q+1,r); // 右侧快速排序
        }
    }
    public static int partiotion(int[] arr, int l, int r) {
        int pivot = arr[l];
        int left = l + 1; // 左指针
        int right = r; // 右指针
        while (left <= right) {
            if (left <= right && arr[left] <= pivot) left++;
            if (left <= right && arr[right] > pivot) right--;
            if (left < right) {
                swap(arr,left,right);
            }
        }
        // 循环退出时，right指向的最后一个小于等于主元的位置，也就是主元应该呆的位置
        swap(arr, l, right);
        return right;
    }
    /***
     * 交换数组的值
     * @param arr
     * @param m
     * @param n
     */
    public static void swap (int[] arr, int m , int n) {
        int num = arr[m];
        arr[m] = arr[n];
        arr[n] = num;
    }

    /***
     * 打印数组
     * @param arr
     */
    public static void print(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            if (i != n-1) {
                System.out.print(arr[i] + " ");
            }else {
                System.out.println(arr[i]);
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

# 786.第k个数

给定一个长度为 n的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k个数。

输入格式

第一行包含两个整数 n 和 k。

第二行包含 n个整数（所有整数均在 1∼1091∼109 范围内），表示整数数列。

输出格式

输出一个整数，表示数列的第 k 小数。

数据范围

1≤n≤100000, 1≤k≤n1

输入样例：

5 3
2 4 1 5 3

1
2

输出样例：

package com.ep.AcWing;

import java.io.IOException;
import java.util.Scanner;

/***
 * @author dep
 * @version 1.0
 * @date 2023-03-02 12:21
 */
public class AcWing786_第k个数 {
    static int[] nums;
    static int k;
    public static void main(String[] args) throws IOException {
        int n;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        k = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        quick_sort(nums,0, nums.length - 1);
    }
    public static void quick_sort(int[] arr, int l, int r) {
        if(l == r){
            System.out.println(arr[l]);
            return;
        }
        int x = arr[l + r >> 1],i = l - 1,j = r + 1;
        while(i < j){
            while (arr[++i] < x);
            while (arr[--j] > x);
            if(i < j) swap(arr,i, j);
        }
        if(j+1 >= k){
            quick_sort(arr,l,j);
        }else{
            quick_sort(arr,j+1,r);
        }
    }

    /***
     * 交换数组的值
     * @param arr
     * @param m
     * @param n
     */
    public static void swap (int[] arr, int m , int n) {
        int num = arr[m];
        arr[m] = arr[n];
        arr[n] = num;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

# 2.归并排序

# 787.归并排序

给定你一个长度为 n 的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。

第二行包含 n个整数（所有整数均在 1∼1091∼109 范围内），表示整个数列。

输出格式

输出共一行，包含 n个整数，表示排好序的数列。

数据范围

1≤n≤100000

输入样例：

5
3 1 2 4 5

1
2

输出样例：

1 2 3 4 5

package com.ep.AcWing;

import java.util.Scanner;

/***
 * @author dep
 * @version 1.0
 * @date 2023-03-02 14:19
 */
public class AcWing787_归并排序 {
    public static void main(String[] args) {
        int n;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        merge_sort(nums,0, n-1);
        print(nums);

    }
    public static void merge_sort(int[] arr, int l, int r) {
        if (l >= r) return;
        int mid =  l + r >> 1;
        merge_sort(arr,l, mid);
        merge_sort(arr, mid+1, r);
        int k = 0, i = l, j = mid +1 ;
        int[] temp = new int[r - l + 1];
        while (i <= mid && j <= r) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= r) {
            temp[k++] = arr[j++];
        }
        for (int m = 0; m < k; m++) {
            arr[m+l] = temp[m];
        }
    }
    public static void print(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            if (i != n-1) {
                System.out.print(arr[i] + " ");
            }else {
                System.out.println(arr[i]);
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

# 788.逆序对的数量

给定一个长度为 n的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。

# 输入格式

第一行包含整数 n，表示数列的长度。

第二行包含 n个整数，表示整个数列。

# 输出格式

输出一个整数，表示逆序对的个数。

# 数据范围

1≤n≤100000，数列中的元素的取值范围 [1,109][1,109]。

# 输入样例：

6
2 3 4 5 6 1

1
2

# 输出样例：

package com.ep.AcWing;

import java.util.Scanner;

/***
 * @author dep
 * @version 1.0
 * @date 2023-03-03 14:44
 */
public class AcWing788_逆序对的数量 {
    static int result = 0;
    public static void merge_sort(int[] nums, int l , int r) {
        if (l >= r) return;
        int mid = l + r >> 1;
        merge_sort(nums, l, mid);
        merge_sort(nums, mid + 1, r);
        int k = 0, i = l, j = mid + 1 ;
        int[] temp = new int[r - l + 1];
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            }else {
                temp[k++] = nums[j++];
                result += (mid - i + 1);
            }
        }
        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        while (j <= r) {
            temp[k++] = nums[j++];
        }
        for (int m = 0; m < k; m++) {
            nums[m + l] = temp[m];
        }
    }

    public static void main(String[] args) {
        int n;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        merge_sort(nums,0, n-1);
        System.out.println(result);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

# 3.二分

# 789.数的范围

给定一个按照升序排列的长度为 n的整数数组，以及 q 个查询。

对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 00 开始计数）。

如果数组中不存在该元素，则返回 -1 -1。

输入格式

第一行包含整数 n 和 q，表示数组长度和询问个数。

第二行包含 n个整数（均在 1∼100001∼10000 范围内），表示完整数组。

接下来 q 行，每行包含一个整数 k，表示一个询问元素。

输出格式

共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 -1 -1。

数据范围

1≤n≤100000 1≤q≤10000 1≤k≤10000

输入样例：

6 3
1 2 2 3 3 4
3
4
5

1
2
3
4
5

输出样例：

3 4
5 5
-1 -1

1
2
3

package com.ep.AcWing;

import java.util.Scanner;

/***
 * @author dep
 * @version 1.0
 * @date 2023-03-04 14:51
 */
public class AcWing789_数的范围 {
    static int[] arr = new int[100010];
    public static void main(String[] args) {
        int n, m;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        while (m-- != 0) {
            int x = scanner.nextInt();
            int l = -1, r = n;
            while (l + 1 != r) { // 寻做左边界
                int mid = l + r >> 1;
                if (arr[mid] >= x) r = mid;
                else l = mid;
            }
            if (arr[r] != x) {
                System.out.println("-1 -1");
            }
            else { // 寻找右边界
                System.out.print(r + " ");
                l = -1; r = n;
                while (l + 1 != r) {
                    int mid = l + r >> 1;
                    if (arr[mid] <= x) l = mid;
                    else r = mid;
                }
                if (arr[l] != x) System.out.println(r);
                else System.out.println(l);
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

# 790.数的三次方根

给定一个浮点数 n，求它的三次方根。

输入格式

共一行，包含一个浮点数 n。

输出格式

共一行，包含一个浮点数，表示问题的解。

注意，结果保留 6位小数。

数据范围

−10000≤n≤10000

输入样例：

1000.00

输出样例：

10.000000

package com.ep.AcWing;

import java.util.Scanner;

/***
 * @author dep
 * @version 1.0
 * @date 2023-03-06 14:35
 */
public class AcWing790_数的三次方根 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        double x;
        x = scanner.nextDouble();
        double l = -1000, r = 1000;
        while (r - l > 1e-8) {
            Double mid = (l + r) / 2;
            if (mid*mid*mid >= x) r = mid;
            else l = mid;
        }
        System.out.println(String.format("%.6f",l));
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 4.高精度

# 791.高精度加法

给定两个正整数（不含前导 00），计算它们的和。

输入格式

共两行，每行包含一个整数。

输出格式

共一行，包含所求的和。

数据范围

1≤整数长度≤1000001≤整数长度≤100000

输入样例：

12
23

1
2

输出样例：

package com.ep.AcWing;

import java.util.Scanner;

/***
 * @author dep
 * @version 1.0
 * @date 2023-03-06 15:10
 */
public class AcWing791_高精度加法 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        char[] a_array = new StringBuffer(scanner.next()).reverse().toString().toCharArray();
        char[] b_array = new StringBuffer(scanner.next()).reverse().toString().toCharArray();
        System.out.println(add(a_array, b_array));

    }
    public static String add(char[] a, char[] b) {
        int m = a.length, n = b.length;
        if (m < n) return add(b,a);
        StringBuffer result = new StringBuffer();
        int t = 0;
        for (int i = 0; i < m; i++) {
            t+=a[i] - '0';
            if (i < n){
                t+=b[i] - '0';
            }
            result.append(t % 10);
            t /= 10;
        }
        if (t == 1) result.append('1');
        return result.reverse().toString();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# 792.高精度减法

给定两个正整数（不含前导 00），计算它们的差，计算结果可能为负数。

输入格式

共两行，每行包含一个整数。

输出格式

共一行，包含所求的差。

数据范围

1≤整数长度≤1051≤整数长度≤105

输入样例：

32
11

1
2

输出样例：

package com.ep.AcWing;

import java.util.Arrays;
import java.util.Scanner;

/***
 * @author dep
 * @version 1.0
 * @date 2023-03-07 10:34
 */
public class AcWing792_高精度减法 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
//        String a = scanner.next();
//        String b = scanner.next();
//        char[] a_array = new char[a.length()];
//        char[] b_array = new char[b.length()];
//        int j = 0;
//        for (int i = a.length() - 1; i >= 0 ; i--) {
//            a_array[j++] = a.charAt(i);
//        }
//        j = 0;
//        for (int i = b.length() - 1; i >= 0 ; i--) {
//            b_array[j++] = b.charAt(i);
//        }
//        System.out.println(Arrays.toString(a_array));
//        System.out.println(Arrays.toString(b_array));
        char[] a_array = new StringBuffer(scanner.next()).reverse().toString().toCharArray();
        char[] b_array = new StringBuffer(scanner.next()).reverse().toString().toCharArray();
        System.out.println(sub(a_array, b_array));
    }
    public static String sub(char[] a, char[] b) {
        if (!cmp(a,b)) return "-" + sub(b,a);
        int t = 0,result = 0;
        StringBuffer stringBuffer = new StringBuffer();
        for (int i = 0; i < a.length; i++) {
            result = a[i] - '0' - t;
            if (i < b.length) {
                result -= (b[i] - '0');
            }
            if (result < 0) t = 1;
            else t = 0;
            result = (result + 10) % 10;
            stringBuffer.append(result);
        }
        //要去掉前缀的0
        char[] chars = stringBuffer.toString().toCharArray();
        int i = chars.length - 1;
        while (i >= 1 && chars[i] == '0') {
            i--;
        }
        String str = "";
        for (int j = i; j >= 0; j--) {
            str += chars[j];
        }
        return str;
    }

    /**
     * 比较两个数的大小
     * @param a 正整数
     * @param b 正整数
     * @return
     */
    public static boolean cmp(char[] a, char[] b) {
        if (a.length != b.length) return a.length > b.length;
        for (int i = a.length - 1; i >= 0; i--) {
            if (a[i] != b[i]) return a[i] > b[i];
        }
        return true;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

# 793.高精度乘法

给定两个非负整数（不含前导 00） A 和 B，请你计算 A×B 的值。

输入格式

共两行，第一行包含整数 A，第二行包含整数 B

输出格式

共一行，包含 A×B�×� 的值。

数据范围

1≤A的长度≤100000, 0≤B≤10000

输入样例：

2
3

1
2

输出样例：

package com.ep.AcWing;

import java.util.Scanner;

/***
 * @author dep
 * @version 1.0
 * @date 2023-03-08 19:30
 */
public class AcWing793_高精度乘法 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        char[] a_arrray = new StringBuffer(scanner.next()).reverse().toString().toCharArray();
        int b = scanner.nextInt();
        System.out.println(mul(a_arrray, b));
    }
    public static String mul(char[] a, int b) {
        int t = 0;
        StringBuffer result = new StringBuffer();
        // t!= 0,最后余数可能不是个位数
        for (int i = 0; i < a.length || t != 0; i++) {
            if (i < a.length) t += (a[i] - '0')  * b;
            result.append(t % 10);
            t /= 10;
        }
        while (result.length() > 1 && result.charAt(result.length() - 1) == '0')
            result.deleteCharAt(result.length() - 1);
//        // 去掉前缀的0
//        char[] a_array = result.toString().toCharArray();
//        int i = a_array.length - 1;
//        while (i > 0 && a_array[i] == '0') {
//            i--;
//        }
//        String str = "";
//        for (int j = i; j >= 0 ; j--) {
//            str += a_array[j];
//        }
        return result.reverse().toString();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

# 794.高精度除法

给定两个非负整数（不含前导 00） A，B，请你计算 A/B 的商和余数。

输入格式

共两行，第一行包含整数 A，第二行包含整数 B。

输出格式

共两行，第一行输出所求的商，第二行输出所求余数。

数据范围

1≤A的长度≤100000, 1≤B≤≤10000, B一定不为 00

输入样例：

7
2

1
2

输出样例：

3
1

1
2

package com.ep.AcWing;

import java.util.Scanner;

/***
 * @author dep
 * @version 1.0
 * @date 2023-03-08 20:14
 */
public class AcWing794_高精度除法 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        char[] a_array = scanner.next().toCharArray();
        int b = scanner.nextInt();
        div(a_array, b);
    }
    public static void div(char[] a, int b) {
        StringBuffer result = new StringBuffer();
        int t = 0;
        for (int i = 0; i < a.length; i++) {
            t = t* 10 + (a[i] - '0');
            result.append(t / b);
            t = t % b;
        }
        // 需要去掉前缀0
        StringBuffer res = result.reverse();
        while (res.length() > 1 && res.charAt(res.length() - 1) == '0') {
            res.deleteCharAt(res.length() - 1);
        }
        System.out.println(res.reverse().toString());
        System.out.println(t);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# 5.前缀和与差分

# 795.前缀和

输入一个长度为 n的整数序列。

接下来再输入 m个询问，每个询问输入一对 l,r。

对于每个询问，输出原序列中从第 l 个数到第 r个数的和。

输入格式

第一行包含两个整数 n 和 m。

第二行包含 n 个整数，表示整数数列。

接下来 m行，每行包含两个整数 l 和 r，表示一个询问的区间范围。

输出格式

共 m 行，每行输出一个询问的结果。

数据范围

1≤l≤r≤n, 1≤n,m≤100000, −1000≤数列中元素的值≤1000−1000≤数列中元素的值≤1000

输入样例：

1
2
3
4
5

输出样例：

3
6
10

1
2
3

package com.ep.AcWing;

import java.util.Scanner;

/***
 * @author dep
 * @version 1.0
 * @date 2023-03-10 22:31
 */
public class AcWing795_前缀和 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        int [] sums = PrefixSum(arr,n);
        while (m!= 0) {
            int l = scanner.nextInt();
            int r = scanner.nextInt();
            System.out.println(sums[r] - sums[l-1]);
            m--;
        }
    }
    // 求前缀和
    public static int[] PrefixSum(int[] arr, int n) {
        int[] sum = new int[n+1];
        sum[0] = 0;
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i-1] + arr[i-1];
        }
        return sum;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

# 796.子矩阵的和

输入一个 n 行 m列的整数矩阵，再输入 q个询问，每个询问包含四个整数 x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

输入格式

第一行包含三个整数 n，m，q。

接下来 n 行，每行包含 m 个整数，表示整数矩阵。

接下来 q 行，每行包含四个整数 x1,y1,x2,y2，表示一组询问。

输出格式

共 q 行，每行输出一个询问的结果。

数据范围

1≤n,m≤1000, 1≤q≤2000001, 1≤x1≤x2≤n1, 1≤y1≤y2≤m1, −1000≤矩阵内元素的值≤1000−1000≤矩阵内元素的值≤1000

输入样例：

1
2
3
4
5
6
7

输出样例：

17
27
21

1
2
3

package com.ep.AcWing;

import java.util.Scanner;

/***
 * @author dep
 * @version 1.0
 * @date 2023-03-11 9:31
 */
public class AcWing796_子矩阵的和 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int q = scanner.nextInt();
        int[][] arr = new int[n+1][m+1];
        int[][] sums = new int[n+1][m+1];
        // 求前缀和
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                arr[i][j] = scanner.nextInt();
                sums[i][j] = sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1] + arr[i][j];
            }
        }
        while (q > 0) {
            int x1 = scanner.nextInt();
            int y1 = scanner.nextInt();
            int x2 = scanner.nextInt();
            int y2 = scanner.nextInt();
            System.out.println(sums[x2][y2] - sums[x1-1][y2] - sums[x2][y1-1] + sums[x1-1][y1-1]);
            q--;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# 797.差分

给定a[1],a[2].....a[n],构造差分数组b[N],使得 a[i] = b[1] + b[2] + ... + b[i];

核心操作:

将a[L-R]全部加上C等价于 b[L] += C, b[R+1] -= C;

输入一个长度为 n 的整数序列。

接下来输入 m个操作，每个操作包含三个整数 l,r,c表示将序列中 [l,r][�,�] 之间的每个数加上 c。

请你输出进行完所有操作后的序列。

输入格式

第一行包含两个整数 n和 m。

第二行包含 n个整数，表示整数序列。

接下来 m行，每行包含三个整数 l，r，c，表示一个操作。

输出格式

共一行，包含 n 个整数，表示最终序列。

数据范围

1≤n,m≤≤100000, 1≤l≤r≤n, −1000≤c≤1000, −1000≤整数序列中元素的值≤1000−1000≤整数序列中元素的值≤1000

输入样例：

6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

1
2
3
4
5

输出样例：

3 4 5 3 4 2

public class AcWing797_差分 {
    static int N = 100010;
    static int[] b = new int[N];
    static int[] a = new int[N];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        String[] s1 = br.readLine().split(" ");
        for (int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(s1[i-1]);
            insert(i,i,a[i]);
        }
        while (m > 0) {
            String[] s2 = br.readLine().split(" ");
            int l = Integer.parseInt(s2[0]);
            int r = Integer.parseInt(s2[1]);
            int c = Integer.parseInt(s2[2]);
            insert(l,r,c);
            m--;
        }
        for (int i = 1; i <= n; i++) {
            a[i] = a[i-1] + b[i];
            System.out.print(a[i] + " ");
        }
    }
    public static void insert(int l, int r, int c){
        b[l] += c;
        b[r + 1] -= c;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

# 798.差分矩阵

输入一个 n 行 m 列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 x1,y1,x2,y2,c，其中 (x1,y1)和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。

每个操作都要将选中的子矩阵中的每个元素的值加上 c。

请你将进行完所有操作后的矩阵输出。

输入格式

第一行包含整数 n,m,q。

接下来 n 行，每行包含 m 个整数，表示整数矩阵。

接下来 q 行，每行包含 55 个整数 x1,y1,x2,y2,c，表示一个操作。

输出格式

共 n 行，每行 m 个整数，表示所有操作进行完毕后的最终矩阵。

数据范围

1≤n,m≤1000, 1≤q≤≤100000, 1≤x1≤x2≤n1, 1≤y1≤y2≤m1, −1000≤c≤1000, −1000≤矩阵内元素的值≤1000−1000≤矩阵内元素的值≤1000

输入样例：

1
2
3
4
5
6
7

输出样例：

2 3 4 1
4 3 4 1
2 2 2 2

1
2
3

package com.ep.AcWing;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/***
 * @author dep
 * @version 1.0
 * @date 2023-03-16 10:51
 */
public class AcWing798_差分矩阵 {
    static int N = 1010;
    static int[][] A = new int[N][N];
    static int[][] B = new int[N][N];
    public static void insert(int x1, int y1, int x2, int y2, int c) {
        B[x1][y1] += c;
        B[x1][y2+1] -= c;
        B[x2+1][y1] -= c;
        B[x2+1][y2+1] += c;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] s = bufferedReader.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        int q = Integer.parseInt(s[2]);
        for (int i = 1; i <= n; i++) {
            String[] s1 = bufferedReader.readLine().split(" ");
            for (int j = 1; j <= m; j++) {
                A[i][j] = Integer.parseInt(s1[j-1]);
                insert(i,j,i,j,A[i][j]);
            }
        }
        while (q != 0) {
            String[] s1 = bufferedReader.readLine().split(" ");
            int x1 = Integer.parseInt(s1[0]);
            int y1 = Integer.parseInt(s1[1]);
            int x2 = Integer.parseInt(s1[2]);
            int y2 = Integer.parseInt(s1[3]);
            int c = Integer.parseInt(s1[4]);
            insert(x1,y1,x2,y2,c);
            q--;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                A[i][j] = A[i-1][j] + A[i][j-1] - A[i-1][j-1] + B[i][j];
                System.out.print(A[i][j] + " ");
            }
            System.out.println();
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

# 6.双指针算法

# 799.最长连续不重复子序列

给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

输入格式

第一行包含整数 n。

第二行包含 n 个整数（均在 0∼1050∼105 范围内），表示整数序列。

输出格式

共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。

数据范围

1≤n≤10的5次方

输入样例：

5
1 2 2 3 5

1
2

输出样例：

package com.ep.AcWing;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

/***
 * @author dep
 * @version 1.0
 * @date 2023-03-16 15:10
 */
public class AcWing799_最长连续不重复子序列 {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String s = bufferedReader.readLine();
        int n = Integer.parseInt(s);
        int[] arr = new int[n];
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        String[] s1 = bufferedReader.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(s1[i]);
        }
        int max = 0;
        for (int i = 0,j = 0; i < n; i++) {
            hashMap.put(arr[i],hashMap.getOrDefault(arr[i],0) + 1);
            while (hashMap.getOrDefault(arr[i],0) > 1) {
                hashMap.put(arr[j],hashMap.getOrDefault(arr[j], 0) - 1);
                j++;
            }
            max = Math.max(max, i - j + 1);
        }
        System.out.println(max);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

# 800.数组元素的目标和

给定两个升序排序的有序数组 A 和 B，以及一个目标值 x。

数组下标从 00 开始。

请你求出满足 A[i]+B[j]=x的数对 (i,j)。

数据保证有唯一解。

输入格式

第一行包含三个整数 n,m,x，分别表示 A 的长度，B 的长度以及目标值 x。

第二行包含 n 个整数，表示数组 A。

第三行包含 m 个整数，表示数组 B。

输出格式

共一行，包含两个整数 i和 j。

数据范围

数组长度不超过 105105。同一数组内元素各不相同。 1≤数组元素≤1091≤数组元素≤109

输入样例：

4 5 6
1 2 4 7
3 4 6 8 9

1
2
3

输出样例：

1 1

package com.ep.AcWing;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/***
 * @author dep
 * @version 1.0
 * @date 2023-03-17 10:15
 */
public class AcWing800_数组元素的目标和 {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] s = bufferedReader.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        int x = Integer.parseInt(s[2]);
        int[] a = new int[n];
        int[] b = new int[m];
        String[] s1 = bufferedReader.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(s1[i]);
        }
        String[] s2 = bufferedReader.readLine().split(" ");
        for (int i = 0; i < m; i++) {
            b[i] = Integer.parseInt(s2[i]);
        }
        int j = m - 1;
        for (int i = 0; i < n; i++) {
            while (j >= 0 && a[i] + b[j] > x) j--;
            if (a[i] + b[j] == x) {
                System.out.println(i + " " + j);
                break;
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

# 2816.判断子序列

给定一个长度为 n 的整数序列 a1,a2,…,an以及一个长度为 m的整数序列 b1,b2,…,bm

请你判断 a序列是否为 b 序列的子序列。

子序列指序列的一部分项按原有次序排列而得的序列，例如序列 {a1,a3,a5}是序列 {a1,a2,a3,a4,a5}的一个子序列。

输入格式

第一行包含两个整数 n,m。

第二行包含 n 个整数，表示 a1,a2,…,an。

第三行包含 m 个整数，表示 b1,b2,…,bm。

输出格式

如果 a 序列是 b 序列的子序列，输出一行 Yes。

否则，输出 No。

数据范围

1≤n≤m≤105, −109≤ai,bi≤≤109

输入样例：

3 5
1 3 5
1 2 3 4 5

1
2
3

输出样例：

Yes

package com.ep.AcWing;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/***
 * @author dep
 * @version 1.0
 * @date 2023-03-17 10:28
 */
public class AcWing2816_判断子序列 {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] s = bufferedReader.readLine().split(" ");
        int n = Integer.parseInt(s[0]), m = Integer.parseInt(s[1]);
        int[] a = new int[n];
        int[] b = new int[m];
        String[] s1 = bufferedReader.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(s1[i]);
        }
        String[] s2 = bufferedReader.readLine().split(" ");
        for (int i = 0; i < m; i++) {
            b[i] = Integer.parseInt(s2[i]);
        }
        int i = 0, j = 0;
        while(i < n && j < m) {
            if (a[i] == b[j]) i++;
            j++;
        }
        if (i == n) System.out.println("Yes");
        else System.out.println("No");
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

# 7.位运算

# 801.二进制中1的个数

给定一个长度为 n的数列，请你求出数列中每个数的二进制表示中 11 的个数。

输入格式

第一行包含整数 n。

第二行包含 n 个整数，表示整个数列。

输出格式

共一行，包含 n 个整数，其中的第 i 个数表示数列中的第 i个数的二进制表示中 11 的个数。

数据范围

1≤n≤100000, 0≤数列中元素的值≤1090≤数列中元素的值≤109

输入样例：

5
1 2 3 4 5

1
2

输出样例：

1 1 2 1 2

package com.ep.AcWing;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/***
 * @author dep
 * @version 1.0
 * @date 2023-03-17 10:49
 */
public class AcWing801_二进制中1的个数 {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String s = bufferedReader.readLine();
        int n = Integer.parseInt(s);
        String[] s1 = bufferedReader.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            int num =  Integer.parseInt(s1[i]);
            System.out.print(getBiteCount4(num) + " ");
        }
    }
    // 这种比较效率比较低
    static int getBiteCount(int num) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if ((num >> i & 1) == 1) count++;
        }
        return count;
    }
    // 比第一个稍微好点
    static int getBiteCount2(int num) {
        int count = 0;
        while (num != 0) {
            if(num % 2 == 1) count ++;
            num /= 2;
        }
        return count;
    }
    // 效率高
    static int getBiteCount3(int num) {
        int count = 0;
        while (num != 0) {
            num = num & (num - 1); // 去掉最右边的1
            count++;
        }
        return count;
    }
    static int lowbit(int num) {
        return num & (-num);
    }
    static int getBiteCount4(int num) {
        int count = 0;
        while (num != 0) {
            num -= lowbit(num); // 去掉最右边的1
            count++;
        }
        return count;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

# x & -x的含义

-x 在计算机存储是用x的补码存储，就是在x的值的基础上进行按位取反(~x)之后在增加1所得，也就是说

x & -x == x & (~x + 1)

x & (-x) 的用途一般是用来获取某个二进制数的 LowBit ，在树状数组 (opens new window)中会用到

lowbit(x)是x的二进制表达式中最低位的1所对应的值

# 8.离散化

# 802.区间和

假定有一个无限长的数轴，数轴上每个坐标上的数都是 00。

现在，我们首先进行 n次操作，每次操作将某一位置 x 上的数加 c。

接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r][�,�] 之间的所有数的和。

输入格式

第一行包含两个整数 n 和 m。

接下来 n 行，每行包含两个整数 x 和 c。

再接下来 m行，每行包含两个整数 l 和 r。

输出格式

共 m行，每行输出一个询问中所求的区间内数字和。

数据范围

−109≤x≤109, 1≤n,m≤105, −109≤l≤r≤109, −10000≤c≤10000

输入样例：

1
2
3
4
5
6
7

输出样例：

8
0
5

1
2
3

package com.ep.AcWing;

import java.util.*;

/***
 * @author dep
 * @version 1.0
 * @date 2023-03-19 10:56
 */
public class AcWing802_区间和 {
    static int N = 300010;
    static int[] a = new int[N];
    static int[] s = new int[N];
    static HashSet<Integer> hashSet = new HashSet<>();
    static int[] alls; // 存储坐标
    static int[][] adds;
    static int[][] query;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        adds = new int[n][2]; // 记录需要加的坐标和对应值
        query = new int[m][2]; // 记录需要查询的左右区间坐标
        for (int i = 0; i < n; i++) {
            int x = scanner.nextInt();
            int c = scanner.nextInt();
            hashSet.add(x);
            adds[i][0] = x;
            adds[i][1] = c;
        }
        for (int i = 0; i < m; i++) {
            int l = scanner.nextInt();
            int r = scanner.nextInt();
            hashSet.add(l);
            hashSet.add(r);
            query[i][0] = l;
            query[i][1] = r;
        }
        alls = hashSet.stream().mapToInt(Integer::intValue).toArray();
        Arrays.sort(alls);

        for (int i = 0; i < adds.length; i++) {
            int x = find(adds[i][0]);
            a[x] += adds[i][1];
        }
        for (int i = 1; i <= alls.length ; i++) {
            s[i] = s[i-1] + a[i];
        }
        for (int i = 0; i < query.length; i++) {
            int l = find(query[i][0]), r = find(query[i][1]);
            System.out.println(s[r] - s[l - 1]);
        }

    }
    // 因为对坐标进行了排序，所以需要找到这些坐标的新位置
    static int find(int x) {
        int l = 0, r = alls.length - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (alls[mid] >= x) r = mid;
            else l = mid + 1;
        }
        return l + 1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

# 9.区间合并

# 803.区间合并

给定 n 个区间 [li,ri][��,��]，要求合并所有有交集的区间。

注意如果在端点处相交，也算有交集。

输出合并完成后的区间个数。

例如：[1,3][1,3] 和 [2,6][2,6] 可以合并为一个区间 [1,6][1,6]。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含两个整数 l 和 r。

输出格式

共一行，包含一个整数，表示合并区间完成后的区间个数。

数据范围

1≤n≤100000, −109≤li≤ri≤109

输入样例：

1
2
3
4
5
6

输出样例：

package com.ep.AcWing;

import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;

import java.util.*;

/***
 * @author dep
 * @version 1.0
 * @date 2023-03-20 16:20
 */
public class AcWing803_区间合并 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        ArrayList<Point> points = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int l = scanner.nextInt();
            int r = scanner.nextInt();
            points.add(new Point(l,r));
        }
        System.out.println(merge(points));
    }
    static int merge(List<Point> points) {
        points.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                if (o1.getX() > o2.getX()) {
                    return 1;
                } else if (o1.getX() < o2.getX()) {
                    return -1;
                } else {
                    if (o1.getY() > o2.getY()) return 1;
                    else return -1;
                }
            }
        });
        ArrayList<Point> ans = new ArrayList<>();
        int start = points.get(0).getX(), end = points.get(0).getY();
        for (int i = 1; i < points.size(); i++) {
            if (points.get(i).getX() > end) {
                ans.add(points.get(i));
                start = points.get(i).getX();
                end = points.get(i).getY();
            } else {
                end = Math.max(points.get(i).getY(), end);
            }
        }
        ans.add(new Point(start, end));
        return ans.size();
    }
}
class Point {
    int x;
    int y;

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }


    public void setX(int x) {
        this.x = x;
    }

    public void setY(int y) {
        this.y = y;
    }

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "Point{" +
                "x=" + x +
                ", y=" + y +
                '}';
    }
}

# 2.数据结构

# 2.1单链表

# 826.单链表

实现一个单链表，链表初始为空，支持三种操作：

向链表头插入一个数；
删除第 k个插入的数后面的数；
在第 k个插入的数后插入一个数。

现在要对该链表进行 M次操作，进行完所有操作后，从头到尾输出整个链表。

注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 11 个插入的数，第 22 个插入的数，…第 n个插入的数。

输入格式

第一行包含整数 M，表示操作次数。

接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：

H x，表示向链表头插入一个数 x。
D k，表示删除第 k 个插入的数后面的数（当 k 为 0 时，表示删除头结点）。
I k x，表示在第 k 个插入的数后面插入一个数 x（此操作中 k 均大于 0）。

输出格式

共一行，将整个链表从头到尾输出。

数据范围

1≤M≤100000 所有操作保证合法。

输入样例：

1
2
3
4
5
6
7
8
9
10
11

输出样例：

6 4 6 5

package com.ep.AcWing.DataStructure;

import java.util.Arrays;
import java.util.Scanner;

/***
 * @author dep
 * @version 1.0
 * @date 2023-04-10 9:53
 */
public class exercise1_826_单链表 {
    static int N = 100010;
    static int[] e = new int[N]; // e[i]表示结点i的值
    static int[] ne = new int[N]; // ne[i]表示结点i的next指针是多少
    static int head;// head表示头结点的下标
    static int idx;// idx 存储当前已经用到了哪个点

    public static void main(String[] args) {
        // 为什么要用数组模拟链表（new 每次的开销很大）
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int k, x;
        init();
        while (m != 0) {
            Character ch = scanner.next().toCharArray()[0];
            switch (ch) {
                case 'H':
                    x = scanner.nextInt();
                    add_to_head(x);
                    break;
                case 'D':
                    k = scanner.nextInt();
                    if (k == 0) {
                        head = ne[head];
                    } else {
                        remove(k - 1);
                    }
                    break;
                case 'I':
                    k = scanner.nextInt();
                    x = scanner.nextInt();
                    add(k - 1, x);
                    break;
            }
            m--;
        }
        print();
    }

    static void init() {
        head = -1;
        idx = 0;
    }

    // 将x插入头结点
    static void add_to_head(int x) {
        e[idx] = x; // 相当于new了一个新的结点
        ne[idx] = head; // 新结点指向head的下一个结点
        head = idx;
        idx++;
    }

    // 将x插到下标是k的节点的后面
    static void add(int k, int x) {
        e[idx] = x;
        ne[idx] = ne[k];
        ne[k] = idx;
        idx++;
    }

    // 将下标是k的点后面的点删掉
    static void remove(int k) {
        ne[k] = ne[ne[k]];
    }

    static void print() {
        int p = head;
        while (p != -1) {
            System.out.print(e[p] + " ");
            p = ne[p];
        }
    }

}

# 2.2双链表

# 827.双链表

实现一个双链表，双链表初始为空，支持 5种操作：

在最左侧插入一个数；
在最右侧插入一个数；
将第 k个插入的数删除；
在第 k个插入的数左侧插入一个数；
在第 k个插入的数右侧插入一个数

现在要对该链表进行 M 次操作，进行完所有操作后，从左到右输出整个链表。

注意:题目中第 k个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n个数，则按照插入的时间顺序，这 n个数依次为：第 1 个插入的数，第 2个插入的数，…第 n个插入的数。

输入格式

第一行包含整数 M，表示操作次数。

接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：

L x，表示在链表的最左端插入数 x。
R x，表示在链表的最右端插入数 x。
D k，表示将第 k个插入的数删除。
IL k x，表示在第 k个插入的数左侧插入一个数。
IR k x，表示在第 k个插入的数右侧插入一个数。

输出格式

共一行，将整个链表从左到右输出。

数据范围

1≤M≤100000 所有操作保证合法。

输入样例：

10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2

1
2
3
4
5
6
7
8
9
10
11

输出样例：

8 7 7 3 2 9

package com.ep.AcWing.DataStructure;

import java.util.Scanner;

/***
 * @author dep
 * @version 1.0
 * @date 2023-04-11 12:30
 */
public class exercise2_827_双链表 {
    static int N = 20;
    static int[] e = new int[N];
    static int[] l = new int[N];
    static int[] r = new int[N];
    static int idx, head, tail;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int k, x;
        init();
        while (m != 0) {
            String ch = scanner.next();
            switch (ch) {
                case "L":
                    x = scanner.nextInt();
                    add(head, x);
                    break;
                case "R":
                    x = scanner.nextInt();
                    add(l[tail], x);
                    break;
                case "D":
                    k = scanner.nextInt();
                    remove(k + 1);
                    break;
                case "IL":
                    k = scanner.nextInt();
                    x = scanner.nextInt();
                    add(l[k + 1], x);
                    break;
                case "IR":
                    k = scanner.nextInt();
                    x = scanner.nextInt();
                    add(k + 1, x);
                    break;
            }
            m--;
        }
        print();
    }

    // 初始化双链表
    static void init() {
        // 0表示左端点，1表示右端点
        head = 0;
        tail = 1;
        r[head] = 1;
        l[tail] = 0;
        idx = 2;
    }

    // 在下标是k的点的右边插入x
    static void add(int k, int x) {
        e[idx] = x;
        r[idx] = r[k];
        l[idx] = k;
        l[r[k]] = idx;
        r[k] = idx;
        idx++;
    }

    // 删除第k个结点
    static void remove(int k) {
        r[l[k]] = r[k];
        l[r[k]] = l[k];
    }

    static void print() {
        for (int i = r[head]; i != tail; i = r[i]) {
            System.out.print(e[i] + " ");
        }
    }
}

# 2.3 栈

# 828.模拟栈

实现一个栈，栈初始为空，支持四种操作：

push x – 向栈顶插入一个数 x；
pop – 从栈顶弹出一个数；
empty – 判断栈是否为空；
query – 查询栈顶元素。

现在要对栈进行 M 个操作，其中的每个操作 3 和操作 4 都要输出相应的结果。

输入格式

第一行包含整数 M，表示操作次数。

接下来 M 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。

输出格式

对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。

其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示栈顶元素的值。

数据范围

1≤M≤100000, 1≤x≤10^9 所有操作保证合法。

输入样例：

10
push 5
query
push 6
pop
query
pop
empty
push 4
query
empty

1
2
3
4
5
6
7
8
9
10
11

输出样例：

5
5
YES
4
NO

1
2
3
4
5

package com.ep.AcWing.DataStructure;

import java.util.Arrays;
import java.util.Scanner;

/***
 * @author dep
 * @version 1.0
 * @date 2023-04-15 10:59
 */
public class exercise3_828_模拟栈 {
    static int N = 100010;
    static int[] arr = new int[N];
    static int top;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int x;
        init();
        while (m != 0) {
            String op = scanner.next();
            switch (op) {
                case "push":
                    x = scanner.nextInt();
                    push(x);
                    break;
                case "pop":
                    pop();
                    break;
                case "empty":
                    if (isEmpty()) {
                        System.out.println("YES");
                    } else {
                        System.out.println("NO");
                    }
                    break;
                case "query":
                    System.out.println(peek());
                    break;
            }
            m--;
        }

    }

    static void init() {
        top = -1;
    }

    static void push(int x) {
        top++;
        arr[top] = x;
    }

    static int pop() {
        if (!isEmpty()) {
            return arr[top--];
        }
        return -1;
    }

    static int peek() {
        return arr[top];
    }

    static Boolean isEmpty() {
        if (top == -1) {
            return true;
        } else {
            return false;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

# 3302.表达式求值

给定一个表达式，其中运算符仅包含 +,-,*,/（加减乘整除），可能包含括号，请你求出表达式的最终值。

注意：

数据保证给定的表达式合法。
题目保证符号 - 只作为减号出现，不会作为负号出现，例如，-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。
题目保证表达式中所有数字均为正整数。
题目保证表达式在中间计算过程以及结果中，均不超过 231−1231−1。
题目中的整除是指向 0 取整，也就是说对于大于 0 的结果向下取整，例如 5/3=1，对于小于 0的结果向上取整，例如 5/(1−4)=−1。
C++和Java中的整除默认是向零取整；Python中的整除//默认向下取整，因此Python的eval()函数中的整除也是向下取整，在本题中不能直接使用。

输入格式

共一行，为给定表达式。

输出格式

共一行，为表达式的结果。

数据范围

表达式的长度不超过 105105。

输入样例：

(2+2)*(1+1)

输出样例：

package com.ep.AcWing.DataStructure;

import java.util.HashMap;
import java.util.Scanner;
import java.util.Stack;

/***
 * @author dep
 * @version 1.0
 * @date 2023-04-15 15:21
 */
public class exercise4_3302_表达式求值 {
     static Stack<Integer> num_stack = new Stack<>();
    static Stack<Character> op_stack = new Stack<>();
    // 运算符的优先级
    static HashMap<Character, Integer> map = new HashMap<>();
    public static void main(String[] args) {
        map.put('+',1);
        map.put('-',1);
        map.put('*',2);
        map.put('/',2);
        Scanner scanner = new Scanner(System.in);
        String exp = scanner.next();
        for (int i = 0; i < exp.length(); i++) {
            char c = exp.charAt(i);
            if (Character.isDigit(c)) {
                int x = 0, j = i;
                while (j < exp.length() && Character.isDigit(exp.charAt(j))) {
                    x = x * 10 + (exp.charAt(j) - '0');
                    j++;
                }
                i = j - 1;
                num_stack.push(x);
            } else if (c == '(') {
                op_stack.push(c);
            } else if( c == ')') {
                while (op_stack.peek() != '(') eval();
                op_stack.pop();
            } else {
                // 这里 map.get(op_stack.peek())，可能会取出左括号
                while (!op_stack.isEmpty() && map.getOrDefault(op_stack.peek(),0) >= map.get(c)) eval();
                op_stack.push(c);
            }
        }
        while (!op_stack.isEmpty()) eval();
        System.out.println(num_stack.pop());
    }

    // 计算
    public static void eval() {
        int b = num_stack.pop();
        int a = num_stack.pop();
        char op = op_stack.pop();
        switch (op) {
            case '+': num_stack.push(a+b);break;
            case '-': num_stack.push(a-b);break;
            case '*': num_stack.push(a*b);break;
            case '/': num_stack.push(a/b);break;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

# 5.动态规划

参考文章：https://blog.csdn.net/raelum/article/details/128996521

# 1.背包问题

# 2.01背包问题

有 N件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤1000 0<vi,wi≤1000

输入样例

1
2
3
4
5

输出样例：

设 d p [ i ] [ j ] 的含义是：在背包承重为 j 的前提下，从前 i 个物品中选能够得到的最大价值。不难发现 d p [ N ] [ M ] 就是本题的答案。

如何计算 d p [ i ] [ j ] 呢？我们可以将它划分为以下两部分：

选第 i 个物品：由于第 i 个物品一定会被选择，那么相当于从前 i − 1个物品中选且总重量不超过 j − v [ i ] ，对应 d p [ i − 1 ] [ j − v [ i ] ] + w [ i ]
不选第 i 个物品：意味着从前 i − 1 个物品中选且总重量不超过 j ，对应 d p [ i − 1 ] [ j ] 。

package com.ep.AcWing.dynamic;

import java.util.Scanner;

/***
 * @author dep
 * @version 1.0
 * @date 2023-03-25 11:08
 */
public class AcWing2_01背包问题 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] V = new int[n+1]; // 存放物品的体积
        int[] W = new int[n+1]; // 存放物品的价值
        int[][] f = new int[n+1][m+1];
        for (int i = 1; i <= n; i++) {
            V[i] = scanner.nextInt();
            W[i] = scanner.nextInt();
        }

        /*
        f[i][j] 表示只看前i个物品，总体积是j的情况下，总价值最大是多少
        result = max(f[n][0-v])

        f[i][j]:
        1. 不选第i个物品，f[i][j] = f[i-1][j],从前i-1个物品选出不超过j的总体积
        2. 选第i个物品， f[i][j] = f[i-1][j-v[i]]; 选择了i,且i的体积为

        f[i][j] = max{1,2};
        f[0][0] = 0;
         */

        // 使用二维数组
//        for (int i = 1; i <= n; i++) {
//            for (int j = 0; j <= m; j++) {
//                f[i][j] = f[i-1][j];
//                if (j >= V[i])
//                    f[i][j] = Math.max(f[i][j],f[i-1][j- V[i]] + W[i]);
//            }
//        }
//        int res = 0;
//        for (int i = 0; i <= m ; i++) res = Math.max(res, f[n][i]);

        int[] dp = new int[m+1];
        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= V[i]; j--) {
                dp[j] = Math.max(dp[j],dp[j-V[i]] + W[i]);
            }
        }

        System.out.println(dp[m]);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

# 3.完全背包问题

有 N种物品和一个容量是 V的背包，每种物品都有无限件可用。

第 i种物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤1000 0<vi,wi≤1000

输入样例

1
2
3
4
5

输出样例：

编辑

#算法 #AcWing

上次更新: 2024/12/19, 09:15:30

← 算法基础 Git命令→