算法

1 差分练习

1 模板题

代码实现：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int num = sc.nextInt();
        long[][] arr = new long[n + 2][m + 2];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                insert(arr, i, j, i, j, sc.nextInt());
            }
        }
        while (num > 0) {
            int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            int x2 = sc.nextInt();
            int y2 = sc.nextInt();
            int zz = sc.nextInt();
            insert(arr, x1, y1, x2, y2, zz);
            num--;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                arr[i][j] = arr[i][j] + arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1];
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void insert(long[][] arr, int x1, int y1, int x2, int y2, int num) {
            arr[x1][y1]+=num;
            arr[x1][y2+1]-=num;
            arr[x2+1][y1]-=num;
            arr[x2+1][y2+1]+=num;
    }
}

2 干草堆2041. 干草堆 - AcWing题库

代码实现：

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

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        int K = input.nextInt();
        long []arr1 = new long[N+2];
        while(K>0){
            int x = input.nextInt();
            int y = input.nextInt();
            arr1[x] += 1;
            arr1[y+1] -= 1;
            K--;
        }
        for (int i = 2; i <= N; i++) {
            arr1[i] =arr1[i-1]+arr1[i];
        }
        Arrays.sort(arr1);
        System.out.println(arr1[N / 2 + 2]);
    }
}

3 最高的牛101. 最高的牛 - AcWing题库

代码实现：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();//牛的数量
        int P = input.nextInt();//最高牛的位置
        int H = input.nextInt();//最高牛的身高
        int M = input.nextInt();//对数
        boolean[][] exist = new boolean[N + 1][N + 1];
        int[] arr = new int[N + 1];
        arr[0] = H;//给第一个元素初始化为H间接使每一个数都初始化为H，在过程中不断的相减从而达到题目的要求
        for (int i = 1; i <= M; i++) {
            int A = input.nextInt();
            int B = input.nextInt();
            if (A > B) {
                int temp = A;//大小
                A = B;
                B = temp;
            }
            if (!exist[A][B]) {//去重
                arr[A + 1]--;
                arr[B]++;
                exist[A][B] = true;
            }
        }
        for (int i = 1; i <= N; i++) {
            arr[i] = arr[i - 1] + arr[i];
            System.out.println(arr[i]);
        }
    }
}

4 棋盘5396. 棋盘 - AcWing题库

代码实现：

import java.io.*;
import java.util.Scanner;


public class Main {
    static int N=2010;
    static int[][] b=new int[N][N];
    public static void main(String[] args) throws IOException {
        Scanner scanner=new Scanner(new BufferedInputStream(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        int n=scanner.nextInt(),m=scanner.nextInt();
        while(m-->0) {
            int x1=scanner.nextInt(),y1=scanner.nextInt(),x2=scanner.nextInt(),y2=scanner.nextInt();
            insert(x1,y1,x2,y2,1);
        }
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
                writer.write(Integer.toString(b[i][j] % 2));
            }
            writer.write('\n');
        }
        writer.flush();
        scanner.close();
    }
    public static void insert(int x1, int y1, int x2, int y2,int c) {
        b[x1][y1]+=c;
        b[x2+1][y1]-=c;
        b[x1][y2+1]-=c;
        b[x2+1][y2+1]+=c;
    }
}

5 桶列表1715. 桶列表 - AcWing题库

代码实现：

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

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        int[] arr = new int[10100];
        int max = 0;
        for (int i = 0; i < N; i++) {
            int si = input.nextInt();
            max = Math.max(max, si);
            int ti = input.nextInt();
            max = Math.max(max, ti);
            int bi = input.nextInt();
            arr[si] += bi;
            arr[ti + 1] -= bi;
        }
        for (int i = 1; i <= max; i++) {
            arr[i] += arr[i - 1];
            //System.out.println(arr[i]);
        }
        Arrays.sort(arr);
        System.out.println(arr[arr.length - 1]);


    }
}

2 双指针练习

