算法模板（Java版）

一、数论

1）GCD

GCD（求最大公约数）

public static int gcd(int a, int b) {
    if(b == 0) return a;
    return gcd(b, a%b);
}

QGCD（快速GCD）

public static int qGCD(int a, int b) {
    if(a == 0) return b;
    if(b == 0) return a;
    if((a & 1) == 0 && (b & 1) == 0) {
        return qGCD(a >> 1, b >> 1) << 1;
    } else if((b & 1) == 0) {
        return qGCD(a, b >> 1);
    } else if((a & 1) == 0) {
        return qGCD(a >> 1, b);
    } else {
        return qGCD(Math.abs(a - b), Math.min(a, b));
    }
}

extGCD（拓展GCD，解决ax + by = c 问题）

import java.util.Scanner;

public class 数论_拓展GCD {
    /**
     *  题目描述：
     *  两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，
     *  也没有约定见面的具***置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。
     *  我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。
     *  纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。
    * 
     *  输入只包括一行5个整数x，y，m，n，L，其中x≠y < 2000000000，0 < m、n < 2000000000，0 < L < 2100000000。
     * 
     *  输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行"Impossible" 
     * Sample Input: 
     * 1 2 3 4 5 
     * Sample Output:
     * 4
     * 
     */
    public static long extGCD(long a, long b, long x, long y) {
        if(b == 0) {
            x = 1;
            y = 0;
            return a;
        }else {
            long d = extGCD(b, a % b, y, x);
            long temp = y;
            y = x - (a / b) * y;
            x = temp;
            return d;
        }
    }

    //分析：
    //设时间为t，青蛙A在t时间后的位置为x + m * t，青蛙B在t时间后的位置y + n * t
    //因为维度线可视作为一个圈，则可推出他们相遇时候的公式：(x + (m * t)) % L = (y + (n * t)) % L
    //上式转换为：(m - n) * t + k * L = y - x;（t、k为未知数，t为次数，k为圈数）
    //满足ax + by = c
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long x = in.nextLong();
        long y = in.nextLong();
        long m = in.nextLong();
        long n = in.nextLong();
        long L = in.nextLong();
        long a = m - n;
        long b = L;
        long c = y - x;
        long d = extGCD(a, b, x, y);
        if(c % d != 0) {
            System.out.println("Impossible");
        }else {
            x = x * c / d;
            long t = Math.abs(b / d);
            x = (x % t + t) % t;
            System.out.println(x);
        }
    }
}

2）素数（也称质数，质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数）

素数筛选

static boolean[] is_prime = new boolean[100000];

public static void prime(int maxN) {
    Arrays.fill(is_prime, true);
    for(int i = 2; i * i < maxN; i++) {
        if(is_prime[i]) {
            for(int j = i * i; j < maxN; j += i) {
                is_prime[j] = false;
            }
        }
    }
}

3）欧拉函数（小于n且和n互质（两个数的最大公约数为1）的正整数（包括1）的个数，如12的欧拉函数是φ(12)=4，有1，5，7，11）

单个数的欧拉函数

public static int euler(int n) {
    int res = n;
    for(int i = 2; i * i <= n; i++) {
        if(n % i == 0) {
            res = res - res / i;
            while(n % i == 0) {
                n /= i;
            }
        }
    }
    if(n > 1) {
        res = res - res / n;
    }
    return res;
}

欧拉函数筛选

static final int MAX = 100000;
static int[] a = new int[MAX];

public static void euler_meter(){
    for(int i = 1; i < MAX; i++){
        a[i] = i;
    }
    for(int i = 2; i < MAX; i++){
        if(a[i] == i){
            for(int j = i; j < MAX; j += i){
                a[j] = a[j] - a[j] / i;
            }
        }
    }
}

3）博弈论

简单博弈

