常用代码模板

Shio2022-08-142024-05-31

【Java版本】常用代码模板

-------基础算法-------

排序

快速排序

代码模板

private void quickSort(int[] arr, int left, int right) {
    // 递归终止条件，如果左边界大于等于右边界则认为递归结束
    if (left >= right) {
        return arr;
    }
    // 设定一个分界值，这里是（left + right）/ 2
    int p = arr[left + right >> 1];
    // 左右提前预留一个位置
    int i = left - 1;
    int j = right + 1;
    while (i < j) {
        // 等效于do while
        // 当数值小于分界值时持续遍历，直到找到第一个大于等于分界值的索引
        // 如果是逆序则调整两个while循环
        while (arr[++i] < p)
            ;
        while (arr[--j] > p)
            ;
        // 交换左右两侧不符合预期的数值
        if (i < j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // 由于分界值取的是left + right >> 1，因此递归取的是left，j j + 1，right
    quickSort(arr, left, j);
    quickSort(arr, j + 1, right);
}

练习题

912. 排序数组

class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    private int[] quickSort(int[] arr, int l, int r) {
       // 待补全的代码模板
    }
}

归并排序

代码模板

private void mergeSort(int[] arr, int left, int right) {
    // 递归终止条件，如果左边界大于等于右边界则认为递归结束
    if (left >= right) {
        return arr;
    }
    // 设定一个分界值，这里是（left + right）/ 2
    int mid = left + right >> 1;
    // 切割
    arr = mergeSort(arr, left, mid);
    arr = mergeSort(arr, mid + 1, right);
    // 归并，长度刚好是 left 到 right
    int[] temp = new int[right - left + 1];
    int i = left;
    int j = mid + 1;
    // 用来归并的索引
    int k = 0;
    while (i <= mid && j <= right) {
        // 如果是逆序则调整if条件
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    // 根据归并后的数组重新赋值排序后的数组
    for (i = left, j = 0; i <= right; i++, j++) {
        arr[i] = temp[j];
    }
}

练习题

class Solution {
    public int[] sortArray(int[] nums) {
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }

    private int[] mergeSort(int[] arr, int left, int right) {
   		// 待补全的代码模板
    }
}

二分法

整数二分

精准查找

代码模板

public int binarySearch(int[] arr, int target) {
    int l = -1;
    int r = nums.length;
    
    while (l + 1 != r) {
        int mid = l + ((r - l) >> 1);
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            r = mid;
        } else {
            l = mid;
        }
    }
    
    return -1;
}

练习题

class Solution {
    public int search(int[] nums, int target) {
       return binarySearch(nums, target);
    }

    public int binarySearch(int[] nums, int target) {
    	// 待补全的模板代码
	}
}

左右查找

代码模板

private int leftBinarySearch(int[] nums, int target) {  
        int l = -1;
    	int r = nums.length;

        while (l + 1 != r) {
            int mid = l + ((r - l) >> 1);
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid;
            }
        }

        if (r < 0 || r >= nums.length || nums[r] != target  ) {
            r = -1;
        }
        return r;   
   
}  

// 区间[left, right]被划分成[left, mid - 1]和[mid, right]时使用：  
// 或者称之为右二分查询，查找右侧最后一个满足条件的数
private int rightBinarySearch(int[] nums, int target) {  
    	int l = -1;
    	int r = nums.length;

        while (l + 1 != r) {
            int mid = l + ((r - l) >> 1);
            if (nums[mid] <= target) {
                l = mid;
            } else {
                r = mid;
            }
        }
    
        if (l < 0 || l >= nums.length || nums[l] != target ) {
            l = -1;
        }
        return l;
}

练习题

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (null == nums || 0 == nums.length) return new int[]{-1, -1};
        int l = leftBinarySearch(nums, target);
        int r = rightBinarySearch(nums, target);
        return new int[]{l, r};
    }
    private int leftBinarySearch(int[] nums, int target) {  
      	// 待补全的模板代码
    }  


    private int rightBinarySearch(int[] nums, int target) {  
    	// 待补全的模板代码
    }
}

浮点数

// 检查x是否满足某种性质  
private static boolean check(double x) {  
   /* ... */  a
}  

