【Java版本】常用代码模板1——基础算法 + 模板题参考实现

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

【Java版本】常用代码模板1——基础算法 + 模板题参考实现

作者：

我是管小亮 , 2023-03-02 08:01:08 , 所有人可见 , 阅读 8611

142

276

一、快速排序算法模板 —— 模板题 AcWing 785. 快速排序

快速排序本质上就是分治！

private static int[] 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);
    return arr;
}

模板题 AcWing 785. 快速排序

import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        // Java8
        // IntStream.range等效于for循环
        // toArray生成数组
        int[] arr = IntStream.range(0, n).map(i -> in.nextInt()).toArray();
        int[] sortedArr = quickSort(arr, 0, n - 1);
        IntStream.range(0, n).mapToObj(i -> sortedArr[i] + " ").forEach(System.out::print);
        /*
        for (int i = 0; i < n; i++) {
            int a = in.nextInt();
            arr[i] = a;
        }
        int[] sortedArr = quickSort(arr, 0, n - 1);
        for (int i = 0; i < n; i++) {
            System.out.print(sortedArr[i] + " ");
        }
        */
    }

    private static int[] quickSort(int[] arr, int left, int right) {
        。。。。。。可参考上述实现
    }
}

二、归并排序算法模板 —— 模板题 AcWing 787. 归并排序

归并排序本质上就是分治！

private static int[] 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];
    }
    return arr;
}

模板题 AcWing 787. 归并排序

import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        // Java8，可参考上面普通写法
        int[] arr = IntStream.range(0, n).map(i -> in.nextInt()).toArray();
        int[] sortedArr = mergeSort(arr, 0, n - 1);
        IntStream.range(0, n).mapToObj(i -> sortedArr[i] + " ").forEach(System.out::print);
    }

    private static int[] mergeSort(int[] arr, int left, int right) {
        。。。。。。
    }
}

三、整数二分算法模板 —— 模板题 AcWing 789. 数的范围

两种模板，分别是 LBS，和 RBS

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

// 区间[left, right]被划分成[left, mid]和[mid + 1, right]时使用： 
// 或者称之为左二分查询，查找左侧第一个满足条件的数
private static int leftBinarySearch(int[] arr, int left, int right) {  
   while (left < right) {  
      int mid = arr[left + right >> 1];  
      if (check(mid)) {  
         right = mid;    // check()判断mid是否满足性质  
      } else {  
         left = mid + 1;  
      }  
   }  
   return left;  
}  

// 区间[left, right]被划分成[left, mid - 1]和[mid, right]时使用：  
// 或者称之为右二分查询，查找右侧最后一个满足条件的数
private static int rightBinarySearch(int[] arr, int left, int right) {  
   while (left < right) {  
      int mid = arr[left + right + 1 >> 1];  
      if (check(mid)) {  
         left = mid;    // check()判断mid是否满足性质  
      } else {  
         right = mid - 1;  // 有加必有减
      }  
   }  
   return left;  
}

模板题 AcWing 789. 数的范围

import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int q = in.nextInt();
        int[] arr = IntStream.range(0, n).map(item -> in.nextInt()).toArray();
        while (q-- > 0) {
            int k = in.nextInt();
            int[] ans = binarySearch(arr, k);
            IntStream.range(0, 2).mapToObj(item -> ans[item] + " ").forEach(System.out::print);
            System.out.println();
        }
    }

    private static int[] binarySearch(int[] arr, int target) {
        // 将返回值放到一个长度为2的数组中
        int[] res = new int[2];
        int n = arr.length;
        int left = 0;
        int right = n - 1;
        // 先LBS，找到左边界
        while (left < right) {
            int mid = left + right >> 1;
            if (arr[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        // 如果没有找到，则默认-1 -1
        if (arr[left] != target) {
            return new int[]{-1, -1};
        }
        res[0] = left;
        left = 0;
        right = n - 1;
        // 再RBS，找到右边界
        while (left < right) {
            int mid = left + right + 1 >> 1;
            if (arr[mid] <= target) {
                left = mid;
            } else {
                right = mid - 1; // 有加必有减
            }
        }
        res[1] = left;
        return res;
    }
}

四、浮点数二分算法模板 —— 模板题 AcWing 790. 数的三次方根

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

// 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);  
   }  
}