/*
小明经常玩 LOL 游戏上瘾，一次他想挑战K大师，不料K大师说：
“我们先来玩个空格填字母的游戏，要是你不能赢我，就再别玩LOL了”。
K大师在纸上画了一行n个格子，要小明和他交替往其中填入字母。

并且：
1. 轮到某人填的时候，只能在某个空格中填入L或O
2. 谁先让字母组成了“LOL”的字样，谁获胜。
3. 如果所有格子都填满了，仍无法组成LOL，则平局。

小明试验了几次都输了，他很惭愧，希望你能用计算机帮他解开这个谜。
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {

    static Map<String, Integer> map = new HashMap<>();//记忆话搜索，记录已经走过的字符串及胜负情况

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        for(int i = 0; i < n; i++) {
            String s = in.readLine();
            System.out.println(game(s));
        }
    }

    private static int game(String s) {
        map.clear();
        return f(s.toCharArray());
    }

    private static int f(char[] c) {
        String s = new String(c);
        if(map.get(s) != null) {
            return map.get(s);
        }
        if(s.contains("LOL")) {
            map.put(s, -1);
            return -1;
        }
        if(!s.contains("*")) {
            map.put(s, 0);
            return 0;
        }
        boolean ping = false;
        for(int i = 0; i < c.length; i++) {
            if(c[i] == '*') {
                try {
                    c[i] = 'L';
                    {
                        int k = f(c);
                        if(k == -1) {
                            map.put(s, 1);
                            return 1;
                        }
                        if(k == 0) {
                            ping = true;
                        }
                    }
                    c[i] = 'O';
                    {
                        int k = f(c);
                        if(k == -1) {
                            map.put(s, 1);
                            return 1;
                        }
                        if(k == 0) {
                            ping = true;
                        }
                    }
                }finally {
                    c[i] = '*';
                }
            }
        }
        if(ping) {
            map.put(s, 0);
            return 0;
        }
        map.put(s, -1);
        return -1;
    }
}

NIM堆问题

/*
有3堆硬币，分别是3,4,5
二人轮流取硬币。
每人每次只能从某一堆上取任意数量。
不能弃权。
取到最后一枚硬币的为赢家。

求先取硬币一方有无必胜的招法。
*/
static void f(int[] a){
    int sum = 0;
    for(int i = 0; i < a.length; i++){
        sum ^= a[i];
    }
    if(sum == 0){
        System.out.println("输了");
            return;
    }
    //打印必胜的方法
    for(int i=0; i<a.length; i++){
        int x = sum ^ a[i];
        if(x<a[i]) System.out.println(a[i] + " --> " + x);
    }
}

4）排列组合

全排列(0 ~ 9)
static int[] a = new int[10];
static boolean[] vis = new boolean[10];

public static void dfs(int step){
    if(step == 10){
        for(int i = 0; i < 10; i++){
            System.out.println(a[i] + " ");
        }
        return;
    }
    for(int i = 0; i < 10; i++){
        if(!vis[i]){
            vis[i] = true;
            a[step] = i;
            dfs(step + 1);
            vis[i] = false;
        }
    }
}

不重复全排列

static int[] a = {1， 1， 2};

public static void dfs(int k){
    if(k == a.length){
        for(int i = 0; i < a.length; i++){
            System.out.println(a[i] + " ");
        }
        return;
    }
    for(int i = k; i < a.length; i++){
        if(needSwap(k, i)){
            swap(i, k);
            dfs(step + 1);
            swap(i, k);
        }
    }
}

public static boolean needSwap(int from, int to) {
    for(int i = from; i < to; i++) {
        if(a[to] == a[i]) {
            return false;
        }
    }
    return true;
}

public static void swap(int x, int y) {
    int temp = a[x];
    a[x] = a[y];
    a[y] = temp;
}

不重复一般组合（例如，从4个中选3个所有组合）

static int[] a = {1， 1， 2, 4};

public static void select_combination(int k, int n){
    if(k == n){
        for(int i = 0; i < n; i++){
            System.out.println(a[i] + " ");
        }
        return;
    }
    for(int i = k; i < a.length; i++){
        if(needSwap(k, i)){
            swap(i, k);
            dfs(step + 1);
            swap(i, k);
        }
    }
}

public static boolean needSwap(int from, int to) {
    for(int i = from; i < to; i++) {
        if(a[to] == a[i]) {
            return false;
        }
    }
    return true;
}

public static void swap(int x, int y) {
    int temp = a[x];
    a[x] = a[y];
    a[y] = temp;
}

全组合（列出数列的全部子集）:利用了状态压缩

public static void full_combination(int[] a) {
    int len = a.length;
    for(int i = 1; i < (1 << len); i++) {
        for(int j = 0; j < len; j++) {
            if((i & (1 << j)) > 0) {
                System.out.print(a[j] + " ");
            }
        }
        System.out.println();
    }
}

5）快速幂

a ^ b

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

矩阵快速幂

static class Matrix{
    int n;
    int a[][] = new int[n][n];
    public Matrix(){}
    public Matrix(int n){
        this.n = n;
    }
}

public static Matrix matrix_pow(A, p, mod){
    Matrix B = unit(A.n);
    while(p > 0){
        if((p & 1) == 1){
            B = matrix_mult(B, A, mod);
        }
        p >>= 1;
        A = matrix_mult(A, A, mod);
    }
    return B;
}

public static Matrix unit(int n){
    Matrix B = new Matrix(n);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(i == j) {
                B.a[i][j] = 1;
            }else {
                B.a[i][j] = 0;
            }
        }
    }
    return B;
}

