❮
❯
TOC
KINA

KINA-0

Start having fun with KINA right now!
分类 算法笔记

Java算法模板（1）：基础算法

作者

常用算法代码模板（Java）——基础算法：排序、二分、高精度、前缀和与差分、位运算、双指针、离散化、区间合并

Java算法模板系列

1 排序

Arrays.sort(arr [, fromIndex, toIndex])
Arrays.sort(arr, comparator)

Collections.sort(list)
Collections.sort(list, comparator)

1.1 直接插入排序

public class InsertSort {
    // 插入排序
    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j >= 1 && arr[j] > arr[j - 1]; j--) {
                swap(arr, j, j - 1);
            }
        }
    }

    // 交换数组中两个元素
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

1.2 快速排序

  1. 确定枢轴：通常从 arr[l]、arr[l + r >> 1]、arr[r]之中任选一个
  2. 划分子区间：双指针 i、j初始位于待排区间两侧外，先 i后 j相向而行，最终使得左右子区间 arr[l ... j]、arr[j+1 ... r]左小右大
  3. 递归排序左右子区间（该写法左子区间右端点必须为 j）

快速排序

public class QuickSort {
    // 快速排序 arr[l ... r]
    public static void quickSort(int[] arr, int l, int r) {
        if (l >= r) return;

        int x = arr[l + (r - l) / 2];   // 枢轴（选择中间元素）
        int i = l - 1, j = r + 1;       // 双指针初始位于两侧外（追加1偏移量）

        while (i < j) {
            do {
                i++;
            } while (arr[i] < x);
            do {
                j--;
            } while (arr[j] > x);
            if (i < j) {
                swap(arr, i, j);    // 交换元素
            }
        }

        quickSort(arr, l, j);       // 左子区间右端点必须为j
        quickSort(arr, j + 1, r);
    }

    // 交换数组中两个元素的方法
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

1.3 归并排序

  1. 确定分界点：mid = l + r >> 1
  2. 递归排序左右子区间
  3. 归并左右子区间为有序子区间：挑出两者较小值，相等则优先归并 arr[i]，使得排序稳定

归并排序

public class MergeSort {
    // 归并排序 arr[l ... r]
    public void mergeSort(int[] arr, int l, int r) {
        if (l >= r) return;

        int mid = l + r >> 1;
        mergeSort(arr, l, mid);         // 递归排序左半部分
        mergeSort(arr, mid + 1, r);     // 递归排序右半部分

        int[] temp = new int[r - l + 1];    // 辅助数组
        int i = l, j = mid + 1, k = 0;      // 初始化指针

        // 归并左右子区间为有序子区间
        while (i <= mid && j <= r) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }

        // 并入区间剩余元素
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= r) {
            temp[k++] = arr[j++];
        }

        // 将排序后的结果复制回原始数组
        for (i = l, j = 0; i <= r; i++, j++) {
            arr[i] = temp[j];
        }
    }
}

2 二分

整数二分：AcWing 789. 数的范围

  1. 中点将区间划分出左右两子区间
  2. 判断中间点是否满足某侧区间的性质 check(mid)，查找x边界，目标在x区间，检测x区间性质。易知该种写法条件检测始终为"≥"或"≤"，对应下文记号check_ge()（greater_equal）、check_le()（less_equal），对比目标和中点的位置关系即可得出条件检测函数。
  3. 返回所检测的x区间的端点x

当查找右边界时中点应为l + r + 1 >> 1，简记：有("右") 加必有("右") 减

浮点数二分：类似整数二分的查找左边界，常写作f(mid) >= target的形式。解唯一，无需处理边界。要注意浮点精度问题。

public class BinarySearch {
    // 查找左边界，即第一个满足条件的元素下标 (lower_bound)
    public static int binarySearchL(int l, int r) {
        while (l < r) {
            int mid = l + r >> 1;    // 计算中间值
            if (check_ge(mid, target)) {
                r = mid;            // 如果中间的值符合条件，则继续在左边查找
            } else {
                l = mid + 1;        // 否则在右边查找
            }
        }
        return l;    // 返回左边界
    }

    // 查找右边界，即最后一个满足条件的元素下标 (upper_bound的前驱)
    public static int binarySearchR(int l, int r) {
        while (l < r) {
            int mid = l + r + 1 >> 1;    // 计算中间值，向右偏移
            if (check_le(mid, target)) {
                l = mid;                // 如果中间的值符合条件，则继续在右边查找
            } else {
                r = mid - 1;            // 否则在左边查找
            }
        }
        return r;    // 返回右边界
    }