// eps 表示精度，取决于题目对精度的要求，默认负六次方
private static double EPS = 1e-6;

private static double floatBinarySearch(double left, double right) {  
   while (right - left > EPS) {  
      double mid = (left + right) / 2;  
      if (check(mid)) {  
         right = mid;  
      } else {  
         left = mid;  
      }  
   }  
   return left;  
}

模板题 AcWing 790. 数的三次方根

import java.util.Scanner;  

public class Main {  

   public static void main(String[] args) {  
      Scanner in = new Scanner(System.in);  
      double x = in.nextDouble();  
      Double left = -Double.MAX_VALUE;  
      Double right = Double.MAX_VALUE;  
      // 由于负六次方精度不够
      while (right - left > 1e-8) {  
         Double mid = (left + right) / 2;  
         if (mid * mid * mid >= x) {  
            right = mid;  
         } else {  
            left = mid;  
         }  
      } 
      // 注意格式化输出字符串
      System.out.printf("%.6f", left);  
   }  
}

快速幂

递归

public int pow(int a, int n) {
   if (n == 0) {
       return 1;
   } else if ((n & 1) == 1) {
       return pow(a, n - 1) * a;
   } else {
       int t = pow (a, n / 2);
       return t 
   }
  
}

迭代

public int pow(int a, int n) {
    int res = 1;
    while (n > 0) {
        if ((n & 1) == 1) res * = a;
        a *= a;
        n >>= 1;
    }
    return res;
}

高精度

高精度加法

/**  
 * 大数据加法  
 */  
private static List<Integer> add(List<Integer> A, List<Integer> B) {  
    // 默认A > B，如果不满足则对调
   if (A.size() < B.size()) {  
      return add(B, A);  
   }  
   int t = 0;  
   List<Integer> C = new ArrayList<>();  
   for (int i = 0; i < A.size(); i++) {  
      t += A.get(i);  
      // 如果在B的范围内，则加B
      if (i < B.size()) {  
         t += B.get(i);  
      } 
      // C记录余数
      C.add(t % 10);  
      t /= 10;  
   }  
   // 进位
   if (t != 0) {  
      C.add(t);  
   }  
   // 去掉开头的零
   while (C.size() > 1 && C.get(C.size() - 1) == 0) {  
      C.remove(C.size() - 1);  
   }  
   return C;  
}

Leetcode暂无练习题, 可用以下代码进行练习

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.ArrayList;  
import java.util.List;  

public class Main {  

   public static void main(String[] args) throws IOException {  
       // 由于数据量较大，使用BufferedReader读取数据
       BufferedReader in = new BufferedReader(new InputStreamReader(System.in));  
       String A = in.readLine();  
       List<Integer> aList = new ArrayList<>();  
       for (int i = A.length() - 1; i >= 0; i--) {  
          aList.add(A.charAt(i) - '0');  
       }  
       String B = in.readLine();  
       List<Integer> bList = new ArrayList<>();  
       for (int i = B.length() - 1; i >= 0; i--) {  
          bList.add(B.charAt(i) - '0');  
       }  
       List<Integer> cList = add(aList, bList);  
       for (int i = cList.size() - 1; i >= 0; i--) {  
          System.out.print(cList.get(i));  
       }  
       // 关闭资源
       in.close();
    }

   /**  
    * 大数据加法  
    */  
   private static List<Integer> add(List<Integer> A, List<Integer> B) {  
      // 模板
   }  
}

高精度减法

private static boolean compare(List<Integer> A, List<Integer> B) {  
    // 优先比较数组长度，长度更大，数值更大
   if (A.size() != B.size()) {  
      return A.size() > B.size();  
   }  
   for (int i = A.size() - 1; i >= 0; i--) {  
      if (A.get(i) == B.get(i)) {  
         continue;  
      }  
      return A.get(i) > B.get(i);  
   }  
   return true;  
}  

/**  
 * 大数据减法  
 */  