public static Matrix matrix_mult(Matrix A, Matrix B, int mod) {
    Matrix C = new Matrix(A.n, B.n);
    for(int i = 0; i < A.n; i++) {
        for(int j = 0; j < B.n; j++) {
            C.a[i][j] = 0;
            for(int k = 0; k < A.n; k++) {
                C.a[i][j] = C.a[i][j] + (A.a[i][k] * B.a[k][j] % mod);
            }
        }
    }
    return C;
}

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int p = in.nextInt();
    int mod = in.nextInt();
    Matrix A = new Matrix(n);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            A.a[i][j] = in.nextInt();
        }
    }
    Matrix res = matrix_pow(A, p, mod);
    for(int i = 0; i < res.n; i++) {
        for(int j = 0; j < res.n; j++) {
            System.out.print(res.a[i][j] + " ");
        }
        System.out.println();
    }
}

6）循环节长度（a/b）

public static int f(int n, int m) {
    n = n % m;
    Vector<Integer> v = new Vector<>();
    while(true) {
        v.add(n);
        n *= 10;
        n = n % m;
        if (n == 0)
            return 0;
        if (v.indexOf(n) >= 0)
            return v.size() - v.indexOf(n);
    }
}

二、字符串（学的不多）

编辑距离

/*
编辑距离，⼜又称Levenshtein距离（也叫做Edit Distance），是指两个字串串之间，由一个转成 另一个所需的少编辑操作次数。许可的编辑操作包括将⼀一个字符替换成另一个字符，插⼊一个字 符，删除⼀个字符
*/

public static void main(String[] args){
    Scanner in = new Scanner(System.in);
    String s1 = in.nextLine();
    String s2 = in.nextLine();
    char[] c1 = s1.toCharArray();
    char[] c2 = s2.toCharArray();
    int len1 = c1.length;
    int len2 = c2.length;
    int[][] dp = new int[len1 + 1][len2 + 1];
    for(int i = 1; i <= len1; i++){
        dp[i][0] = i;
    }
    for(int i = 1; i <= len2; i++){
        dp[0][i] = i;
    }
    for(int i = 1; i <= len1; i++){
        for(int j = 1; j <= len2; j++){
            if(c[i - 1] == c[j - 1]){
                dp[i][j] = dp[i - 1][j - 1];
            }else{
                dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
            }
        }
    }
    System.out.println(dp[len1][len2]);
}

最长公共子序列

/*
比如字符串1：BDCABA；字符串2：ABCBDAB 最长公共子序列是：BCBA
*/
public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    String s = in.nextLine();
    char[] c1 = s.toCharArray();
    s = in.nextLine();
    char[] c2 = s.toCharArray();
    int len1 = c1.length;
    int len2 = c2.length;
    int dp[][] = new int[len1 + 1][len2 + 1];
    for(int i = 1; i <= len1; i++) {
        for(int j = 1; j <= len2; j++) {
            if(c1[i - 1] == c2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    System.out.println(dp[len1][len2]);
}

最长上升子序列

/*
比如：2 5 3 4 1 7 6  其中最长上升子序列是 2 3 4 7 
*/
public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int[] a = new int[n];
    for(int i = 0; i < n; i++) {
        a[i] = in.nextInt();
    }
    int dp[] = new int[n];
    int ans = 1;
    for(int i = 0; i < n; i++) {
        dp[i] = 1;
        for(int j = i; j >= 0; j--) {
            if(dp[j] < dp[i]) {
                if(a[j] < a[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        ans = Math.max(dp[i], ans);
    }
    System.out.println(ans);
}

Karp-Rabin算法 （字符串匹配）

/**
比如：字符串1：abcaabcaabcbcabc 字符串2：abc 答案：4
*/
static int send = 31;

public static void karp_rabin(String s1, String s2){
    long hash_s2 = hash(s2);
    int len_s1 = s1.length();
    int len_s2 = s2.length();
    long[] hash_s1 = new long[len_s1 - len_s2 + 1];
    hash_s1[0] = hash(s1.subString(0, len_s2));
    int ans = 0;
    for(int i = len_s2; i < len_s1; i++){
        char newChar = s1.charAt(i);
        char oldChar = s1.charAt(i - len_s2);
        long v = (long) (hash_s1[i - len_s2] * send - oldChar * Math.pow(send, len_s2) + newChar);
        hash_s1[i - len_s2 + 1] = v;
    }
    for(int i = 0; i < hash_s1.length; i++) {
        if (hash_s1[i] == hash_s2) { // 当j == len_s2的时候则说明第二个循环从头扫到尾，即满足题意。
            ans++;
            // 为了验证是否正确，进行了下标打印（下标0代表字符串的第一位）
            System.out.println("match:" + i);
            System.out.println(ans);
        }
    }
}

public static long hash(String s){
    int len = s.length();
    long hash = 0;
    for(int i = 0; i < len; i++){
        hash = send * hash + s.charAt(i);
    }
    return hash;
}

KMP算法（字符串匹配）

public int kmp(String text, String pattern) {
    int m = pattern.length();
    if (m == 0)
        return 0;
    int n = text.length();
    int[] next = new int[m + 1];
    for (int i = 2, j = 0; i <= m; i++) {
        while (j > 0 && pattern.charAt(i - 1) != pattern.charAt(j))
            j = next[j];
        if (pattern.charAt(i - 1) == pattern.charAt(j))
            j++;
        next[i] = j;
    }
    for (int i = 1, j = 0; i <= n; i++) {
        while (j > 0 && text.charAt(i - 1) != pattern.charAt(j))
            j = next[j];
        if (text.charAt(i - 1) == pattern.charAt(j))
            j++;
        if (j == m)
            return i - m;
    }
    return -1;
}

三、背包问题

01背包

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int N = in.nextInt();
    int V = in.nextInt();
    int[] c = new int[N + 1];
    int[] w = new int[N + 1];
    for(int i = 1; i <= N; i++) {
        w[i] = in.nextInt();
        c[i] = in.nextInt();
    }
    int[] dp = new int[V + 1];
    for(int i = 1; i <= N; i++) {
        for(int j = V; j >= c[i]; j--) {
            dp[j] = Math.max(dp[j - c[i]] + w[i], dp[j]);
        }
    }
    System.out.println(dp[V]);
}

多重背包

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int N = in.nextInt();
    int V = in.nextInt();
    int[] c = new int[N + 1];
    int[] w = new int[N + 1];
    int[] n = new int[N + 1];
    for(int i = 1; i <= N; i++) {
        w[i] = in.nextInt();
        c[i] = in.nextInt();
        n[i] = in.nextInt();
    }
    int[] dp = new int[V + 1];
    for(int i = 1; i <= N; i++) {
        for(int j = V; j >= 0; j--) {
            for(int k = 0; k <= n[i]; k++){
                if(j >= k * c[i]){
                    dp[j] = Math.max(dp[j - c[i] * k] + k * w[i], dp[j]);
                }
            }
        }
    }
    System.out.println(dp[V]);
}

多重背包（二进制优化）

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int N = in.nextInt();
    int V = in.nextInt();
    int[] c = new int[N + 1];
    int[] w = new int[N + 1];
    int[] n = new int[N + 1];
    for(int i = 1; i <= N; i++) {
        w[i] = in.nextInt();
        c[i] = in.nextInt();
        n[i] = in.nextInt();
    }
    int[] dp = new int[V + 1];
    for(int i = 1; i <= N; i++) {
        int t = n[i];
        int k = 1;
        while(k < t){
            for(int j = V; j >= k * c[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - k * c[i]] + k * w[i]);
            }
            k *= 2;
            t -= k;
        }
        for(int j = V; j >= t * c[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - t * c[i]] + t * w[i]);
        }
    }
    System.out.println(dp[V]);
}

