java算法和数据结构模板库.zip

# Java-Algorithm-Template `一个真正的鳗` `JDK11` 😨😨😨 ## java算法和数据结构模板库 (更新中😨) ### 重要工具 java快读模板 🤖 ```java class Main { static InputReader in = new InputReader(); static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); static class InputReader { private StringTokenizer st; private BufferedReader bf; public InputReader() { bf = new BufferedReader(new InputStreamReader(System.in)); st = null; } public String next() throws IOException { while (st == null || !st.hasMoreTokens()) { st = new StringTokenizer(bf.readLine()); } return st.nextToken(); } public String nextLine() throws IOException { return bf.readLine(); } public int nextInt() throws IOException { return Integer.parseInt(next()); } public long nextLong() throws IOException { return Long.parseLong(next()); } public double nextDouble() throws IOException { return Double.parseDouble(next()); } } } ``` ### 算法模板 **一些算法小技巧** ```java class Main { // 上取整 void solve(int x, int y) { int ans = (x + y - 1) / y; } // 负数取模 void solve(int p) { int x = -1000; int v = (x % p + p) % p; } } ``` 1. 二进制枚举子集 ```java class Main { void solve(int n) { for (int i = 1; i < (1 << n); i++) { for (int j = i; j; j = (j - 1) & 1) { //... } } } } ``` 2. 快速排序 ```java class Main { void quickSort(int[] q, int l, int r) { int i = l - 1; int j = r + 1; int x = q[l + r >> 1]; while (i < j) { do { i++; } while (q[i] < x); do { j--; } while (q[j] > x); if (i < j) swap(q, i, j); } quickSort(q, l, j); quickSort(q, j+ 1, r); } void swap(int[] q, int i, int j) { q[i] ^= q[j]; q[j] ^= q[i]; q[i] ^= q[j]; } } ``` 3. 归并排序 ```java class Main { int[] tmp; void mergeSort(int[] q, int l, int r) { if (l >= r) return; int mid = l + r >> 1; mergeSort(q, l, mid); mergeSort(q, mid + 1, r); int k = 0; int i = l; int j = mid + 1; while (i <= mid && j <= r) { if (q[i] <= q[j]) tmp[k++] = q[i++]; else tmp[k++] = q[j++]; } while (i <= mid) tmp[k++] = q[i++]; while (j <= r) tmp[k++] = q[j++]; for (i = l, j = 0; i <= r; i++, j++) { q[i] = tmp[j]; } } } ``` 4. **很重要的二分模板** ```java class Main { boolean check(int mid) { // 检查mid是否满足某种性质 一般用于二分答案 // 假如mid满足 那么 [mid+1, r]也满足 // 假如mid不满足 那么 [l, mid-1]也不满足 return true; } // 最大值最小 // 区间[l, r] 被划分为[l, mid] 和 [mid+1, r]时使用 int bSearch1(int l, int r) { while (l < r) { int mid = l + r >> 1; if (check(mid)) { r = mid; } else { l = mid + 1; } } return l; } // 最小值最大 // 区间[l, r] 被划分为[l, mid-1] 和 [mid, r]时使用 int bSearch2(int l, int r) { while (l < r) { int mid = l + r + 1 >> 1; if (check(mid)) { l = mid; } else { r = mid - 1; } } return l; } } ``` 5. 一维前缀和 ```java class Main { void solve(int[] arr, int l, int r) { int n = arr.length; int[] s = new int[n+1]; // 构建前缀和数组 for (int i = 1; i <= n; i++) { s[i] = s[i - 1] + arr[i - 1]; } int sum = sumRange(s, l, r); } // 查询区间和[l, r] int sumRange(int[] s, int l, int r) { return s[r] - s[l-1]; } } ``` 6. 二维前缀和 ```java class Main { void solve(int[][] mat, int x1, int y1, int x2, int y2) { int m = mat.length; int n = mat[0].length; int[][] s = new int[m+10][n+10]; // 构建前缀和数组 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { int x = i + 1, y = j + 1; s[x][y] = mat[i][j]; } } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1]; } } } // (x1, y1)是左上角 (x2,y2)是右下角 int sumRange(int[][] s, int x1, int y1, int x2, int y2) { return s[x2+1][y2+1] - s[x1][y2+1] - s[x2+1][y1] + s[x1][y1]; } } ``` 7. 一维差分 ```java class Main { void solve(int[] arr, int[][] ops, int c) { int n = arr.length; // 给区间 [l, r]中每个数加上 c int[] diff = new int[n+1]; for (int[] o : ops) { int l = o[0], r = o[1]; diff[l] += c; diff[r + 1] -= c; } } } ``` 8. 二分差分 ```java class Main { // n * n的矩阵 void solve(int n, int[][] queries) { int[][] diff = new int[n+2][n+2]; for (int[] q : queries) { // 区间 + 1 int x1 = q[0], y1 = q[1], x2 = q[2], y2 = q[3]; diff[x1+1][y1+1] += 1; diff[x2+2][y1+1] -= 1; diff[x1+1][y2+2] -= 1; diff[x2+2][y2+2] += 1; } int[][] arr = new int[n][n]; // 前缀和还原数组 for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { arr[i-1][j-1] = (diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1]); } } } } ``` 9. 滑动窗口 (元素翻转|替换模板) ```text 这样的题目一般是: 给你一串数字(字符串), 你可以最多翻转k次, 求数组中连续相同字符(数字)的长度 ``` ```java class Main { int solve(String s, int k) { char[] ss = s.toCharArray(); int[] map = new int[26]; int maxCnt = 0; int i = 0, j = 0, ans = 0; while (i < ss.length) { map[ss[i]-'a']++; maxCnt = Math.max(maxCnt, map[ss[i]-'a']); if (i - j + 1 > maxCnt + k) { char l = ss[j]; map[l-'a']--; j++; } ans = Math.max(ans, i - j + 1); i++; } return ans; } } ``` 10. 滑动窗口 (恰好k个模板) ```text 这样的题目一般是求: 给你一个数组, 求出数组中恰好k个满足条件的子数组 问题转换成求 最多满足k个 和 最多满足k-1个子数组的个数 两个作差可求出答案 ``` ```java class Main { // 求出恰好k个奇数的子数组个数 int solve(int[] nums, int k) { return calc(nums, k) - calc(nums, k - 1); } int calc(int[] nums, int k) { int i = 0, j = 0, cnt = 0; int ans = 0; while (i < nums.length) { cnt += (nums[i] & 1); while (cnt > k) { cnt -= (nums[j] & 1); j++; } ans += i - j + 1; i++; } return ans; } } ``` ### 数据结构模板 1. Trie > 一般用于解决字符串前缀匹配相关问题 ```java class Main { Node root = new Node(); // 插入s void insert(String s) { int n = s.length(); var cur = root; for (int i = 0; i < n; i++) { int idx = s.charAt(i) - 'a'; if (cur.son[idx] == null) { cur.son[idx] = new Node(); } cur = cur.son[idx]; } cur.isEnd = t