private static List<Integer> subtract(List<Integer> A, List<Integer> B) {  
   if (!compare(A, B)) {  
      System.out.print("-");  
      return subtract(B, A);  
   }  
   int t = 0;  
   List<Integer> C = new ArrayList<>();  
   for (int i = 0; i < A.size(); i++) {  
      t = A.get(i) - t;  
      if (i < B.size()) {  
         t -= B.get(i);  
      }  
      C.add((t + 10) % 10);  
      if (t < 0) {  
         t = 1;  
      } else {  
         t = 0;  
      }  
   }  
   while (C.size() > 1 && C.get(C.size() - 1) == 0) {  
      C.remove(C.size() - 1);  
   }  
   return C;  
}

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.ArrayList;  
import java.util.List;  

public class Main {  

   public static void main(String[] args) throws IOException {  
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));  
      String s = in.readLine();  
      List<Integer> A = getIntegerList(s);  
      s = in.readLine();  
      List<Integer> B = getIntegerList(s);  
      List<Integer> C = subtract(A, B);  
      for (int i = C.size() - 1; i >= 0; i--) {  
         System.out.print(C.get(i));  
      }  
      in.close();  
   }  

   /**  
    * 由于是大数据，因此用BufferedReader读取 根据读取的字符串转换成集合  
    */  
   private static List<Integer> getIntegerList(String s) {  
      List<Integer> res = new ArrayList<>(s.length());  
      for (int i = s.length() - 1; i >= 0; i--) {  
         res.add(Character.getNumericValue(s.charAt(i)));  
      }  
      return res;  
   }  

   private static boolean compare(List<Integer> A, List<Integer> B) {  
      if (A.size() != B.size()) {  
         return A.size() > B.size();  
      }  
      for (int i = A.size() - 1; i >= 0; i--) {  
         if (A.get(i) == B.get(i)) {  
            continue;  
         }  
         return A.get(i) > B.get(i);  
      }  
      return true;  
   }  

   /**  
    * 大数据减法  
    */  
   private static List<Integer> subtract(List<Integer> A, List<Integer> B) {  
      if (!compare(A, B)) {  
         System.out.print("-");  
         return subtract(B, A);  
      }  
      int t = 0;  
      List<Integer> C = new ArrayList<>();  
      for (int i = 0; i < A.size(); i++) {  
         t = A.get(i) - t;  
         if (i < B.size()) {  
            t -= B.get(i);  
         }  
         C.add((t + 10) % 10);  
         if (t < 0) {  
            t = 1;  
         } else {  
            t = 0;  
         }  
      }  
      while (C.size() > 1 && C.get(C.size() - 1) == 0) {  
         C.remove(C.size() - 1);  
      }  
      return C;  
   }  
}

高精度乘低精度

/**  
 * 大数据乘法  
 */  
private static List<Integer> subtract(List<Integer> A, Integer b) {  
   List<Integer> C = new ArrayList<>();  
   if (b == 0) {  
      C.add(0);  
      return C;  
   }  
   int t = 0;  
   for (int i = 0; i < A.size(); i++) {  
      t += A.get(i) * b;  
      C.add(t % 10);  
      t /= 10;  
   }  
   if (t != 0) {  
      C.add(t);  
   }  
   while (C.size() > 1 && C.get(C.size() - 1) == 0) {  
      C.remove(C.size() - 1);  
   }  
   return C;  
}

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.ArrayList;  
import java.util.List;  

public class Main {  

   public static void main(String[] args) throws IOException {  
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));  
      String s = in.readLine();  
      List<Integer> A = getIntegerList(s);  
      Integer b = Integer.parseInt(in.readLine());  
      List<Integer> C = subtract(A, b);  
      for (int i = C.size() - 1; i >= 0; i--) {  
         System.out.print(C.get(i));  
      }  
      in.close();  
   }  

   /**  
    * 由于是大数据，因此用BufferedReader读取 根据读取的字符串转换成集合  
    */  
   private static List<Integer> getIntegerList(String s) {  
      List<Integer> res = new ArrayList<>(s.length());  
      for (int i = s.length() - 1; i >= 0; i--) {  
         res.add(Character.getNumericValue(s.charAt(i)));  
      }  
      return res;  
   }  

   /**  
    * 大数据乘法  
    */  
   private static List<Integer> subtract(List<Integer> A, Integer b) {  
      List<Integer> C = new ArrayList<>();  
      if (b == 0) {  
         C.add(0);  
         return C;  
      }  
      int t = 0;  
      for (int i = 0; i < A.size(); i++) {  
         t += A.get(i) * b;  
         C.add(t % 10);  
         t /= 10;  
      }  
      if (t != 0) {  
         C.add(t);  
      }  
      while (C.size() > 1 && C.get(C.size() - 1) == 0) {  
         C.remove(C.size() - 1);  
      }  
      return C;  
   }  
}

