算法基础课相关代码模板[Java版]

• 活动链接 —— 算法基础课
• c++ 版本及原题链接

快速排序算法模板

public static void quickSort(int[] nums, int l, int r) {
    if (l == r) return;

    int i = l - 1, j = r + 1, mid = nums[l + r >> 1];

    while (i < j) {
        while (nums[++i] < mid);
        while (nums[--j] > mid);
        if (i < j) {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
    }

    quickSort(nums, l, j);
    quickSort(nums, j + 1, r);
}

归并排序算法模板

private static void mergeSort(int[] nums, int l, int r) {
    if (l >= r) {
        return;
    }

    int mid = l + ((r - l) >> 2);

    mergeSort(nums, l, mid);
    mergeSort(nums, mid + 1, r);

    int[] tmp = new int[r - l + 1];
    int i = l, j = mid + 1;
    int k = 0;

    while (i <= mid && j <= r) {
        if (nums[i] < nums[j]) {
            tmp[k++] = nums[i++];
        } else {
            tmp[k++] = nums[j++];
        }
    }

    while(i <= mid) {
        tmp[k++] = nums[i++];
    }
    while(j <= r) {
        tmp[k++] = nums[j++];
    }

    for (i = l, k = 0; i <= r; i++, k++) {
        nums[i] = tmp[k];
    }
}

整数二分算法模板

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

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

浮点数二分算法模板

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

double bsearch_3(double l, double r)
{
    final double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

高精度加法

import java.math.BigInteger;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        BigInteger a = new BigInteger(reader.readLine());
        BigInteger b = new BigInteger(reader.readLine());

        reader.close();

        System.out.print(a.add(b));
    }
}

高精度减法

import java.math.BigInteger;
import java.io.*;


public class Main {
    public static void main (String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        BigInteger a = new BigInteger(reader.readLine());
        BigInteger b = new BigInteger(reader.readLine());

        System.out.print(a.subtract(b));
    }
}

高精度乘低精度

import java.math.BigInteger;
import java.io.*;


public class Main {
    public static void main (String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        BigInteger a = new BigInteger(reader.readLine());
        BigInteger b = new BigInteger(reader.readLine());

        System.out.print(a.multiply(b));
    }
}

高精度除以低精度

import java.math.BigInteger;
import java.io.*;


public class Main {
    public static void main (String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        BigInteger a = new BigInteger(reader.readLine());
        BigInteger b = new BigInteger(reader.readLine());

        BigInteger[] res = a.divideAndRemainder(b);

        System.out.println(res[0]);
        System.out.print(res[1]);
    }
}

一维前缀和

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

二维前缀和

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]

一维差分

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

二维差分

给以(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

位运算

位运算技巧