1 判断源字符串是否可以通过删除字符从而变成目标字符串

import java.util.Scanner;

public class abc_2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String SS = sc.next();
        String TS = sc.next();
        sc.close();

        if (en(SS, TS)) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
    private static boolean en(String SS, String TS) {
        int sIndex = 0, tIndex = 0;

        while (sIndex < SS.length() && tIndex < TS.length()) {
            if (SS.charAt(sIndex) == TS.charAt(tIndex)) {
                tIndex++; // 移动目标字符串的索引
            }
            sIndex++; // 移动源字符串的索引
        }
        // 如果目标字符串已经完全匹配，则返回YES
        return tIndex == TS.length();
    }
}

2 数组的逆置

import java.util.Scanner;

public class abc_1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int len = sc.nextInt();
        int [] arr = new int[len];
        for (int i = 0; i < len; i++) {
            arr[i] = sc.nextInt();
        }
        for(int i=0,j=len-1;i<j;i++,j--) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        for(int i=0;i<len;i++) {
            System.out.print(arr[i]+" ");
        }
    }
}

3 完美序列（未ac）

代码实现

1 暴力for

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

public class abc_6 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        int p = input.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = input.nextInt();
        }
        Arrays.sort(arr);
        int count = 0;
        for (int i = 0; i < N - 1; i++) {
            for (int j = arr.length - 1; j > 0; j--) {
                if (arr[i] * p >= arr[j] && i < j) {
                    count = Math.max(count, j - i + 1);
                }
            }
        }
        System.out.println(count);
    }
}

双指针算法改进

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

public class abc_7 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        int p = input.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = input.nextInt();
        }
        Arrays.sort(arr);
        int count = 0;
        int j = 0;
        for (int i = 0; i < N; i++) {
            while (j < N && arr[i] * p >= arr[j]) {
                j++;
            }
            if (i < j) {
                count = Math.max(count, j - i);
            }
        }
        System.out.println(count);
    }
}

4 最长连续递增序列

import java.util.Scanner;

public class acb_4 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();//数组长度
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = input.nextInt();
        }
        int len_max = 0;
        for (int i = 0; i < n; i++) {
            int j = i;
            //这里需要将索引位置拉到倒数第二个数
            while (j < n - 1 && check(arr, j)) {
                //j-i+1是两个位置的距离差，+1是因为index+1位置开始
                len_max = Math.max(len_max, j - i + 1 + 1);
                j++;
            }
        }
        System.out.println(len_max);
    }

    public static boolean check(int[] arr, int index) {
        return arr[index + 1] - arr[index] > 0;
    }
}

5 --3. 无重复字符的最长子串 - 力扣（LeetCode）

代码实现：

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

class abc_8 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int len = len(s);
        System.out.println(len);
    }

    public static int len(String s) {
        if (s == null || s.isEmpty()) return 0;
        Set<Character> set = new HashSet<>();
        int i = 0, j = 0, res = 0;
        while (j < s.length()) {//枚举以第j个字符结尾的最长不重复子串,j从0到s.length()-1
            if (!set.contains(s.charAt(j))) {//set不包含s.charAt(j)，说明不重复，放心加入，j继续后移，更新最大长度
                set.add(s.charAt(j++));
                res = Math.max(res, j - i);
            } else {
                set.remove(s.charAt(i++));
                //由于j直到调用set.add(s.charAt(j++))那里才会更新，
                //故!set.contains(s.charAt[j])会连续为false很多次，
                //直到set.remove(s.charAt(i++))连续执行很多次，这里的i是从0索引位置开始出发一直删到重复那个元素
                //eg:pwwkew  此时的s.charAt(j)为w,要将set集合里面的从头开始删除到w - (pw)
                //把s.charAt[j]删除为止
            }
        }
        return res;
    }
}

3 滑动窗口练习

//外层循环扩展右边界，内层循环扩展左边界
for (int l = 0, r = 0 ; r < n ; r++) {
	//当前考虑的元素
	while (l <= r && check()) {//区间[left,right]不符合题意
        //扩展左边界
    }
    //区间[left,right]符合题意，统计相关信息
}