高精度除以低精度

/**  
 * 大数据除法  
 */  
private static List<Integer> divide(List<Integer> A, Integer b) {  
   int t = 0;  
   List<Integer> C = new ArrayList<>();  
   for (int i = A.size() - 1; i >= 0; i--) {  
      t = t * 10 + A.get(i);  
      C.add(t / b);  
      t %= b;  
   }  
   Collections.reverse(C);  
   while (C.size() > 1 && C.get(C.size() - 1) == 0) {  
      C.remove(C.size() - 1);  
   }  
   // 为了方便传递，放在了数组的最后一位，因此输出时需要从倒数第二位开始  
   C.add(t);  
   return C;  
}

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.ArrayList;  
import java.util.Collections;  
import java.util.List;  

public class Main {  

   public static void main(String[] args) throws IOException {  
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));  
      String s = in.readLine();  
      List<Integer> A = getIntegerList(s);  
      Integer b = Integer.parseInt(in.readLine());  
      List<Integer> C = divide(A, b);  
      for (int i = C.size() - 2; i >= 0; i--) {  
         System.out.print(C.get(i));  
      }  
      System.out.println();  
      System.out.print(C.get(C.size() - 1));  
      in.close();  
   }  

   /**  
    * 由于是大数据，因此用BufferedReader读取 根据读取的字符串转换成集合  
    */  
   private static List<Integer> getIntegerList(String s) {  
      List<Integer> res = new ArrayList<>(s.length());  
      for (int i = s.length() - 1; i >= 0; i--) {  
         res.add(Character.getNumericValue(s.charAt(i)));  
      }  
      return res;  
   }  

   /**  
    * 大数据除法  
    */  
   private static List<Integer> divide(List<Integer> A, Integer b) {  
      int t = 0;  
      List<Integer> C = new ArrayList<>();  
      for (int i = A.size() - 1; i >= 0; i--) {  
         t = t * 10 + A.get(i);  
         C.add(t / b);  
         t %= b;  
      }  
      Collections.reverse(C);  
      while (C.size() > 1 && C.get(C.size() - 1) == 0) {  
         C.remove(C.size() - 1);  
      }  
      // 为了方便传递，放在了数组的最后一位，因此输出时需要从倒数第二位开始  
      C.add(t);  
      return C;  
   }  
}

前缀和和差分

一维前缀和

代码模板

class PreSum {
    // 前缀和数组
    private int[] preSum;

    /* 输入一个数组，构造前缀和 */
    public PreSum(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];
    }
}

练习题

303. 区域和检索 - 数组不可变

class NumArray {
    PreSum preSum;

    public NumArray(int[] nums) {
        preSum = new PreSum(nums);
    }
    
    public int sumRange(int left, int right) {
        return preSum.sumRange(left, right);
    }
}

class PreSum {
    // 待补全的模板代码
}

二维前缀和

代码模板

class preSum {
     	// 定义：preSum[i][j] 记录 matrix 中子矩阵 [0, 0, i-1, j-1] 的元素和
       private int[][] preSum;

       public preSum(int[][] matrix) {
           int n = matrix.length;
           int m = matrix[0].length;
		
           // 构造前缀和矩阵
           preSum = new int[n + 1][m + 1];
           for (int i = 1; i <= n; i++) {
               for (int j = 1; j <= m; 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];
       }
   }

练习题

363. 矩形区域不超过 K 的最大数值和

class Solution {
    public int maxSumSubmatrix(int[][] matrix, int target) {
        int res = Integer.MIN_VALUE;
        preSum numMatrix = new preSum(matrix);
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                for (int k = i; k < matrix.length; k++) {
                    for (int l = j; l < matrix[0].length; l++) {
                        int temp = numMatrix.sumRegion(i, j, k, l);
                        if (temp > target) {
                            continue;
                        }else {
                            res = res > temp ? res : temp;
                        
                        }
                    }
                }
            }
        }