五、高精度加法 —— 模板题 AcWing 791. 高精度加法

/**  
 * 大数据加法  
 */  
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;  
}

模板题 AcWing 791. 高精度加法

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) {  
      。。。。。。可参考上述实现
   }  
}

六、高精度减法 —— 模板题 AcWing 792. 高精度减法

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;  
}

模板题 AcWing 792. 高精度减法

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;  
   }  
}

七、高精度乘低精度 —— 模板题 AcWing 793. 高精度乘法

/**  
 * 大数据乘法  
 */  
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;  
}

模板题 AcWing 793. 高精度乘法

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;  
   }  
}

八、高精度除以低精度 —— 模板题 AcWing 794. 高精度除法

/**  
 * 大数据除法  
 */  
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;  
}

模板题 AcWing 794. 高精度除法

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;  
   }  
}

九、一维前缀和 —— 模板题 AcWing 795. 前缀和

S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

private static final int N = 100010;
private static final int[] a = new int[N + 5];
private static final int[] s = new int[N + 5];

private static void init(int n) {  
   for (int i = 1; i <= n; i++) {  
      s[i] = s[i - 1] + a[i];  
   }  
}  

private static int sumPrefix(int left, int right) {  
   return s[right] - s[left - 1];  
}

模板题 AcWing 795. 前缀和

import java.io.IOException;  
import java.util.Scanner;  

public class Main {  

   private static final int N = 100010;  
   private static final int[] a = new int[N + 5];  
   private static final int[] s = new int[N + 5];  

   public static void main(String[] args) throws IOException {  
      Scanner in = new Scanner(System.in);  
      int n = in.nextInt();  
      int m = in.nextInt();  
      for (int i = 1; i <= n; i++) {  
         a[i] = in.nextInt();  
      }  
      init(n);  
      while (m-- > 0) {  
         int l = in.nextInt();  
         int r = in.nextInt();  
         int res = sumPrefix(l, r);  
         System.out.println(res);  
      }  
   }  

   private static void init(int n) {  
      for (int i = 1; i <= n; i++) {  
         s[i] = s[i - 1] + a[i];  
      }  
   }  

   private static int sumPrefix(int left, int right) {  
      return s[right] - s[left - 1];  
   }  
}

十、二维前缀和 —— 模板题 AcWing 796. 子矩阵的和

S[i, j] = 第 i 行 j 列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1-1, y2] - S[x2, y1-1] + S[x1-1, y1-1]

private static final int N = 1010;  
private static final int[][] a = new int[N + 5][N + 5];  
private static final int[][] s = new int[N + 5][N + 5];

private static void init(int n, int m) {  
   for (int i = 1; i <= n; i++) {  
      for (int j = 1; j <= m; j++) {  
         s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];  
      }  
   }  
}  

private static int sumPrefix(int x1, int y1, int x2, int y2) {  
   return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];  
}

模板题 AcWing 796. 子矩阵的和

import java.io.IOException;  
import java.util.Scanner;  

public class Main {  

   private static final int N = 1010;  
   private static final int[][] a = new int[N + 5][N + 5];  
   private static final int[][] s = new int[N + 5][N + 5];  

   public static void main(String[] args) throws IOException {  
      Scanner in = new Scanner(System.in);  
      int n = in.nextInt();  
      int m = in.nextInt();  
      int q = in.nextInt();  
      for (int i = 1; i <= n; i++) {  
         for (int j = 1; j <= m; j++) {  
            a[i][j] = in.nextInt();  
         }  
      }  
      init(n, m);  
      while (q-- > 0) {  
         int x1 = in.nextInt();  
         int y1 = in.nextInt();  
         int x2 = in.nextInt();  
         int y2 = in.nextInt();  
         int res = sumPrefix(x1, y1, x2, y2);  
         System.out.println(res);  
      }  
   }  