    // 浮点数二分
    public static double binarySearchF(double l, double r) {
        final double eps = 1e-8;        // 精度，视题目而定
        while (r - l > eps) {
            double mid = (l + r) / 2;    // 计算中间值
            if (check_ge(mid, target)) {
                r = mid;        // 目标在左边，更新右边界
            } else {
                l = mid;        // 否则更新左边界
            }
        }
        return l;    // 返回左边界，即为目标值的估计
    }
}

3 高精度运算

Java内置大数类：BigInteger、BigDecimal

4 前缀和、差分

以下前缀和与差分数组必须从下标1开始存储

4.1 一维前缀和

对于数列a[1], a[2], ... , a[n]，规定a[i]的前缀和为前$i$个数的和：s[i] = a[1] + a[2] + ... + a[i] (i >= 1)

求法：s[0] = 0, s[i] = s[i - 1] + a[i] (i >= 1)

应用：求下标区间$[l,\ r]$上的片段和s[r] - s[l - 1]

一维前缀和

public class PrefixSumArray {
    static int n = 100010;
    static int[] a = new int[n + 1];
    static int[] s = new int[n + 1];    // 前缀和数组

    // 初始化前缀和数组
    public static void init() {
        for (int i = 1; i <= n; i++) {
            s[i] = s[i - 1] + a[i];
        }
    }

    // 求下标区间[l, r]上的片段和
    public static int getPartialSum(int l, int r) {
        return s[r] - s[l - 1];
    }
}

4.2 二维前缀和

对于n * m的矩阵a[n][m]，规定a[i][j]的二维前缀和s[i][j]为元素a[i][j]左上角所有元素的和。

求法：s[0][j] = s[i][0] = s[0][0] = 0, s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j] (i, j >= 1)

应用：求下图以(x1, y1)为左上角、(x2, y2)为右下角的子矩阵（含边界）上的片段和，只需将整块左上矩形面积减去红、绿区域（不含待求区域边界）面积再补上多减去的重叠区域面积，即为S = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]

二维前缀和

public class PrefixSumMatrix {
    static int n = 100010;
    static int m = 100010;
    static int[][] a = new int[n + 1][m + 1];
    static int[][] s = new int[n + 1][m + 1];   // 前缀和矩阵

    // 初始化前缀和矩阵
    public static void init() {
        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] + a[i][j];
            }
        }
    }

    // 求以(x1, y1)为左上角、(x2, y2)为右下角的子矩阵（含边界）上的片段和
    public static int getPartialSum(int x1, int y1, int x2, int y2) {
        return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
    }
}

4.3 一维差分

由数组a[1], a[2], ... ,a[n]构造差分数组b[1], b[2], ... , b[n]，使得a[i] = b[1] + b[2] + ... + b[i]，b[i] = a[i] - a[i - 1]

应用：给区间[l, r]上所有数加上C，时间复杂度 $O(1)$。方法如下

  1. 给b[l]加上C，使得a[l], a[l + 1], ... , a[n]均加上了C
  2. 给b[r + 1]减去C，使得a[r + 1], a[r + 2], ... , a[n]均减去了本不应加的C

对于原差分数组的初始化亦可采用上述操作，赋值a[i]即相当于给区间[i, i]加上a[i]

一维差分

public class DifferenceArray {
    static int n = 100010;
    static int[] a = new int[n + 1];
    static int[] b = new int[n + 1];    // 差分数组

    // 给区间[l, r]上所有数加上c
    public static void insert(int l, int r, int c) {
        b[l] += c;
        b[r + 1] -= c;
    }

    // 初始化差分数组
    public static void init() {
        for (int i = 1; i <= n; i++) {
            insert(i, i, a[i]);
        }
    }

    // 将操作过的差分数组变为原数组（前缀和与差分互为逆运算）
    public static void toOriginalArray() {
        for (int i = 1; i <= n; i++) {
            b[i] += b[i - 1];
        }
    }
}

4.4 二维差分

参考一维差分与二维前缀和，差分矩阵中每个数都蕴含于其右下矩阵中的每个数。

操作：给下图以(x1, y1)为左上角、(x2, y2)为右下角的子矩形（含边界）加上C，只需给整个右下角加C，给红、绿区域各减C，最后再给重叠区域加上多减的C即可

对于原差分矩阵初始化操作亦可采用上述操作，参考一维差分

二维差分

public class DifferenceMatrix {
    static int n = 100010;
    static int m = 100010;
    static int[][] a = new int[n + 1][m + 1];
    static int[][] b = new int[n + 1][m + 1];    // 差分矩阵