        return res;
    }

    class preSum {
		// 待补全的模板代码
    }
}

一维差分

代码模板

class Difference {
    
    int[] diff;
    
   	public Difference(int[] nums) {
        diff = new int[nums.length];
        for (int i = 1; i < nums.length; i++) {
            diff[i] = nums[i] - nums[i - 1];
		}
    } 
    
    public void update(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 < res.length; i++) {
            res[i] = res[i - 1] + diff[i];
        }
        return res;
    }
}

练习题

1109. 航班预订统计

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] res = new int[n];
        Difference diff = new Difference(res);
        for (int i = 0; i < bookings.length; i++) {
            diff.update(bookings[i][0] - 1, bookings[i][1] - 1, bookings[i][2]);
        }
        return diff.result();
    }
}

class Difference {
   // 待补全的模板代码
}

二维差分

代码模板

class Difference {
    
    private int[][] matrix; // 存储原始矩阵
    private int[][] diff; // 存储差分矩阵
    
    public Difference(int[][] nums) {
        matrix = nums;
        int n = matrix.length; // 矩阵行数
        int m = matrix[0].length; // 矩阵列数
        diff = new int[n + 1][m + 1]; // 差分矩阵的大小比原始矩阵多1
        // 计算差分矩阵
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 更新差分矩阵
                update(i, j, i, j, matrix[i][j]);
            }
        }
    }

    // 更新差分矩阵
    public void update(int x1, int y1, int x2, int y2, int val) {
        // 更新对应位置的数量
        diff[x1][y1] += val;
        // 右下角的方格减去val
        diff[x2 + 1][y1] -= val;
        // 右下角的方格减去val
        diff[x1][y2 + 1] -= val;
        // 左上角的方格加上val
        diff[x2 + 1][y2 + 1] += val;
    }

    // 获取更新后的矩阵
    public int[][] result() {
        int n = matrix.length; // 矩阵行数
        int m = matrix[0].length; // 矩阵列数
        int[][] res = new int[n][m]; // 存储更新后的矩阵
        res[0][0] = diff[0][0]; // 差分矩阵的第一个元素即为更新后的矩阵的第一个元素
        // 计算第一列的元素值
        for (int i = 1; i < n; i++) {
            res[i][0] = res[i - 1][0] + diff[i][0];
        }
        // 计算第一行的元素值
        for (int i = 1; i < m; i++) {
            res[0][i] = res[0][i - 1] + diff[0][i];
        }

        // 计算其他位置的元素值
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                // 使用差分矩阵计算当前位置的值
                res[i][j] = res[i - 1][j] + res[i][j - 1] - res[i - 1][j - 1] + diff[i][j];
            }
        }

        return res;
    }
}

练习题

2536. 子矩阵元素加 1

class Solution {
    public int[][] rangeAddQueries(int n, int[][] queries) {
        Difference diffeMatrix = new Difference(new int[n][n]);
        for (int i = 0; i < queries.length; i++) { 
            diffeMatrix.update(queries[i][0],
                            queries[i][1],
                            queries[i][2],
                            queries[i][3],
                            1);
        }

        return diffeMatrix.result();
    }

    class Difference {
       // 待补全的代码模板 
    }
    
}

位运算

位1的个数(汉明权重)

代码模板

public int hammingWeight(int n) {
        int count = 0;
        for (int i = n; i != 0; i -= (i & -i)) {
            count++;
        }

        return count;
}

练习题

191. 位1的个数

public class Solution {
   
    public int hammingWeight(int n) {
        // 待补全的代码模板 
    }
   
}

双指针算法

同向指针

代码模板

int slow = 0;
int fast = 0;
while (fast < nums.length()) {
    if (check()) {
        // do something
        slow ++;
    }
    fast ++;
}

练习题

异向指针

int l = 0;
int r = nums.length - 1;

while (l <= r) {
	// do something
	l ++;
	r --;
}

离散化

模板题 AcWing 802. 区间和

// 去重 + 排序  
List<Integer> distinctSorterAlls = alls.stream().distinct().sorted()  
      .collect(Collectors.toList());  

// 离散化映射，把离散化的下标映射到连续的数组下标 + 1
for (int[] item : add) {  
   int index = Collections.binarySearch(distinctSorterAlls, item[0]) + 1;  
   a[index] += item[1];  
}  