完全背包

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int N = in.nextInt();
    int V = in.nextInt();
    int[] c = new int[N + 1];
    int[] w = new int[N + 1];
    for(int i = 1; i <= N; i++) {
        w[i] = in.nextInt();
        c[i] = in.nextInt();
    }
    int[] dp = new int[V + 1];
    for(int i = 1; i <= N; i++) {
        for(int j = c[i]; j <= V; j++) {
            dp[j] = Math.max(dp[j - c[i]] + w[i], dp[j]);
        }
    }
    System.out.println(dp[V]);
}

混合背包

/*
题目链接：https://www.acwing.com/problem/content/7/
*/
import java.util.Scanner;

public class 背包问题_混合背包问题 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int V = in.nextInt();
        int[] v = new int[N + 1];
        int[] w = new int[N + 1];
        int[] s = new int[N + 1];
        for(int i = 1; i <= N; i++) {
            v[i] = in.nextInt();
            w[i] = in.nextInt();
            s[i] = in.nextInt();
        }
        int[] dp = new int[V + 1];
        for(int i = 1; i <= N; i++) {
            if(s[i] == -1) {
                for(int j = V; j >= v[i]; j--) {
                    dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
                }
            }else if(s[i] == 0) {
                for(int j = v[i]; j <= V; j++) {
                    dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
                }
            }else {
                int k = 1;
                int t = s[i];
                while(k < t) {
                    for(int j = V; j >= k * v[i]; j--) {
                        dp[j] = Math.max(dp[j], dp[j - k * v[i]] + k * w[i]);
                    }
                    t -= k;
                    k <<= 1;
                }
                for(int j = V; j >= t * v[i]; j--) {
                    dp[j] = Math.max(dp[j], dp[j - t * v[i]] + t * w[i]);
                }
            }
        }
        System.out.println(dp[V]);
    }
}

二维费用背包问题

/*
题目链接：https://www.acwing.com/problem/content/8/
*/
import java.util.Scanner;

public class 背包问题_二维费用背包问题 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int V = in.nextInt();
        int M = in.nextInt();
        int[] v = new int[N + 1];
        int[] m = new int[N + 1];
        int[] w = new int[N + 1];
        for(int i = 1; i <= N; i++) {
            v[i] = in.nextInt();
            m[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        int[][] dp = new int[V + 1][M + 1];
        for(int i = 1; i <= N; i++) {
            for(int j = V; j >= v[i]; j--) {
                for(int k = M; k >= m[i]; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - v[i]][k - m[i]] + w[i]);
                }
            }
        }
        System.out.println(dp[V][M]);
    }
}