   private static void init(int n, int m) {  
      for (int i = 1; i <= n; i++) {  
         for (int j = 1; j <= m; j++) {  
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];  
         }  
      }  
   }  

   private static int sumPrefix(int x1, int y1, int x2, int y2) {  
      return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];  
   }  
}

十一、一维差分 —— 模板题 AcWing 797. 差分

给区间[l, r]中的每个数加上 c：B[l] += c, B[r + 1] -= c

private static final int N = 100010;  
private static final int[] a = new int[N + 5];  
private static final int[] b = new int[N + 5];

private static void init(int n) {  
   for (int i = 1; i <= n; i++) {  
      b[i] = a[i] - a[i - 1];  
   }  
}  

private static void difference(int left, int right, int c) {  
   b[left] += c;  
   b[right + 1] -= c;  
}

模板题 AcWing 797. 差分

import java.io.IOException;  
import java.util.Scanner;  
import java.util.stream.IntStream;  

public class Main {  

   private static final int N = 100010;  
   private static final int[] a = new int[N + 5];  
   private static final int[] b = new int[N + 5];  

   public static void main(String[] args) throws IOException {  
      Scanner in = new Scanner(System.in);  
      int n = in.nextInt();  
      int m = in.nextInt();  
      IntStream.rangeClosed(1, n).forEach(i -> a[i] = in.nextInt());  
      init(n);  
      while (m-- > 0) {  
         int left = in.nextInt();  
         int right = in.nextInt();  
         int c = in.nextInt();  
         difference(left, right, c);  
      }  
      for (int i = 1; i <= n; i++) {  
//       a[i] = a[i - 1] + b[i];  
//       System.out.print(a[i] + " ");  
         b[i] += b[i - 1];  
         System.out.print(b[i] + " ");  
      }  
   }  

   private static void init(int n) {  
      for (int i = 1; i <= n; i++) {  
         b[i] = a[i] - a[i - 1];  
      }  
   }  

   private static void difference(int left, int right, int c) {  
      b[left] += c;  
      b[right + 1] -= c;  
   }  
}

十二、二维差分 —— 模板题 AcWing 798. 差分矩阵

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上 c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

private static final int N = 1010;  
private static final int[][] a = new int[N + 5][N + 5];  
private static final int[][] s = new int[N + 5][N + 5];  
private static final int[][] b = new int[N + 5][N + 5];

private static void difference(int x1, int y1, int x2, int y2, int c) {  
   b[x1][y1] += c;  
   b[x2 + 1][y1] -= c;  
   b[x1][y2 + 1] -= c;  
   b[x2 + 1][y2 + 1] += c;  
}  

private static void sumPrefix(int n, int m) {  
   for (int i = 1; i <= n; i++) {  
      for (int j = 1; j <= m; j++) {  
         s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + b[i][j];  
      }  
   }  
}

模板题 AcWing 798. 差分矩阵

import java.io.IOException;  
import java.util.Scanner;  

public class Main {  

   private static final int N = 1010;  
   private static final int[][] a = new int[N + 5][N + 5];  
   private static final int[][] s = new int[N + 5][N + 5];  
   private static final int[][] b = new int[N + 5][N + 5];  

