algorithm-misc

质数

计算不同质因子的数目

比方说，300的不同质因子的数目为3，因为 300 = 2 * 2 * 3 * 5 * 5 。

// 计算10^5内的数的不同质因子的数目
private static final int MX = (int) 1e5 + 1;
private static final int[] omega = new int[MX];
static {
    for (int i = 2; i < MX; i++)
        if (omega[i] == 0) // i 是质数
            for (int j = i; j < MX; j += i)
                omega[j]++; // i 是 j 的一个质因子
}
// 作者：灵茶山艾府
// 链接：https://leetcode.cn/problems/apply-operations-to-maximize-score/solutions/2385936/gong-xian-fa-dan-diao-zhan-pythonjavacgo-23c4/

最小质因子 LPF

static {
    for (int i = 2; i < MX; i++) {
        if (lpf[i] == 0) {
            for (int j = i; j < MX; j += i) {
                if (lpf[j] == 0) {
                    lpf[j] = i;
                }
            }
        }
    }
}

特殊数

最大公约数(Greatest Common Divisor)

递归写法

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

迭代写法

private long gcd(long a, long b) {
    while (a != 0) {
        long tmp = a;
        a = b % a;
        b = tmp;
    }
    return b;
}

BigInteger写法

1
2
3

BigInteger gcd = BigInteger.ZERO, lcm = BigInteger.ONE;
gcd = gcd.gcd(BigInteger.valueOf(nums[j]));
lcm = lcm.multiply(BigInteger.valueOf(nums[j])).divide(lcm.gcd(BigInteger.valueOf(nums[j])));

最小公倍数(Least Common Multiple)

可以用最大公约数来进一步获得

1
2
3

private int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

计算数组的gcd和lcm前后缀

3334. 数组的最大因子得分

long[] preGcd = new long[n + 1];
long[] preLcm = new long[n + 1];
long[] sufGcd = new long[n + 1];
long[] sufLcm = new long[n + 1];
preLcm[0] = 1;  // preGcd[0] = 0 即可
for (int i = 0; i < n; i++) {
    preGcd[i + 1] = gcd(preGcd[i], nums[i]);
    preLcm[i + 1] = lcm(preLcm[i], nums[i]);
}
sufLcm[n] = 1;
for (int i = n - 1; i >= 0; i--) {
    sufGcd[i] = gcd(sufGcd[i + 1], nums[i]);
    sufLcm[i] = lcm(sufLcm[i + 1], nums[i]);
}

中位数

用一个最大堆和一个最小堆在log时间内获得中位数

数据流的中位数

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

例如 arr = [2,3,4] 的中位数是 3 。
例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

MedianFinder() 初始化 MedianFinder 对象。
void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10^-5 以内的答案将被接受。

示例 1：

输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]

解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);  // arr = [1]
medianFinder.addNum(2);  // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);  // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

提示:

-10^5 <= num <= 10^5
在调用 findMedian 之前，数据结构中至少有一个元素
最多 5 * 10^4 次调用 addNum 和 findMedian

Java

class MedianFinder {
    int cnt = 0;
    PriorityQueue<Integer> left = new PriorityQueue<>((a,b) -> b-a);  // 最大堆
    PriorityQueue<Integer> right = new PriorityQueue<>();  // 最小堆
    
    public MedianFinder() {

    }
    
    public void addNum(int num) {
        if ((cnt & 1) == 0) {
            left.offer(num);
            right.offer(left.poll());
        }
        else {
            right.offer(num);
            left.offer(right.poll());
        }
        cnt++;
    }
    
    public double findMedian() {
        if ((cnt & 1) == 0) return ((double)left.peek() + right.peek()) / 2;
        else return right.peek();
    }
}

O(n)计算两两距离之和

给定一个数组nums包含各个点的坐标，请你计算两两距离之和，要求O(n)

依次计算每个点与左边所有点的距离之和