// 前缀和  
for (int i = 1; i <= distinctSorterAlls.size(); i++) {  
   s[i] = s[i - 1] + a[i];  
}  

// 离散化映射，把离散化的下标映射到连续的数组下标 + 1 
for (int[] item : query) {  
   int l = Collections.binarySearch(distinctSorterAlls, item[0]) + 1;  
   int r = Collections.binarySearch(distinctSorterAlls, item[1]) + 1;  
   System.out.println(s[r] - s[l - 1]);  
}

模板题 AcWing 802. 区间和

import java.util.ArrayList;  
import java.util.Collections;  
import java.util.List;  
import java.util.Scanner;  
import java.util.stream.Collectors;  

public class Main {  

   private static final int N = 300000;  

   public static void main(String[] args) {  
      Scanner in = new Scanner(System.in);  
      int n = in.nextInt();  
      int m = in.nextInt();  
      List<Integer> alls = new ArrayList<>();  
      int[] a = new int[N];  
      int[] s = new int[N];  
      List<int[]> add = new ArrayList<>();  
      List<int[]> query = new ArrayList<>();  
      for (int i = 0; i < n; i++) {  
         int x = in.nextInt();  
         int c = in.nextInt();  
         add.add(new int[]{x, c});  
         alls.add(x);  
      }  

      for (int i = 0; i < m; i++) {  
         int l = in.nextInt();  
         int r = in.nextInt();  
         query.add(new int[]{l, r});  
         alls.add(l);  
         alls.add(r);  
      }  

      // 去重 + 排序  
      List<Integer> distinctSorterAlls = alls.stream().distinct().sorted()  
            .collect(Collectors.toList());  

      // 离散化映射，把离散化的下标映射到连续的数组下标 + 1      
       for (int[] item : add) {  
         int index = Collections.binarySearch(distinctSorterAlls, item[0]) + 1;  
         a[index] += item[1];  
      }  

      // 前缀和  
      for (int i = 1; i <= distinctSorterAlls.size(); i++) {  
         s[i] = s[i - 1] + a[i];  
      }  

      // 离散化映射，把离散化的下标映射到连续的数组下标 + 1      
       for (int[] item : query) {  
         int l = Collections.binarySearch(distinctSorterAlls, item[0]) + 1;  
         int r = Collections.binarySearch(distinctSorterAlls, item[1]) + 1;  
         System.out.println(s[r] - s[l - 1]);  
      }  
   }  
}

区间合并

代码模板

public int[][] merge(int[][] intervals) {
	LinkedList<int[]> res = new LinkedList<>();
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]); 
    res.add(intervals[0]);
    for (int i = 1; i < intervals.length; i++) {
        int[] cur = intervals[i];
        int[] last = res.getLast();
        if (cur[0] <= last[1]) {
            last[1] = Math.max(last[1], cur[1]);
        } else {
            res.add(cur);
        }
    }
       return res.toArray(new int[res.size()][2]);
}

练习题

56. 合并区间

public int[][] merge(int[][] intervals) {
        // 待补全的模板代码
}

-------图论算法-------

构建邻接表

代码模板

List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
    // 初始化邻接表
    List<Integer>[] graph = new LinkedList[numCourses];
    for (int i = 0; i < numCourses; i++) {
        graph[i] = new LinkedList<>();
    }
    // 填充邻接表
    for (int[] edge : prerequisites) {
        int from = edge[1], to = edge[0];
        graph[from].add(to);
    }
    return graph;
}

环路检测

代码模板

// 正在遍历的路径上的结点
boolean[] onPath;
// 访问过的结点
boolean[] visited;
// 是否存在环
boolean hasCycle = false;

void traverse(List<Integer>[] graph, int cur) {
    if (onPath[cur]) {
        hasCycle = true;
    }
    if (visited[cur] || hasCycle) {
        return;
    }
    // 将结点标志为已遍历
    visited[cur] = true;
    // 开始遍历s结点
    onPath[cur] = true;
    for (int next : graph[cur]) {
        traverse(graph,  next);
    }
    // 结点s遍历完成
    onPath[cur] = false;
}

模板题

207. 课程表

class Solution {
    
