#基础算法

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）

2 

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;}
}