1-- 3. 无重复字符的最长子串 - 力扣（LeetCode）

代码实现：

class abc_9 {
    public int lengthOfLongestSubstring(String s) {
        //滑动窗口
        char[] ss = s.toCharArray();
        Set<Character> set = new HashSet<>();//去重
        int res = 0;//结果
        for(int left = 0, right = 0; right < s.length(); right++) {//每一轮右端点都扩一个。
            char ch = ss[right];//right指向的元素，也是当前要考虑的元素
            while(set.contains(ch)) {//set中有ch，则缩短左边界，同时从set集合出元素
                set.remove(ss[left]);
                left++;
            }
            set.add(ss[right]);//别忘。将当前元素加入。
            res = Math.max(res, right - left + 1);//计算当前不重复子串的长度。
        }
        return res;
    }
}

4 DFS深度优先搜索

1全排列问题：输入一个数实现1到这个数的全排列

代码实现：

import java.util.Scanner;

public class abc_2_2 {
    static boolean[] v = new boolean[20];//判断数值是否访问
    static int n;//1-n的全排列
    static int[] a = new int[20];//保存方案

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        dfs(0);
    }

    private static void dfs(int x) {
        //x表示第几个数了
        if (x == n) {
            for (int i = 0; i < n; i++) {
                System.out.print(a[i] + " ");
            }
            System.out.println();
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (!v[i]) {//v[i]boolean数组中不存在
                a[x] = i;
                v[i] = true;
                dfs(x + 1);
                v[i] = false;
            }
        }
    }
}

分析

//123举例：123遍历
//dfs(0) 调用for循环,v[1]为false,1可以赋值给a[0] ,v[1]=true
//dfs(1) 调用for循环，v[1]为true已经被使用，v[2]为false,2可以被赋值给a[1] ,v[2]=true
//dfs(2) 调用for循环，v[1]为true已经被使用，v[2]为true已经被使用，v[3]为false,3可以赋值a[2] //,v[3]=true
//dfs(3) 直接执行if语句遍历输出数组(v[2]=false)
//123
//后来123遍历结束,执行回溯算法
//回溯dfs(1) for循环执行到3,v[1]为true v[2]=false,3赋值给a[1],v[2]=true
//dfs(2)，v[1]为true，v[2]为true,v[3]为false,2可以赋值a[2]，v[3]=true
//dfs(3)直接执行if语句遍历输出数组
//132
//dfs(2)到3已经执行完毕回溯dfs(0)

拓展题：实现一个数组的元素全排列

代码实现

import java.util.Scanner;

public class TTrain {

    static int n;
    static char[] arr_P = new char[26];
    static char[] arr_p = new char[26];
    static Scanner input = new Scanner(System.in);
    static boolean[] emp = new boolean[200];

    public static void main(String[] args) {
        n = input.nextInt();
        for (int i = 0; i < n; i++) {
            arr_P[i] = input.next().charAt(0);
        }

        ddfs(0);
    }

    private static void ddfs(int row) {
        if (row == n) {
            for (int i = 0; i < n; i++) {
                System.out.print(arr_p[i] + " ");
            }
            System.out.println();
        }
        for (int i = 0; i < n; i++) {
            if (!emp[arr_P[i]]) {
                emp[arr_P[i]] = true;
                arr_p[row] = arr_P[i];
                ddfs(row + 1);
                emp[arr_P[i]] = false;
            }
        }
    }
}

2 n-皇后问题

代码实现：

import java.util.Scanner;

public class abc_2_3 {
    //首先我们需要一个全局变量n
    static int n;
    //还需要三个boolean数组判断行列两条斜线
    static boolean[] arr1 = new boolean[30];
    static boolean[] arr2 = new boolean[30];
    static boolean[] arr3 = new boolean[30];
    //需要输入的Scanner对象
    static Scanner input = new Scanner(System.in);
    //需要一个二维数组存放棋盘
    static char[][] arr_s = new char[30][30];