    // 正在遍历的路径上的结点
    boolean[] onPath;
    // 访问过的结点has
    boolean[] visited;
    // 是否存在环
    boolean hasCycle = false;
 
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = buildGraph(numCourses, prerequisites);
        visited = new boolean[numCourses];
        onPath = new boolean[numCourses];
		
        for (int i = 0; i < numCourses; i++) {
            // 遍历图中的所有节点
            traverse(graph, i);
        }
        // 只要没有循环依赖可以完成所有课程
        return !hasCycle;
        
    }
   
    void traverse(List<Integer>[] graph, int s) {
        // 待补全的模板代码
    }

    List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
        // 待补全的模板代码
    }
}

拓扑排序

代码模板

// 正在遍历的路径上的结点
boolean[] onPath;
// 访问过的结点
boolean[] visited;
// 是否存在环
boolean hasCycle = false;
// 后序遍历结果
List<Integer> postorder = new ArrayList<>();

// 拓扑排序就是将后序遍历翻转
public int[] topologicalSort(int num, int[][] depends) {
    List<Integer>[] graph = buildGraph(num, depends);
    visited = new boolean[num];
    onPath = new boolean[num];

    for (int i = 0; i < num; i++) {
        traverse(graph, i);
    }

    if (hasCycle) {
        return new int[]{};
    }
    Collections.reverse(postorder);
    return postorder.stream().mapToInt(Integer::intValue).toArray();
}

public void traverse(List<Integer>[] graph, int cur) {
    if (onPath[cur]) {
        hasCycle = true;
    }
    if (visited[cur] || hasCycle) {
        return;
    }
    visited[cur] = true;
    onPath[cur] = true;
    for (int next : graph[cur]) {
        traverse(graph, next);
    }

    postorder.add(cur);
    onPath[cur] = false;
}

模板题

210. 课程表 II

class Solution {

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        return topologicalSort(numCourses, prerequisites);
    }

    
    public int[] topologicalSort(int num, int[][] depends) {
       // 待补全的模板代码
    }

    public void traverse(List<Integer>[] graph, int cur) {
       // 待补全的模板代码
    }    

    List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
       // 待补全的模板代码
    }

}

并查集

代码模板

class UF {
    private int count;
    private int[] parent;
    
    public UF(int n){
        this.count = 0;
        this.parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
	}
    
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ)
            return;
        parent[rootP] = rootQ;
        count--;
    }
        
   	public boolean connected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }
    
    public int find(int x) {
        if (x != parent[x]) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
        // 迭代写法
        // while (parent[x] != x) {
            // parent[x] = parent[parent[x]];
            // x = parent[x];
        // }
        // return x;
    }
    
    public int count() {
        return count;
    }
}

练习题

990. 等式方程的可满足性

class Solution {
    public boolean equationsPossible(String[] equations) {
        UF uf = new UF(26);
        for (int i = 0; i < equations.length; i++) {
            if (getOperator(equations[i]).equals("==")) {
                uf.union(getLeft(equations[i]), getRight(equations[i]));
            }
        }

        for (int i = 0; i < equations.length; i++) {
            if (getOperator(equations[i]).equals("!=")) {
                if (uf.connected(getLeft(equations[i]), getRight(equations[i])))
                    return false;
            }
        }
        return true;
    }

    private String getOperator(String s) {
        return s.substring(1, 3);
    }

    private int getLeft(String s) {
        return s.substring(0, 1).charAt(0) - 'a';
    }

    private int getRight(String s) {
        return s.substring(3).charAt(0) - 'a';
    }
}

class UF {
    // 待补全的模板代码
}

二分图

~~~





## -------面试常考-------



## 二叉树前中后序遍历

### 递归



**代码模板**

~~~java
public void order(List<Integer> res, TreeNode root) {
    if (null == root) return
        
    // 前序遍历
    res.add(root.val);
  	order(res, root.left);
    order(res, root.right);
        
    // 中序遍历
    // order(res, root.left);
    // res.add(root.val);
    // order(res, root.right);
    
    // 后序遍历
    // order(res, root.left);
    // order(res, root.right);
    // res.add(root.val);
    
    
}

迭代

颜色标记法