    // 给以(x1, y1)为左上角、(x2, y2)为右下角的子矩阵（含边界）加上c
    public static void insert(int x1, int y1, int x2, int y2, int c) {
        b[x1][y1] += c;
        b[x2 + 1][y1] -= c;
        b[x1][y2 + 1] -= c;
        b[x2 + 1][y2 + 1] += c;
    }

    // 初始化差分矩阵
    public static void init() {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                insert(i, j, i, j, a[i][j]);
            }
        }
    }

    // 将操作过的差分矩阵变为原矩阵：求差分矩阵的前缀和
    public static void toOriginalMatrix() {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
            }
        }
    }
}

5 位运算

例题

  1. 求 $n$ 的二进制表示中第 $k$ 位数字：n >> k & 1 （先把第 $k$ 位数字移到最后一位，再看个位是几，即和 $1$ 做按位与运算）
  2. lowbit(n)：返回 $n$ 的最后一位 $1$
public class BitwiseOperation {
    // 返回x的最后一位1
    public static int lowbit(int x) {
        return x & -x;  // -x = ~x + 1
    }

    // 输出整数x的二进制表示（31位）
    public static void printInBinary(int x) {
        for (int i = 0; i < 31; i++) {
            System.out.print(x >> i & 1);
        }
    }

    // 统计x的二进制表示中有几位1
    public static int countOnesInBinary(int x) {
        int cnt = 0;
        while (x != 0) {
            x -= lowbit(x);
            cnt++;
        }
        return cnt;
    }
}

6 双指针算法

常见的双指针问题：

  1. 对于一个序列，用两个指针维护一段区间
  2. 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作
/* 朴素算法 O(n^2) */
// for (int i = 0; i < n; i++) {
//   for (int j = i; j < n; j++) {
//       ...
//   }
// }

/* 双指针优化后的算法 O(n) */
/* 例1 */
for (int i = 0, j = 0; i < n; i++) { // i为子序列右端点，j为左端动点
    while (j < i && check(i, j)) {
        ...
        j++;
    }
    ...
}
/* 例2 */
for (int i = 0; i < n;) {    // i为子序列左端点，j为动态右端动点
    int j = i;
    while (j < n && check(i, j)) {
        ...
        j++;
    }
    ...
    i = j + 1;  // 将i直接移至j附近
}

7 离散化

高度分散的整数 → $0, 1, 2, ..., n-1$ 或 $1, 2, ..., n$

public class Discretization {
    static List<Integer> alls = new ArrayList<>();  // 存储所有待离散化的值

    // 离散化（保序）
    public static void init() {
        Collections.sort(alls);     // 将所有值排序
        alls = new ArrayList<>(new HashSet<>(alls));    // 去重
    }

    // 根据离散化的值k获取原来的值x
    public static int get(int k) {
        return alls.get(k);
    }

    // 二分求出x对应的离散化的值
    public static int find(int x) {
        int l = 0, r = alls.size() - 1;
        while (l < r) { // 找到第一个大于等于x的位置（唯一）
            int mid = (l + r) >> 1;
            if (alls.get(mid) >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return r + 1;   // 这里+1是为了映射到1, 2, ..., alls.size()
    }
}

8 区间合并

  1. 先将所有区间按左端点大小排序
  2. 当前维护区间与下一区间之间分三种情况：包含、有交集（含端点）、无交集
    • 包含：无需操作（实为有交集的特殊情况）
    • 有交集：更新当前区间右端点为较大的即可，继续维护
    • 无交集：结束维护当前区间并保存，更新为下一区间
  3. 迭代结束后保存当前维护区间

区间合并

public class SegmentsMerge {
    static List<int[]> segs = new ArrayList<>();    // 每个元素表示一段区间，int[0]表示左端点，int[1]表示右端点

    // 合并区间
    List<int[]> merge() {
        List<int[]> res = new ArrayList<>();

        segs.sort(Comparator.comparingInt(a -> a[0])); // 按左端点大小排序

        int st = Integer.MIN_VALUE, ed = Integer.MIN_VALUE; // 当前维护区间（初始化为负无穷）
        for (int[] seg : segs) {
            if (ed < seg[0]) {    // 若与当前维护区间无交集
                if (st != Integer.MIN_VALUE) {
                    res.add(new int[]{st, ed});    // 当前区间结束维护并保存
                }
                st = seg[0];    // 转移至此区间
                ed = seg[1];
            } else {
                ed = Math.max(ed, seg[1]);    // 有交集则比较右端点
            }
        }

        if (st != Integer.MIN_VALUE) {
            res.add(new int[]{st, ed});    // 保存最后一个区间
        }
        return res;
    }
}

发表评论