第一讲 基础算法

快速排序

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