组合背包问题

/*
题目链接：https://www.acwing.com/problem/content/9/
*/
import java.util.Scanner;

public class 背包问题_分组背包问题 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int V = in.nextInt();
        int[] a = new int[N + 1];
        int[][] v = new int[N + 1][];
        int[][] w = new int[N + 1][];
        for(int i = 1; i <= N; i++) {
            a[i] = in.nextInt();
            v[i] = new int[105];
            w[i] = new int[105];
            for(int j = 1; j <= a[i]; j++) {
                v[i][j] = in.nextInt();
                w[i][j] = in.nextInt();
            }
        }
        int[] dp = new int[V + 1];
        for(int i = 1; i <= N; i++) {
            for(int j = V; j >= 0; j--) {
                for(int k = 1; k <= a[i]; k++) {
                    if(j >= v[i][k]){
                        dp[j] = Math.max(dp[j], dp[j - v[i][k]] + w[i][k]);
                    }
                }
            }
        }
        System.out.println(dp[V]);
    }
}

三、图论
###Dijkstra（邻接矩阵形式）——求单源最短路（无负权边）

import java.util.Arrays;
import java.util.Scanner;

public class 图_最短路径_dijkstra_邻接矩阵 {

    private static int n, m;
    private static int[][] map;
    private static boolean[] vis;
    private static int[] dis;
    private static final int INF = 0x3f3f3f;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        init();//初始化
        for(int i = 0; i < m; i++) {
            int a = in.nextInt();//起点
            int b = in.nextInt();//终点
            int c = in.nextInt();//权值
            insert(a, b, c);//无向图
//          insert01(a, b, c);//有向图
        }
        dijkstra(1);
        System.out.println(dis[n]);
    }

    private static void init() {
        map = new int[n + 1][n + 1];
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(i == j) map[i][j] = 0;
                else map[i][j] = INF;
            }
        }
        vis = new boolean[n + 1];
        dis = new int[n + 1];
        Arrays.fill(dis, INF);
    }

    private static void dijkstra(int u) {
        for(int i = 1; i <= n; i++){
            dis[i] = map[u][i];
        }
        vis[i] = true;
        for(int i = 1; i <= n - 1; j++){
            int mind = INF;
            int minj = -1;
            for(int j = 1; j <= n; j++){
                if(!vis[j] && dis[j] < mind){
                    mind = dis[j];
                    minj = j;
                }
            }
            if(minj == -1) return;
            vis[minj] = true;
            for(int j = 1; j <= n; j++){
                if(map[minj][j] < INF){
                    if(dis[j] > dis[minj] + map[minj][j]){
                        dis[j] = dis[minj] + map[minj][j];
                    }
                }
            }
        }
    }

    //无向图添加边
    private static void insert(int a, int b, int c) {
        map[a][b] = c;
        map[b][a] = c;
    }

    //有向图添加边
    private static void insert(int a, int b, int c) {
        map[a][b] = c;
    }

}

Dijkstra（邻接矩阵链表）——求单源最短路（无负权边）
import java.util.Arrays;
import java.util.Scanner;

public class 图_最短路径_dijkstra_邻接链表 {

    private static int n, m;
    private static boolean[] vis;
    private static int[] dis;
    private static final int INF = 0x3f3f3f;
    private static Edge[] e;
    private static int[] head;
    private static int size;

    static class Edge{
        int v;//终点
        int w;//权重
        int next;//下一条边的id
        public Edge(){}
        public Edge(int v, int w, int next){
            this.v = v;
            this.w = w;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        init();//初始化
        for(int i = 0; i < m; i++) {
            int a = in.nextInt();//起点
            int b = in.nextInt();//终点
            int c = in.nextInt();//权值
            insert(a, b, c);//无向图
//          insert01(a, b, c);//有向图
        }
        dijkstra(1);
        System.out.println(dis[n]);
    }

    private static void init() {
        e = new Edge[2 * m + 1];//无向图
//      e = new Edge[m + 1];//有向图
        vis = new boolean[n + 1];
        dis = new int[n + 1];
        Arrays.fill(dis, INF);
        head = new int[n + 1];
        Arrays.fill(head, -1);
    }

    private static void dijkstra(int u) {
        dis[u] = 0;
        for(int i = 1; i <= n; i++){
            int mind = INF;
            int minj = -1;
            for(int j = 1; j <= n; j++){
                if(!vis[j] && dis[j] < mind){
                    mind = dis[j];
                    minj = j;
                }
            }
            if(minj == -1){
                return;
            }
            vis[minj] = true;
            for(int j = head[minj]; j != -1; j = e[j].next){
                int v = e[j].v;
                int w = e[j].w;
                if(!vis[v] && dis[v] > dis[minj] + w){
                    dis[v] = dis[minj] + w;
                }
            }
        }
    }