   public static void main(String[] args) throws IOException {  
      Scanner in = new Scanner(System.in);  
      int n = in.nextInt();  
      int m = in.nextInt();  
      int q = in.nextInt();  
      for (int i = 1; i <= n; i++) {  
         for (int j = 1; j <= m; j++) {  
            a[i][j] = in.nextInt();  
            difference(i, j, i, j, a[i][j]);  
         }  
      }  
      while (q-- > 0) {  
         int x1 = in.nextInt();  
         int y1 = in.nextInt();  
         int x2 = in.nextInt();  
         int y2 = in.nextInt();  
         int c = in.nextInt();  
         difference(x1, y1, x2, y2, c);  
      }  
      sumPrefix(n, m);  
      for (int i = 1; i <= n; i++) {  
         for (int j = 1; j <= m; j++) {  
            System.out.print(s[i][j] + " ");  
         }  
         System.out.println();  
      }  
   }  

   private static void difference(int x1, int y1, int x2, int y2, int c) {  
      b[x1][y1] += c;  
      b[x2 + 1][y1] -= c;  
      b[x1][y2 + 1] -= c;  
      b[x2 + 1][y2 + 1] += c;  
   }  

   private static void sumPrefix(int n, int m) {  
      for (int i = 1; i <= n; i++) {  
         for (int j = 1; j <= m; j++) {  
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + b[i][j];  
         }  
      }  
   }  
}

十三、位运算 —— 模板题 AcWing 801. 二进制中 1 的个数

private static int countDigitOne(int x) {  
   int count = 0;  
   for (int i = x; i != 0; i -= (i & -i)) {  
      count++;  
   }  
   return count;  
}

模板题 AcWing 801. 二进制中 1 的个数

import java.io.IOException;  
import java.util.Scanner;  
import java.util.stream.IntStream;  

public class Main {  

   public static void main(String[] args) throws IOException {  
      Scanner in = new Scanner(System.in);  
      int n = in.nextInt();  
      int[] a = new int[n + 5];  
      IntStream.range(0, n).forEach(i -> a[i] = in.nextInt());  
      IntStream.range(0, n).mapToObj(i -> countDigitOne(a[i]) + " ").forEach(System.out::print);  
   }  

   private static int countDigitOne(int x) {  
      int count = 0;  
      for (int i = x; i != 0; i -= (i & -i)) {  
         count++;  
      }  
      return count;  
   }  
}

十四、双指针算法 —— 模板题 AcWIng 799. 最长连续不重复子序列， AcWing 800. 数组元素的目标和

for (int i = 0, j = 0; i < n; i ++ ) {
    while (j < i && check(i, j)) {
        j ++ ;
    }
    // 具体问题的逻辑
}

模板题 AcWIng 799. 最长连续不重复子序列

import java.io.IOException;  
import java.util.HashMap;  
import java.util.Map;  
import java.util.Scanner;  
import java.util.stream.IntStream;  

public class Main {  

   public static void main(String[] args) throws IOException {  
      Scanner in = new Scanner(System.in);  
      int n = in.nextInt();  
      int[] a = new int[n + 5];  
      IntStream.range(0, n).forEach(i -> a[i] = in.nextInt());  
      int res = twoPoints(a, n);  
      System.out.println(res);  
   }  

   private static int twoPoints(int[] a, int n) {  
      int res = 0;  
      Map<Integer, Integer> map = new HashMap<>();  
      int j = 0;  
      for (int i = 0; i < n; i++) {  
         map.put(a[i], map.getOrDefault(a[i], 0) + 1);  
         while (j < i && map.get(a[i]) > 1) {  
            map.put(a[j], map.getOrDefault(a[j], 0) - 1);  
            j++;  
         }  
         res = Math.max(res, i - j + 1);  
      }  
      return res;  
   }  
}

模板题 AcWing 800. 数组元素的目标和

import java.io.IOException;  
import java.util.ArrayList;  
import java.util.List;  
import java.util.Scanner;  
import java.util.stream.IntStream;  

public class Main {  