    public static void main(String[] args) {
        n = input.nextInt();
        //二维数组初始化
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr_s[i][j] = '.';
            }
        }
        dfs_s(0);
    }

    private static void dfs_s(int row) {
        if (row == n) {//递归出口
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    System.out.print(arr_s[i][j] + " ");
                }
                System.out.println();
            }
            System.out.println();
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!arr1[i] && !arr2[i + row] && !arr3[-row + i + n]) {
                arr1[i] = arr2[row + i] = arr3[-row + i + n] = true;
                arr_s[row][i] = 'Q';
                dfs_s(row + 1);
                arr1[i] = arr2[row + i] = arr3[-row + i + n] = false;
                arr_s[row][i] = '.';
            }
        }
    }
}

补充：
// exist_1 列 i--(x) dfs(num)相当于树的一层一层的遍历
// exist_2 左斜线/ i+num--(x+b)
// exist_3 右斜线\ i-num--(-x+b)

2

import java.util.Scanner;

public class abc_2_8 {
    static Scanner sc = new Scanner(System.in);
    static int n;
    static char[][] arrss = new char[30][30];
    static boolean[] a = new boolean[30];
    static boolean[] b = new boolean[30];
    static boolean[] c = new boolean[30];
    static boolean[] d = new boolean[30];


    public static void main(String[] args) {
        n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arrss[i][j] = '.';
            }
        }
        dfs_8(0, 0, 0);
    }

    private static void dfs_8(int x, int y, int s) {
        if (y == n) {
            y = 0;
            x++;
        }
        if (x == n) {
            if (s == n) {
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        System.out.print(arrss[i][j] + " ");
                    }
                    System.out.println();
                }
                System.out.println();
            }
            return;
        }
        //不放
        dfs_8(x, y + 1, s);
        //放
        if (!a[x] && !b[y] && !c[x + y] && !d[x - y + n]) {
            arrss[x][y] = 'Q';
            a[x] = b[y] = c[x + y] = d[x - y + n] = true;
            dfs_8(x, y + 1, s + 1);
            a[x] = b[y] = c[x + y] = d[x - y + n] = false;
            arrss[x][y] = '.';
        }
    }
}

5 数学知识模板

1 质数模板

    private static boolean isPrime(int n) {
        if (n < 2) {
            return false;
        }
        for (int i = 2; i <= n / i; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

2 分解质因数

    private static void input_s(int n) {
        for (int i = 2; i <= n / i; i++) {//先判断质数，再在质数范围内判断因数
            if (n % i == 0) {
                while (n % i == 0) {
                    n /= i;
                    System.out.println(i);
                }
            }
        }
        if (n > 1) {
            System.out.println(n);
        }
    }

3 最小公倍数最大公因数

最大公因数（GCD）

最大公因数可以通过欧几里得算法来计算。欧几里得算法的基本思想是：两个数的最大公因数等于其中较小的数和两数相除余数的最大公因数。

最小公倍数（LCM）

最小公倍数可以通过最大公因数来计算。两个数的乘积等于它们的最大公因数和最小公倍数的乘积。即：

    //最大公因数    
    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    // 计算最小公倍数
    public static int lcm(int a, int b) {
        return a*b/gcd(a,b);
    }

4 java内置库进制转换

    // 将整数转换为二进制字符串
    public static String toBinary(int num) {
        return Integer.toBinaryString(num);
    }

    // 将整数转换为四进制字符串
    public static String toQuaternary(int num) {
        StringBuilder result = new StringBuilder();
        while (num > 0) {
            result.insert(0, num % 4);
            num /= 4;
        }
        return result.toString();
    }

    // 将整数转换为八进制字符串
    public static String toOctal(int num) {
        return Integer.toOctalString(num);
    }

    // 将整数转换为十六进制字符串
    public static String toHexadecimal(int num) {
        return Integer.toHexString(num);
    }