# 算法的技巧
这里写着一些平时写算法的一些比较使用的点，谈不上思路，套路，模板啥的，就是一些点。
逆推累加和：
tar = k*(k+1)/2，如何逆推 k，直接k = Math.sqrt(2*tar)，这就是sqrt(k*(k+1)) = k，详细应用参考力扣 754 。简洁代码计算前缀和：比如给一个只有 0 和 1 的二维数组，计算连续的 1 的前缀和（从四个方向），参考 LeetCode764。
// 初始化数组，使得下标从 1 开始 | |
int[][] arr = new int[n+10][n+10]; | |
for(int i = 1 ; i <= n ; i++) Arrays.fill(arr[i],1); | |
// 将 arr 的部分元素赋值为 0 | |
for(int i = 0 ; i < mines.length ; i++) arr[mines[i][0]+1][mines[i][1]+1] = 0; | |
// L=left, R=right, U=up, D=down | |
int[][] L = new int[n+10][n+10], R = new int[n+10][n+10], U = new int[n+10][n+10], D = new int[n+10][n+10]; | |
for(int i = 1 ; i <= n ; i++) { | |
for(int j = 1 ; j <= n ;j++) { | |
if(arr[i][j] == 1) { | |
L[i][j] = L[i-1][j] + 1; | |
U[i][j] = U[i][j-1] + 1; | |
} | |
if(arr[n-i+1][n-j+1] == 1) {// 从下向上，从右往左 | |
R[n-i+1][n-j+1] = R[n-i+1][n-j+2] + 1; | |
D[n-i+1][n-j+1] = D[n-i+2][n-j+1] + 1; | |
} | |
} | |
} |
用
Math.max()兜底：举个🌰，动态规划有时不止用到前面一个状态，可能是前面三个状态同时转移到下一个状态，那么我们在转移的时候就要考虑i-3,i-2,i-1的合法性，如果写三个if语句就显得冗余，可以用f[Math.max(0,i-n)]的写法。请注意，这种写法不是适用大多数题的，因为一旦下标不合法，一般就是不需要这个状态，而不是取f[0]这个状态。用到这种技巧的题，可以参考 LeetCode808. 分汤 。Java 里面的优先队列
PriorityQueue是小根堆
PriorityQueue<Integer> minQueue = new PriorityQueue<>((a, b) -> a - b); // 就是默认的小根堆 | |
PriorityQueue<Integer> maxQueue = new PriorityQueue<>((a, b) -> b - a); //b-a 才是大根堆 |
