算法

 

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++; // 移动源字符串的索引}// 如果目标字符串已经完全匹配，则返回YESreturn 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()-1if (!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 {//首先我们需要一个全局变量nstatic 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);}