难搞的算法都给我退！退！退！

输入篇

小数据都可以用 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<Integer> heap = new PriorityQueue<>(); int a = 0; //添加 heap.add(a); //取出 int h0 = heap.poll(); //大根堆 PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k,(a,b) -> b-a);

 map按照Value从大到小，若Value相同，再按照Key从小到大

Map<Integer,Integer> map = new HashMap<Integer,Integer>(); // map按照Value从大到小，若Value相同，再按照Key从小到大     ArrayList<Map.Entry<Integer,Integer>> arrayList = new ArrayList<Map.Entry<Integer,Integer>>(map.entrySet());
 
    Collections.sort(arrayList,new Comparator<Map.Entry<Integer,Integer>>(){
 
        public int compare(Entry<Integer, Integer> o1, Entry<Integer, Integer> o2) {
            int result = o2.getValue() -o1.getValue();
            if(result != 0) {
                return result;
            }else {
                return o1.getKey()-o2.getKey();
            }    
        }
    });
    //遍历list得到map里面排序后的元素     for(Entry<Integer,Integer> 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];
        }
    } /* 查询闭区间 [left, right] 的累加和 */ 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];
        }
    } /* 给闭区间 [i, j] 增加 val（可以是负数）*/ 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博客