凭借我考了这么多次ccf 170分却不会优化，费尽心思刷遍历年1、2 题，最终总结的万能算法，希望可以祝我下次西西艾福考试能冲200（手动狗头保命）。也希望各位看到这篇文章的小可爱们都可以摆脱西西艾福的折磨。
难搞的算法都给我退！退！退！
输入篇
小数据都可以用 Scanner sc = new Scanner(System.in);
但是大数据的时候经常会出现内存超限，所以要用BufferedReader，其他的该怎么写就怎么写。
public static void main(String[] args) throws IOException{
BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
String str = sc.readLine();
String[] vars = str.trim().split(" ");
int n = Integer.parseInt(vars[0]);
int m = Integer.parseInt(vars[1]);
}
排序篇
我最近常用的几种题目中用到的排序。
小根堆，即最小的元素在根结点
//系统自带小根堆，可以直接将输入的数据进行排序
PriorityQueue heap = new PriorityQueue<>();
int a = 0;
//添加
heap.add(a);
//取出
int h0 = heap.poll();
//大根堆
PriorityQueue maxHeap = new PriorityQueue<>(k,(a,b) -> b-a);
map按照Value从大到小，若Value相同，再按照Key从小到大
Map map = new HashMap();
// map按照Value从大到小，若Value相同，再按照Key从小到大
ArrayList> arrayList = new
ArrayList>(map.entrySet());
Collections.sort(arrayList,new Comparator>(){
public int compare(Entry o1, Entry o2) {
int result = o2.getValue() -o1.getValue();
if(result != 0) {
return result;
}else {
return o1.getKey()-o2.getKey();
}
}
});
//遍历list得到map里面排序后的元素
for(Entry en: arrayList) {
System.out.println(en.getKey()+" "+ en.getValue());
}
}
二维数组int[n][m]的排序，先按第一列排序，相同的话按第二列排序
//先按第一列排序，相同的话按第二列排序
Arrays.sort(num,(o1,o2)->o1[0]-o2[0]==0?o1[1]-o2[1]:o1[0]-o2[0]);
提升篇
一维前缀和
class NumArray {
// 前缀和数组
private int[] preSum;
public NumArray(int[] nums) {
// preSum[0] = 0，便于计算累加和
preSum = new int[nums.length + 1];
// 计算 nums 的累加和
for (int i = 1; i < preSum.length; i++) {
preSum[i] = preSum[i - 1] + nums[i - 1];
}
}
public int sumRange(int left, int right) {
return preSum[right + 1] - preSum[left];
}
}
二维前缀和
class NumMatrix {
// 定义：preSum[i][j] 记录 matrix 中子矩阵 [0, 0, i-1, j-1] 的元素和
private int[][] preSum;
public NumMatrix(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
if (m == 0 || n == 0) return;
// 构造前缀和矩阵
preSum = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// 计算每个矩阵 [0, 0, i, j] 的元素和
preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] + matrix[i - 1][j - 1] - preSum[i-1][j-1];
}
}
}
// 计算子矩阵 [x1, y1, x2, y2] 的元素和
public int sumRegion(int x1, int y1, int x2, int y2) {
// 目标矩阵之和由四个相邻矩阵运算获得
return preSum[x2+1][y2+1] - preSum[x1][y2+1] - preSum[x2+1][y1] + preSum[x1][y1];
}
}
一维差分
// 差分数组工具类
class Difference {
// 差分数组
private int[] diff;
public Difference(int[] nums) {
assert nums.length > 0;
diff = new int[nums.length];
// 根据初始数组构造差分数组
diff[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
diff[i] = nums[i] - nums[i - 1];
}
}
public void increment(int i, int j, int val) {
diff[i] += val;
if (j + 1 < diff.length) {
diff[j + 1] -= val;
}
}
public int[] result() {
int[] res = new int[diff.length];
// 根据差分数组构造结果数组
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
res[i] = res[i - 1] + diff[i];
}
return res;
}
}
二维差分
int [][]a = new int[n + 2][m + 2];//原数组
int [][]b = new int[n + 2][m + 2];//差分数组
for(int i = 1; i <= n; i++) {
split = br.readLine().split(" ");
for(int j = 1; j <= m; j++) {
a[i][j] = Integer.parseInt(split[j - 1]);
b[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1];//初始化差分数组
}
}
for(int i = 0; i < q; i++) {
split = br.readLine().split(" ");
int x1 = Integer.parseInt(split[0]);
int y1 = Integer.parseInt(split[1]);
int x2 = Integer.parseInt(split[2]);
int y2 = Integer.parseInt(split[3]);
int c = Integer.parseInt(split[4]);
b[x1][y1] += c;//差分核心操作
b[x1][y2 + 1] -= c;//减去右边多余的部分
b[x2 + 1][y1] -= c;//减去下边多余的部分
b[x2 + 1][y2 + 1] += c;//将多减去的再加回来
}
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];//利用差分数组求前缀和数组
}
}
具体解法请参考链接
一维前缀和、二维前缀和 小而美的算法技巧：前缀和数组 :: labuladong的算法小抄
一维数组 小而美的算法技巧：差分数组 :: labuladong的算法小抄
二维差分 798. 差分矩阵 Java题解 （二维差分）_深街酒徒*的博客-CSDN博客
有遇到新的话再补，既然各位都看到这里了，就把这些算法抄到书上吧（毕竟考ccf的时候是可以带书的），你们懂的哦，好记性不如打小抄。
抄都抄了，再顺手点个赞再去考试吧。