(a[i]−a[0])+(a[i]−a[1])+⋯+(a[i]−a[i−1]) = i⋅a[i]−(a[0]+a[1]+⋯+a[i−1])

long res = 0, sum = 0;
for (int i = 0; i < n; i++) {  // 计算每个点与左边所有点的距离之和
    sum = (sum + nums[i]) % MOD;
    res = (res + (long)(i+1)*nums[i] - sum) % MOD;
}

正负数除2取整方向不同

正数除2是向下取整，负数除2是向上取整

比如3/2 = 1，3是向下取整；而-3/2 = -1，-3是向上取整

算法技巧

用一维数组表示东南西北四个方向

/**
 *   y →
 * x 1 1 1
 * ↓ 1 1 1
 *   1 1 1
 */
int dir[] = new int[]{0, 1, 0, -1, 0};
for (int i = 0; i < dir.length - 1; i++) {
    int nx = x + dir[i], ny = y + dir[i + 1];
}

排列组合

全排列（有顺序，可重复）

dfs(n, numSelect, 0);
public void dfs(int n, int numSelect, int vis) {
    if (numSelect == 0) return;
    for (int i = 0; i < n; i++) {
        if ((1 << i && vis) != 0) continue;
        dfs(n, numSelect-1, vis|1<<i);
    }
}

组合（无顺序，不重复）

增加一个起始位置的参数

dfs(n, numSelect, 0, 0);
public void dfs(int n, int numSelect, int vis, int start) {
    if (numSelect == 0) return;
    for (int i = start; i < n; i++) {
        if ((1 << i && vis) != 0) continue;
        dfs(n, numSelect-1, vis|1<<i, i+1);
    }
}

获得一个list的全排列

private List<List<int[]>> permutations(List<int[]> arr) {
    List<List<int[]>> result = new ArrayList<>();
    permute(arr, 0, result);
    return result;
}

private void permute(List<int[]> arr, int start, List<List<int[]>> result) {
    if (start == arr.size()) {
        result.add(new ArrayList<>(arr));
    }
    for (int i = start; i < arr.size(); i++) {
        swap(arr, start, i);
        permute(arr, start + 1, result);
        swap(arr, start, i);
    }
}

杨辉三角

[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]

递推过程：f[i+1][j+1] = f[i][j] + f[i][j+1]

实际上，就是组合数：f[i][j] = Comb(i, j)

因为组合数的递推关系直接体现在杨辉三角的构造当中：Comb(n, k) = Comb(n-1, k-1) + Comb(n-1, k)

Lucas定理

Lucas定理是一个关于组合数在模p环境下的计算方法，其中p是一个素数。

Lucas 定理表述如下：

对于任何素数 $p$ 和非负整数 $n$ 和 $k$ ，组合数 $\binom{n}{k} \mod p$ 可以通过以下方式计算：

$\binom{n}{k} \mod p \equiv \prod_{i=0}^{\infty} \binom{n_i}{k_i} \pmod{p}$

其中， $n_i$ 和 $k_i$ 分别是 $n$ 和 $k$ 相对于 $p$ 的基数 $p$ 展开的系数。也就是说，
$n = n_0 + n_1p + n_2p^2 + \ldots$ 和 $k = k_0 + k_1p + k_2p^2 + \ldots$ ，其中 $n_i$ 和 $k_i$ 是小于 $p$ 的整数。

Lucas 定理特例（p = 2）

当 $p = 2$ 时，Lucas 定理用于计算 $\binom{n}{k} \mod 2$ 的值，其中 $n$ 和 $k$ 是非负整数。在这种情况下，每个数字的二进制表示中的每一位只能是 0 或 1。

对于任何非负整数 $n$ 和 $k$ ，我们有：

$\binom{n}{k} \equiv \prod_{i=0}^{\infty} \binom{n_i}{k_i} \pmod{2}$

这里， $n_i$ 和 $k_i$ 是 $n$ 和 $k$ 的二进制表示中的第 $i$ 位数字。组合数 $\binom{n_i}{k_i}$ 的值取决于：