    //无向图添加边
    private static void insert(int u, int v, int w) {
        e[size] = new Edge(v, w, head[u]);
        head[u] = size++;
        e[size] = new Edge(u, w, head[v]);
        head[v] = size++;
    }

    //有向图添加边
    private static void insert(int u, int v, int w) {
        e[size] = new Edge(b, c, head[a]);
        head[u] = size++;
    }

}

SPFA（邻接链表）——单源最短路（有负权边）

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 图_最短路径_spfa_邻接链表 {

    private static int n, m, size;
    private static Edge[] e;
    private static int[] head;
    private static int[] dis;
    private static boolean[] vis;
    private static final int INF = 0x3f3f3f;
    private static int[] in;

    public static class Edge{
        int v;
        int w;
        int next;
        public Edge() {}
        public Edge(int v, int w, int next) {
            this.v = v;
            this.w = w;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        init();
        for(int i = 0; i < m; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();
            insert02(a, b, c);
        }
        if(spfa(1)) {
            System.out.println("有负环");
        }else {
            System.out.println(dis[n]);
        }
    }

    //加入负环判断
    private static boolean spfa(int u) {
        vis[u] = true;
        dis[u] = 0;
        in[u]++;
        Queue<Integer> q = new LinkedList<>();
        q.add(u);
        while(!q.isEmpty()){
            int now = q.poll();
            vis[now] = false;
            for(int i = head[now]; i != -1; i = e[i].next){
                int v = e[i].v;
                int w = e[i].w;
                if(dis[v] > dis[u] + w){
                    dis[v] = dis[u] + w;
                    if(!vis[v]){
                        q.add(v);
                        vis[v] = true;
                        in[v]++;
                        if(in[v] > n) return true;
                    }
                }
            }
        }
        return false;
    }

    private static void init() {
        e = new Edge[2 * m + 1];
        head = new int[n + 1];
        Arrays.fill(head, -1);
        vis = new boolean[n + 1];
        dis = new int[n + 1];
        Arrays.fill(dis, INF);
        in = new int[n + 1];
    }

    private static void insert01(int u, int v, int w) {
        e[size] = new Edge(v, w, head[u]);
        head[u] = size++;
    }

    private static void insert02(int u, int v, int w) {
        insert01(u, v, w);
        insert01(v, u, w);
    }
}

floyd——多源最短路

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int m = in.nextInt();
    int[][] map = new int[n + 1][n + 1];
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(i == j) map[i][j] = 0;
            else map[i][j] = 0x3f;
        }
    }
    for(int i = 0; i < m; i++) {
        int a = in.nextInt();
        int b = in.nextInt();
        int c = in.nextInt();
        map[a][b] = map[b][a] = c;
    }
    //floyd核心
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
            }
        }
    }
    System.out.println(map[1][n]);
}

图的拓扑排序

public class 图_拓扑排序 {

    private static int n, m;
    private static Edge[] e;
    private static int[] indegree;
    private static int[] head;
    private static int size;

    public static class Edge{
        int v;
        int next;
        public Edge() {}
        public Edge(int v, int next) {
            this.v = v;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        init();
        for(int i = 0; i < m; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            insert(a, b);
            indegree[b]++;
        }
        topo();
    }

    private static void topo() {
        Queue<Integer> q = new LinkedList<>();
        for(int i = 1; i <= n; i++) {
            if(indegree[i] == 0) {
                q.add(i);
            }
        }
        while(!q.isEmpty()) {
            int now = q.peek();
            System.out.println(now);
            q.poll();
            for(int i = head[now]; i != -1; i = e[i].next) {
                int v = e[i].v;
                indegree[v]--;
                if(indegree[v] == 0) {
                    q.add(v);
                }
            }
        }
    }

    private static void insert(int u, int v) {
        e[size] = new Edge(v, head[u]);
        head[u] = size++;
    }

    private static void init() {
        e = new Edge[m + 1];
        indegree = new int[n + 1];
        Arrays.fill(indegree, 0);
        head = new int[2 * m + 1];
        Arrays.fill(head, -1);
    }
}

最小生成树——Kruskal

public class 最小生成树 {

    static int n, m;
    static Edge[] e;
    static int[] pre;

    public static class Edge{
        int u;
        int v;
        int w;
        public Edge() {}
        public Edge(int u, int v, int w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }
        @Override
        public String toString() {
            return "Edge [u=" + u + ", v=" + v + ", w=" + w + "]";
        }
    }