白色 : 第一次访问为白色, 需要"变色"成黑色(此处为在顶部多放置一个null结点来表示变色操作)
黑色: 结点为黑色, 可直接取出进行操作

代码模板

public List<Integer> orderTraversal(TreeNode root) {

        if (null == root) return new LinkedList<>();

        List<Integer> res = new LinkedList<>();
        Deque<TreeNode> stack = new LinkedList<>();

        stack.push(root);

        while (!stack.isEmpty()) {

            if (null != stack.peek()) {

                TreeNode node = stack.pop();
                
                // 前序遍历
                if (null != node.right) stack.push(node.right);
                if (null != node.left) stack.push(node.left);
                stack.push(node);
                stack.push(null);
                
                // 中序遍历
                // if (null != node.right) stack.push(node.right);
                // stack.push(node);
                // stack.push(null);
                // if (null != node.left) stack.push(node.left);
                
                // 后序遍历
                // stack.push(node);
                // stack.push(null);
                // if (null != node.right) stack.push(node.right);
                // if (null != node.left) stack.push(node.left);
                

            } else {

                stack.pop();
                TreeNode node = stack.pop();
                res.add(node.val);

            }
        }

        return res;
    }

模板题

144. 二叉树的前序遍历 - 力扣（LeetCode）

94. 二叉树的中序遍历 - 力扣（LeetCode）

145. 二叉树的后序遍历 - 力扣（LeetCode）

蓝桥杯

素数

求1 - n之间的素数

埃氏筛

public static boolean[] getPrimes(int n) {
		boolean[] primes = new boolean[n + 1];
		primes[1] = true;
		for (int i = 2; i <= n; i++) {
			if (!primes[i]) {
				for (int j = i * i; j <= n; j += i) {
					primes[j] = true;
				}
			}
		}
		return primes;
}

测试程序

public static void main(String[] args) {
		boolean[] result = getPrimes(100);
		IntStream.range(0, result.length)
        	.filter(i -> !result[i]) 
        	.forEach(i -> System.out.print(i + " "));
		
}

欧拉筛(线性筛)

public static int[] getPrimes(int n) {
		int[] primes = new int[n + 1];
		boolean[] vis = new boolean[n + 1];
		int pos = 0;
		for (int i = 2; i <= n; i++) {
			if (!vis[i]) {
				primes[++pos] = i;
			}
			for (int j = 1; i* primes[j] <= n; j++) {
				vis[i * primes[j]] = true;
				if (i % primes[j] == 0)
					break;
			}
		}
		return primes;
}

测试程序

public static void main(String[] args) {
		int[] result = getPrimes(100);
		
		Arrays.stream(result)
			.filter(i -> i != 0)
        	.forEach(i -> System.out.print(i + " "));
}

最小公倍数和最大公约数

求最大公约数

public static long gcd(long a, long b) {
    long c = 0;
    while (b != 0) {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

测试程序

public static void main(String[] args) {
		long a = 15;
		long b = 12;
		System.out.println(gcd(a, b));
}

求最小公倍数

同上求最大公约数

测试程序

public static void main(String[] args) {
		long a = 15;
		long b = 12;
		System.out.println(a * b / gcd(a, b));
}

快速输入输出模板

import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;


public class Template {
	public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
	public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
	
	static {
		cin.ordinaryChars('0', '0');
		cin.wordChars('0', '9');
		cin.ordinaryChar('-');
		cin.wordChars('-', '-');
	}
	
	public static void main(String[] args) throws Exception{
//		int a = nextInt();
//		long b = nextLong();
//		double c = nextDouble();
//		String d = nextString();
//		cout.println(a);
//		cout.println(b);
//		cout.println(c);
//		cout.println(d);
		cout.flush();
		closeAll();
	}
	
	public static int nextInt() throws Exception {
		cin.nextToken();
		return Integer.parseInt(cin.sval);
	}
	
	public static long nextLong() throws Exception {
		cin.nextToken();
		return Long.parseLong(cin.sval);
	}
	
	public static double nextDouble() throws Exception {
		cin.nextToken();
		return Double.parseDouble(cin.sval);
	}
	
	public static String nextString() throws Exception {
		cin.nextToken();
		return cin.sval;
	}
	
	public static void closeAll() throws Exception {
		in.close();
		out.close();
		cout.close();
	}
}