本文最后更新于2021年11月3日,已超过 6 个月没更新!
第一讲 基础算法
快速排序
import java.util.*;
public class Main{
static Random random = new Random();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; ++ i) a[i] = sc.nextInt();
quickSort(a, 0, n - 1);
for (int i = 0; i < n; ++ i)
System.out.print(a[i] + " ");
}
public static void quickSort(int[] nums, int start, int end) {
if (start >= end) return;
int i = start, j = end;
// 随机数
int randIdx = random.nextInt(j - i + 1) + i;
swap (nums, i, randIdx);
int pivot = nums[i];
while (i < j) {
while (i < j && nums[j] >= pivot) -- j;
if (i < j) nums[i] = nums[j];
while (i < j && nums[i] <= pivot) ++ i;
if (i < j) nums[j] = nums[i];
}
nums[i] = pivot;
quickSort(nums, start, i - 1);
quickSort(nums, i + 1, end);
}
public static void swap (int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
第k个数
import java.util.*;
public class Main{
static Random random = new Random();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), k = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; ++ i) a[i] = sc.nextInt();
System.out.println(quickSortSelect(a, 0, n - 1, k - 1));
}
public static int quickSortSelect(int[] nums, int start, int end, int k) {
int i = start, j = end;
// 随机数
int randIdx = random.nextInt(j - i + 1) + i;
swap (nums, i, randIdx);
int pivot = nums[i];
while (i < j) {
while (i < j && nums[j] >= pivot) -- j;
if (i < j) nums[i] = nums[j];
while (i < j && nums[i] <= pivot) ++ i;
if (i < j) nums[j] = nums[i];
}
nums[i] = pivot;
if (k == i) return nums[i];
else if (k < i) return quickSortSelect(nums, start, i - 1, k);
else return quickSortSelect(nums, i + 1, end, k);
}
public static void swap (int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
二分
数的范围
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), q = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; ++ i) nums[i] = sc.nextInt();
while (q-- > 0) {
int tar = sc.nextInt();
int l1 = 0, r1 = n - 1;
// 找大于等于 tar 的最右边的数
// 未找到会停留在比tar的大的那个数上
while (l1 < r1) {
int mid = (l1 + r1) >> 1;
if (nums[mid] >= tar) r1 = mid;
else l1 = mid + 1;
}
if (nums[l1] != tar) System.out.println("-1 -1");
else {
int l2 = 0, r2 = n - 1;
// 找小于等于 tar 的最左边的数
// 未找到会停留在比tar的小的那个数上
while (l2 < r2) {
int mid = (l2 + r2 + 1) >> 1;
if (nums[mid] <= tar) l2 = mid;
else r2 = mid - 1;
}
System.out.println(l1 + " " + l2);
}
}
}
}
数的三次方根
import java.util.*;
/**
* 如果题目中要求保留4位小数,EPS取1e-6,如果题目中要求保留6位小数,那EPS取1e-8
*/
public class Main{
static double EPS = 1e-8;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
double n = sc.nextDouble();
double l = -10000, r = 10000;
while (r - l > EPS) {
double m = (l + r) / 2;
if (m * m * m >= n) r = m;
else l = m;
}
System.out.printf("%.6f\n",l);
}
}
浮点数二分模板
double l = a, r = b;
while(r - l > eps){
double mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
高精度
高精度加法
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s1 = sc.nextLine();
String s2 = sc.nextLine();
int len1 = s1.length(), len2 = s2.length();
StringBuilder sb = new StringBuilder();
// add
int t = 0;
for (int i = len1 - 1, j = len2 - 1; i >= 0 || j >= 0; -- i, -- j) {
if (i >= 0) t += s1.charAt(i) - '0';
if (j >= 0) t += s2.charAt(j) - '0';
sb.append(t % 10);
t /= 10;
}
if (t == 1) sb.append(t);
System.out.println(sb.reverse());
}
}
高精度减法
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s1 = sc.nextLine();
String s2 = sc.nextLine();
// sub
if (compare(s1, s2)) System.out.println(sub(s1, s2));
else System.out.println("-" + sub(s2, s1));
}
// sub s1 - s2
public static String sub (String s1, String s2) {
int len1 = s1.length(), len2 = s2.length();
StringBuilder sb = new StringBuilder();
int t = 0;
for (int i = len1 - 1, j = len2 - 1; i >= 0; -- i, -- j) {
t = s1.charAt(i) - '0' - t;
if (j >= 0) t -= s2.charAt(j) - '0';
sb.append((t + 10) % 10);
t = t < 0 ? 1 : 0;
}
sb.reverse();
// 去除前导0
int idx = 0;
// 这里要idx < len1 - 1
while (idx < len1 - 1 && sb.charAt(idx) == '0') ++ idx;
return sb.substring(idx);
}
// 比较两个数大小
public static boolean compare(String s1, String s2) {
int len1 = s1.length(), len2 = s2.length();
if (len1 != len2) return len1 > len2;
else {
for (int i = 0; i < len1; ++ i) {
if (s1.charAt(i) != s2.charAt(i))
return s1.charAt(i) > s2.charAt(i);
}
}
return true;
}
}
高精度乘法
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String a = sc.nextLine();
int b = sc.nextInt();
int n = a.length();
if (b == 0) {
System.out.println(b);
return;
}
// 高精度乘法
StringBuilder str = new StringBuilder();
int t = 0;
for (int i = n - 1; i >= 0 || t != 0; -- i) {
if (i >= 0) t += (a.charAt(i) - '0') * b;
str.append(t % 10);
t /= 10;
}
System.out.println(str.reverse());
}
}
高精度除法
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String a = sc.nextLine();
int b = sc.nextInt();
int n = a.length();
// 高精度除法
StringBuilder str = new StringBuilder();
int t = 0;
for (int i = 0; i < n; ++ i) {
t = t * 10 + a.charAt(i) - '0';
str.append(t / b);
t %= b;
}
// 去除高位零
int idx = 0;
for (; idx < str.length() - 1 && str.charAt(idx) == '0'; ++ idx);
System.out.printf("%s\n%d", str.substring(idx), t);
}
}
前缀和
前缀和⭐
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
int[] s = new int[n + 1];
for (int i = 1; i <= n; ++ i) {
s[i] = sc.nextInt() + s[i - 1];
}
while (m-- > 0) {
int l = sc.nextInt(), r = sc.nextInt();
System.out.println(s[r] - s[l - 1]);
}
}
}
子矩阵的和
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt(), q = sc.nextInt();
int[][] s = new int[n + 1][m + 1];
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= m; ++ j) {
s[i][j] = s[i][j - 1] + sc.nextInt() + s[i - 1][j] - s[i - 1][j - 1];
}
}
while (q -- > 0) {
int x1 = sc.nextInt(), y1 = sc.nextInt();
int x2 = sc.nextInt(), y2 = sc.nextInt();
System.out.println(s[x2][y2] + s[x1 - 1][y1 - 1] - s[x2][y1 - 1] - s[x1 - 1][y2]);
}
}
}
差分
import java.util.*;
public class Main{
static int[] p;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
p = new int[n + 2];
for (int i = 1; i <= n; ++ i) insert(i, i, sc.nextInt());
while (m -- > 0) {
int l = sc.nextInt(), r = sc.nextInt(), c = sc.nextInt();
insert(l, r, c);
}
for (int i = 1; i <= n; ++ i) {
p[i] += p[i - 1];
System.out.print(p[i] + " ");
}
}
public static void insert (int l, int r, int x) {
p[l] += x;
p[r + 1] -= x;
}
}
差分矩阵
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] strs = br.readLine().split(" ");
int n = Integer.parseInt(strs[0]), m = Integer.parseInt(strs[1]), q = Integer.parseInt(strs[2]);
int[][] s = new int[n + 2][m + 2];
for (int i = 1; i <= n; ++ i) {
strs = br.readLine().split(" ");
for (int j = 1; j <= m; ++ j) {
insert(s, i, j, i, j, Integer.parseInt(strs[j - 1]));
}
}
while (q -- > 0) {
strs = br.readLine().split(" ");
int x1 = Integer.parseInt(strs[0]), y1 = Integer.parseInt(strs[1]);
int x2 = Integer.parseInt(strs[2]), y2 = Integer.parseInt(strs[3]);
int c = Integer.parseInt(strs[4]);
insert(s, x1, y1, x2, y2, c);
}
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];
bw.write(s[i][j] + " ");
}
bw.write("\n");
}
br.close();
bw.close();
}
public static void insert(int[][] s, int x1, int y1, int x2, int y2, int c) {
s[x1][y1] += c;
s[x2 + 1][y1] -= c;
s[x1][y2 + 1] -= c;
s[x2 + 1][y2 + 1] += c;
}
}
双指针
模板
for (int i = 0, j = 0; i < n; i ++) {
while (j < i && check(i, j)) j ++;
// 每道题的具体逻辑
}
最长连续不重复子序列
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; ++ i) a[i] = sc.nextInt();
HashMap<Integer, Integer> map = new HashMap<>();
int i = 1, j = 0;
map.put(a[j], j);
int ans = 1;
while (i < n) {
if (map.containsKey(a[i])) {
ans = Math.max(ans, i - j);
int idx = map.get(a[i]);
for (int k = j; k <= idx; ++ k) {
map.remove(a[k]);
}
j = idx + 1;
}
map.put(a[i], i);
++ i;
}
ans = Math.max(ans, i - j);
System.out.println(ans);
}
}
离散化
区间和
import java.util.*;
public class Main{
static int N = 300010;
static int[] a = new int[N];
static int[] s = new int[N];
static List<Integer> alls = new ArrayList<>();
static List<int[]> adds = new ArrayList<>();
static List<int[]> queries = new ArrayList<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
// 输入插入
for (int i = 0; i < n; ++ i) {
int x = sc.nextInt(), c = sc.nextInt();
adds.add(new int[]{x, c});
alls.add(x);
}
// 输入查询
for (int i = 0; i < m; ++ i) {
int l = sc.nextInt(), r = sc.nextInt();
queries.add(new int[]{l, r});
alls.add(l);
alls.add(r);
}
// 排序
Collections.sort(alls);
// 去重
alls = alls.subList(0, unique(alls) + 1);
// 执行插入
for (int[] p : adds)
a[find(p[0])] += p[1];
// 前缀和
for (int i = 1; i <= alls.size(); ++ i) {
// s[i] = s[i - 1] + a[i];
s[i] = s[i - 1] + a[i - 1];
}
// 查询
for (int[] q : queries) {
// System.out.println(s[find(q[1])] - s[find(q[0]) - 1]);
System.out.println(s[find(q[1]) + 1] - s[find(q[0])]);
}
}
// 查找 找到大于等于x的第一个数
public static int find(int x) {
int l = 0, r = alls.size() - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (alls.get(mid) >= x) r = mid;
else l = mid + 1;
}
// return l + 1;
return l;
}
// 去重
public static int unique (List<Integer> list) {
int n = list.size();
int i, j;
for (i = 0, j = 0; j < n;) {
while (j < n && list.get(i) == list.get(j)) ++ j;
if (j < n) list.set(++ i, list.get(j));
}
return i; // 返回最后一个元素坐标
}
}
区间合并
区间合并
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] s = new int[n][2];
for (int i = 0; i < n; ++ i) {
s[i][0] = sc.nextInt();
s[i][1] = sc.nextInt();
}
Arrays.sort(s, (x, y) -> x[0]- y[0]);
int cnt = 1;
int l = s[0][0], r = s[0][1];
for (int i = 1; i < n; ++ i) {
int x = s[i][0], y = s[i][1];
if (r < x) {
++ cnt;
l = x;
r = y;
} else {
r = Math.max(r, y);
}
}
System.out.println(cnt);
}
}