「Acwing算法合集」
力扣算法系列文章
一、差分
题目如下：
输入一个长度为 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
输入样例：
6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1
输出样例：
3 4 5 3 4 2
代码如下：
import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int query = sc.nextInt(); int[] arr = new int[n]; int[] help = new int[n]; for(int i = 0; i < n; ++i){ arr[i] = sc.nextInt(); } help[0] = arr[0]; for(int i = 1; i < n; ++i){ help[i] = arr[i] - arr[i - 1]; } while(query-- > 0){ int l = sc.nextInt(); int r = sc.nextInt(); int add = sc.nextInt(); help[l - 1] += add; if(r < n){ help[r] -= add; } } for(int i = 1; i < n; ++i){ help[i] += help[i - 1]; } for(int i = 0; i < n; i++){ System.out.print(help[i] + " "); } }}运行结果：
二、差分矩阵
题目如下：
输入一个 n 行 m 列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 x1,y1,x2,y2,c，其中 (x1,y1) 和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。
每个操作都要将选中的子矩阵中的每个元素的值加上 c。
请你将进行完所有操作后的矩阵输出。
输入格式
第一行包含整数 n,m,q。
接下来 n 行，每行包含 m 个整数，表示整数矩阵。
接下来 q 行，每行包含 5 个整数 x1,y1,x2,y2,c，表示一个操作。
输出格式
共 n 行，每行 m 个整数，表示所有操作进行完毕后的最终矩阵。
数据范围
1≤n,m≤1000,
1≤q≤100000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤c≤1000,
−1000≤矩阵内元素的值≤1000
输入样例：
3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1
输出样例：
2 3 4 1
4 3 4 1
2 2 2 2
代码如下：
import java.util.Scanner;public class Main { public static void insert(int[][] help, int row1, int col1, int row2, int col2, int add){ help[row1][col1] += add; if(row2 + 1 < help.length) { help[row2 + 1][col1] -= add; } if(col2 + 1 < help[0].length) { help[row1][col2 + 1] -= add; } if(col2 + 1 < help[0].length && row2 + 1 < help.length){ help[row2 + 1][col2 + 1] += add; } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int row = sc.nextInt(); int col = sc.nextInt(); int query = sc.nextInt(); int[][] arr = new int[row][col]; int[][] help = new int[row][col]; for(int i = 0; i < row; ++i){ for(int j = 0; j < col; ++j){ arr[i][j] = sc.nextInt(); insert(help, i, j, i, j, arr[i][j]); } } while(query -- > 0){ int row1 = sc.nextInt(); int col1 = sc.nextInt(); int row2 = sc.nextInt(); int col2 = sc.nextInt(); int add = sc.nextInt(); insert(help, row1 - 1, col1 - 1, row2 - 1, col2 - 1, add); } for(int i = 1; i < col; ++i){ help[0][i] += help[0][i - 1]; } for(int i = 1; i < row; ++i){ help[i][0] += help[i - 1][0]; } for(int i = 1; i < row; ++i){ for(int j = 1; j < col; ++j){ help[i][j] += help[i - 1][j] + help[i][j - 1] - help[i - 1][j - 1]; } } for(int i = 0; i < row; ++i){ for(int j = 0; j < col; ++j){ System.out.print(help[i][j] + " "); } System.out.println(); } }}运行结果：
三、最长连续不重复子序列
题目如下：
给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
输入格式
第一行包含整数 n。
第二行包含 n 个整数（均在 0∼105 范围内），表示整数序列。
输出格式
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。
数据范围
1≤n≤105
输入样例：
5
1 2 2 3 5
输出样例：
3
代码如下：
import java.util.Scanner;public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] arr = new int[n]; int[] help = new int[100001]; for(int i = 0 ; i < n; ++i){ arr[i] = sc.nextInt(); } int end = 1; help[arr[0]] ++; int p1 = 0; int ma = 1; while(end < n){ help[arr[end]]++; while(help[arr[end]] > 1 && p1 <= end){ help[arr[p1++]]--; } ma = Math.max(ma, end - p1 + 1); end++; } System.out.println(ma); }}运行结果：
四、数组元素的目标和
题目如下：
给定两个升序排序的有序数组 A 和 B，以及一个目标值 x。
数组下标从 0 开始。
请你求出满足 A[i]+B[j]=x 的数对 (i,j)。
数据保证有唯一解。
输入格式
第一行包含三个整数 n,m,x，分别表示 A 的长度，B 的长度以及目标值 x。
第二行包含 n 个整数，表示数组 A。
第三行包含 m 个整数，表示数组 B。
输出格式
共一行，包含两个整数 i 和 j。
数据范围
数组长度不超过 105。
同一数组内元素各不相同。
1≤数组元素≤109
输入样例：
4 5 6
1 2 4 7
3 4 6 8 9
输出样例：
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 x = sc.nextInt(); int[] arr1 = new int[n]; int[] arr2 = new int[m]; for(int i = 0; i < n; ++i){ arr1[i] = sc.nextInt(); } for(int i = 0; i < m; ++i){ arr2[i] = sc.nextInt(); } for(int i = 0; i < n; ++i){ int l = 0; int r = m - 1; int y = x - arr1[i]; while(l < r){ int mid = l + ((r - l) >> 1); if(arr2[mid] >= y){ r = mid; }else if(arr2[mid] < y){ l = mid + 1; } } if(arr2[l] == y){ System.out.println(i + " " + l); break; } } }}运行结果：
在线短网址网站