    public static int krusual(){
        init();
        Arrays.sort(e, new Comparator<Edge>() {
            public int compare(Edge o1, Edge o2) {
                return o1.w - o2.w;
            }
        });
        int count = 0;//记录已生成的边数
        int sum = 0;//记录答案
        for(int i = 0; i < m; i++) {
            if(merge(e[i].u, e[i].v)) {
                count++;
                sum += e[i].w;
            }
            if(count == n - 1) {//满足最小生成树条件
                break;
            }
        }
        if(count < n - 1) {
            return -1;
        }else{
            return sum;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        e = new Edge[m];
        for(int i = 0; i < m; i++) {
            e[i] = new Edge(in.nextInt(), in.nextInt(), in.nextInt());
        }
        int res = krusual();
        if(res == -1){
            System.out.println("不连通);
        }else{
            System.out.println(res);
        }
    }

    private static boolean merge(int u, int v) {
        int uu = find(u);
        int vv = find(v);
        if(uu != vv){
            pre[vv] == uu;
            return true;
        }
        return false;
    }

    private static int find(int u) {
        int r = u;
        while(r != pre[r]){
            r = pre[r];
        }
        return r;
    }

    //并查集初始
    private static void init() {
        pre = new int[n + 1];
        for(int i = 1; i <= n; i++) {
            pre[i] = i;
        }
    }
}

最小生成树——Prim

import java.util.Arrays;
import java.util.Scanner;

public class 最小生成树_Prim {

    static int n, m;
    static final int INF = 0x3f3f3f;
    static int[] head;
    static int size;
    static Edge[] e;
    static boolean[] vis;
    static int[] dis;

    static class Edge{
        int v;
        int w;
        int next;
        public Edge() {}
        public Edge(int v, int w, int next) {
            this.v = v;
            this.w = w;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        init();
        int st = 0;
        for(int i = 0; i < m; i++) {
            int u = in.nextInt();
            int v = in.nextInt();
            int w = in.nextInt();
            insert(u, v, w);
            insert(v, u, w);
            st = u;
        }
        int res = prim(st);
        System.out.println(res);
    }

    private static int prim(int st) {
        int sum = 0;
        int count = 0;
        dis[st] = 0;
        for(int i = head[st]; i != -1; i = e[i].next) {
            int v = e[i].v;
            int w = e[i].w;
            if(dis[v] > w) {
                dis[v] = w;
            }
        }
        vis[st] = true;
        count++;
        while(count < n) {
            int mind = INF;
            int minj = -1;
            for(int i = 1; i <= n; i++) {
                if(!vis[i] && dis[i] < mind) {
                    mind = dis[i];
                    minj = i;
                }
            }
            vis[minj] = true;
            count++;
            sum += mind;
            for(int i = head[minj]; i != -1; i = e[i].next) {
                int v = e[i].v;
                int w = e[i].w;
                if(!vis[v] && dis[v] > w) {
                    dis[v] = w;
                }
            }
        }
        return sum;
    }

    private static void init() {
        head = new int[n + 1];
        Arrays.fill(head, -1);
        e = new Edge[m * 2 + 1];
        vis = new boolean[n + 1];
        dis = new int[n + 1];
        Arrays.fill(dis, INF);
    }

    private static void insert(int u, int v, int w) {
        e[size] = new Edge(v, w, head[u]);
        head[u] = size++;
    }
}

线段树（多用于解决区间问题）

import java.util.Arrays;
import java.util.Scanner;

public class 线段树_构建 {

    private static final int MAX = 105;
    private static int[] a = new int[MAX];
    private static int[] minv = new int[MAX * 4];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for(int i = 1; i <= n; i++) {
            a[i] = in.nextInt();
        }
        build_tree(1, 1, n);
        update_tree(1, 1, n, 5, 7);//更新线段树中a数组下标为5的值。
        query_tree(1, 1, n, 2, 5);//查询2~5区间的最小值
    }


    //区间查询
    private static int query_tree(int id, int l, int r, int x, int y) {
        if(x <= l && r <= y) {
            return minv[id];
        }
        int mid = (l + r) >> 1;
        int res = Integer.MAX_VALUE;
        if(x <= mid) {
            res = Math.min(res, query_tree(id << 1, l, mid, x, y));
        }
        if(y > mid) {
            res = Math.min(res, query_tree(id << 1 | 1, mid + 1, r, x, y));
        }
        return res;
    }

    //更新
    private static void update_tree(int id, int l, int r, int x, int v) {
        if(l == r) {
            minv[id] = v;
            return;
        }
        int mid = (l + r) >> 1;
        if(x <= mid) {
            update_tree(id << 1, l, mid, x, v);
        }else {
            update_tree(id << 1 | 1, mid + 1, r, x, v);
        }
        minv[id] = Math.min(minv[id << 1], minv[id << 1 | 1]);
    }

    //构建线段树
    private static void build_tree(int id, int l, int r) {
        if(l == r) {
            minv[id] = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build_tree(id << 1, l, mid);
        build_tree(id << 1 | 1, mid + 1, r);
        minv[id] = Math.min(minv[id << 1], minv[id << 1 | 1]);
    }
}

四、二分

二分

private static int binary_search(Integer[] a, int k) {
    int l = 0;
    int r = a.length - 1;
    while(l <= r) {
        int mid = (r + l) >> 1;
        if(a[mid] == k) return mid;
        if(a[mid] < k) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}

二分搜索逼近左边界

区间[left, right]被分为左区间[left, mid]和右区间[mid + 1, right]。

public int binarySearchLeft(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (check(mid))
            right = mid;
        else
            left = mid + 1;
    }
    return nums[left];
}

最大值最小问题

public class 二分_最大值最小 {

    static int[] a = {2, 4, 6, 8, 10, 12, 14};

    public static void main(String[] args) {
        System.out.println(bsearch_maxMin(11));
    }

    private static int bsearch_maxMin(int x) {
        int l = 0;
        int r = a.length - 1;
        while(l < r) {
            int mid = (l + r) >> 1;
            if(x <= a[mid]) {
                r = mid;
            }else {
                l = mid + 1;
            }
        }
        return l;//返回5
    }
}

最小值最大问题

public class 二分_最小值最大 {

    static int[] a = {2, 4, 6, 8, 10, 12, 14};

    public static void main(String[] args) {
        System.out.println(bsearch_maxMin(3));
    }

    private static int bsearch_maxMin(int x) {
        int l = 0;
        int r = a.length - 1;
        while(l < r) {
            int mid = (l + r + 1) >> 1;
            if(x <= a[mid]) {
                r = mid - 1;
            }else {
                l = mid;
            }
        }
        return l;//返回4
    }
}

排序

快速排序

public void quickSort(int[] nums, int left, int right) {
    if (left >= right)
        return;
    int i = left - 1, j = right + 1, x = nums[left];
    while (i < j) {
        do i++; while (nums[i] < x);
        do j--; while (nums[j] > x);
        if (i < j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
    quickSort(nums, left, j);
    quickSort(nums, j + 1, right);
}

归并排序mergeSort

mergeSort时间复杂度是稳定O(nlogn)，空间复杂度O(n)，稳定的。quickSort时间复杂度平均O(nlogn)，最坏O(n^2)，最好O(nlogn)，空间复杂度O(nlogn)，不稳定的。

public void mergeSort(int[] nums, int left, int right) {
    if (left >= right)
        return;

    int mid = left + (right - left) / 2;
    mergeSort(nums, left, mid);
    mergeSort(nums, mid + 1, right);

    int k = 0, i = left, j = mid + 1;
    int[] temp = new int[right - left + 1];
    while (i <= mid && j <= right)
        if (nums[i] < nums[j])
            temp[k++] = nums[i++];
        else
            temp[k++] = nums[j++];
    while (i <= mid)
        temp[k++] = nums[i++];
    while (j <= right)
        temp[k++] = nums[j++];
    for (i = left, j = 0; i <= right; i++, j++)
        nums[i] = temp[j];
}

Tire

public static final int SIZE = 26;

public static class TrieNode {
    TrieNode[] children = new TrieNode[SIZE];
    int times;

    TrieNode() {
        times = 0;
        for (int i = 0; i < SIZE; i++)
            children[i] = null;
    }
}

public static TrieNode root = new TrieNode();

public static void insert(String word) {
    TrieNode node = root;
    for (int i = 0; i < word.length(); i++) {
        int index = word.charAt(i) - 'a';
        if (node.children[index] == null)
            node.children[index] = new TrieNode();
        node = node.children[index];
    }
    node.times++;
}

public static int query(String word) {
    TrieNode node = root;
    for (int i = 0; i < word.length(); i++) {
        int index = word.charAt(i) - 'a';
        if (node.children[index] == null)
            return 0;
        node = node.children[index];
    }
    return node.times;
}

并查集

public static int[] p;

public static int find(int x) {
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}

p[find(a)] = find(b);

排序

快速排序 （以一个数区分）

 public static void main(String[] args) {
        int[] nums = {23, 15,2, 1, 3, 4,4};
        quickSort(nums, 0, nums.length - 1);
        for (int x : nums) {
            System.out.println(x);
        }
    }

    private static void quickSort(int[] q, int l , int r) {
        // 递归终止条件
        if (l >= r) return;

        // 取分界点
        int x = q[l];
        int i = l - 1;
        int j = r + 1;
        while (i < j) {
            while (q[++i] < x);
            while (q[--j] > x);
            if (i < j) {
                int tmp = q[i];
                q[i] = q[j];
                q[j] = tmp;
            }
        }
        // 递归交换左右两个区间,记得一定得选j,如果选i的话，x不能选左边第一个
        quickSort(q, l, j);
        quickSort(q, j+1, r);
    }

归并模板

public static 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, i = l, 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];
        }

双指针模板

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;

    // 具体问题的逻辑
}
常见问题分类：
    (1) 对于一个序列，用两个指针维护一段区间
    (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

参考

https://www.acwing.com/blog/content/593/
https://www.jianshu.com/p/20f4b6cb27a7