- $\binom{0}{0} = 1$
- $\binom{1}{0} = 1$
- $\binom{0}{1} = 0$
- $\binom{1}{1} = 1$

考虑计算 $\binom{10}{5} \mod 2$ ：

- $n = 10$ 的二进制表示为 $1010_2$
- $k = 5$ 的二进制表示为 $0101_2$

根据 Lucas 定理：

$\binom{10}{5} \equiv \binom{1}{0} \cdot \binom{0}{0} \cdot \binom{1}{1} \cdot \binom{0}{1} \equiv 1 \cdot 1 \cdot 1 \cdot 0 \equiv 0 \pmod{2}$

因此， $\binom{10}{5} \mod 2 = 0$ 。这说明 Lucas 定理在 $p = 2$ 时提供了一种快速判断组合数在模 2 环境下的奇偶性的方法。

离线查询和在线查询

离线就是所有要查询的内容已经全给你了，你可以任意操作。可以按照自己定义的某种顺序回答询问，而不是按照输入顺序回答询问。
在线的意思是不知道接下来要查询的内容是什么，然后每次调用函数只给你传入一个查询参数，这种一般用在设计题里面。

bfs

在bfs过程中，如果是计算步数的话，我们常常这样写

while (!dq.isEmpty()) {
    step++;
    int sz = dq.size();
    for (int j = 0; j < sz; j++) {...}
}

注意这里sz必须是要单独用一个变量保存的，否则像下面这样，bfs过程中是由dq.offer()添加操作的，会导致步数计算错误

1	for (int j = 0; j < dq.size(); j++) {...}

但是，如果j从大到小的话，就不用担心了，因为for循环的初始化只进行一次

1	for (int j = dq.size(); j > 0; j++) {...}

离散化

题目给出的区间往往很大，直接分配数组可能会超出内存限制，所以我们需要离散化。

将所有数映射到一个连续的数字1-n，离散化主要有TreeSet和binarySearch两种方式

TreeSet方式，具体题解可以看本博客的：二维偏序

TreeSet<Integer> set = new TreeSet<>(); 
for (int i = 0; i < n; i++) {
    set.add(nums[i]);
}
int idx = 0;
Map<Integer, Integer> map = new HashMap<>();
for (Integer x : set) map.put(x, ++idx);

binarySearch方式，具体实现可以看这个题解：2926. 平衡子序列的最大和(2448)

1	int idx = Arrays.binarySearch(arr, cur) + 1; // 离散化后的坐标（从1开始）

集合论与位运算

分享｜从集合论到位运算，常见位运算技巧分类总结！

lowbit = x & -x  // 获得最低位的1，例如x = 1110，lowbit = 0010
if (x == (x & -x))  // 判断x是否只包含一个1（即2的幂次）
for (int s = j; s >= 0; s = (s-1) & j) {  // 枚举j的子集，例如j=1001，则s有1001, 1000, 0001, 0000
    if (s == 0) break;  // 需要特判下
}

模取

Java负数模取结果解析

a % b = a - (a/b)*b  // 正数负数通用公式
-8 % 7 = -8 - (-1 * 7) = -1
-8 % -7 = -8 - (1 * -7) = -1
8 % -7 = 8 - (-1 * -7) = 1

加减乘除模取

分享丨模运算的世界：当加减乘除遇上取模（模运算恒等式/费马小定理）

MOD = 1_000_000_007
// 加
(a + b) % MOD
// 减
(a - b + MOD) % MOD
// 把任意整数 a 取模到 [0,MOD-1] 中，无论 a 是正是负
(a % MOD + MOD) % MOD
// 乘（注意使用 64 位整数）
a * b % MOD
// 多个数相乘，要步步取模，防止溢出
a * b % MOD * c % MOD
// 除（MOD 是质数且 b 不是 MOD 的倍数）
a * pow(b, MOD - 2, MOD) % MOD