   public static void main(String[] args) throws IOException {  
      Scanner in = new Scanner(System.in);  
      int n = in.nextInt();  
      int m = in.nextInt();  
      int x = in.nextInt();  
      int[] a = new int[n + 5];  
      IntStream.range(0, n).forEach(i -> a[i] = in.nextInt());  
      int[] b = new int[m + 5];  
      IntStream.range(0, m).forEach(i -> b[i] = in.nextInt());  
      List<int[]> res = twoPoints(a, n, b, m, x);  
      res.forEach(item -> System.out.println(item[0] + " " + item[1]));  
   }  

   private static List<int[]> twoPoints(int[] a, int n, int[] b, int m, int x) {  
      List<int[]> res = new ArrayList<>();  
      for (int i = 0, j = m - 1; i < n; i++) {  
         while (j >= 0 && a[i] + b[j] > x) {  
            j--;  
         }  
         if (j >= 0 && a[i] + b[j] == x) {  
            res.add(new int[]{i, j});  
         }  
      }  
      return res;  
   }  
}

十五、离散化 —— 模板题 AcWing 802. 区间和

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

// 离散化映射，把离散化的下标映射到连续的数组下标 + 1for (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];  
}  

// 离散化映射，把离散化的下标映射到连续的数组下标 + 1for (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]);  
      }  
   }  
}

十六、区间合并 —— 模板题 AcWing 803. 区间合并

private static int[][] merge(int[][] a) {  
   if (a == null || a.length == 0 || a[0].length == 0) {  
      return new int[0][2];  
   }  
   Arrays.sort(a, Comparator.comparingInt(item -> item[0]));  
   List<int[]> res = new ArrayList<>();  
   for (int[] arr : a) {  
      int left = arr[0];  
      int right = arr[1];  
      if (res.size() == 0 || res.get(res.size() - 1)[1] < left) {  
         res.add(new int[]{left, right});  
      } else {  
         int newRight = Math.max(res.get(res.size() - 1)[1], left);  
         res.set(res.size() - 1, new int[]{res.get(res.size() - 1)[0], newRight});  
      }  
   }  
   return res.toArray(new int[res.size()][2]);  
}

模板题 AcWing 803. 区间合并

import java.util.ArrayList;  
import java.util.Arrays;  
import java.util.Comparator;  
import java.util.List;  
import java.util.Scanner;  
import java.util.stream.IntStream;  

public class Main {  

   public static void main(String[] args) {  
      Scanner in = new Scanner(System.in);  
      int n = in.nextInt();  
      int[][] a = new int[n][2];  
      IntStream.range(0, n).forEach(i -> {  
         int l = in.nextInt();  
         a[i][0] = l;  
         int r = in.nextInt();  
         a[i][1] = r;  
      });  
      int[][] res = merge(a);  
      System.out.println(res.length);  
   }  

   private static int[][] merge(int[][] a) {  
      if (a == null || a.length == 0 || a[0].length == 0) {  
         return new int[0][2];  
      }  
      Arrays.sort(a, Comparator.comparingInt(item -> item[0]));  
      List<int[]> res = new ArrayList<>();  
      for (int[] arr : a) {  
         int left = arr[0];  
         int right = arr[1];  
         if (res.size() == 0 || res.get(res.size() - 1)[1] < left) {  
            res.add(new int[]{left, right});  
         } else {  
            int newRight = Math.max(res.get(res.size() - 1)[1], right);  
            res.set(res.size() - 1, new int[]{res.get(res.size() - 1)[0], newRight});  
         }  
      }  
      return res.toArray(new int[res.size()][2]);  
   }  
}

29 评论

这就敲给你看 8个月前

大佬写的真好，JS输入输出等数据处理，每次都是自己手敲的吗，我是写JS的，每次做题在处理数据输入和输出感觉会很困扰，想问下大佬这些输入输出方式是自己每次手敲还是直接复制粘贴呢？

VinciWu 2023-04-11 22:02

我是管小亮 2023-11-12 20:11

：）

梅故 17天前

arraylist有sort方法，传入一个comparator比较器就行，可以不用二维数组来回倒腾

sections.sort(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });