算法模板

持续更新中…

1.二分查找

// 找到大于等于目标数的第一个位置
public int lower_bound(int[] nums, int target) {
    int low = 0, high = nums.length - 1;
    while (low < high) {
        int mid = (high - low) / 2 + low;
        if (nums[mid] < target) {
            low = mid + 1; 
        } else {
            high = mid;
        }
    }
    return low;
}

// 找到大于目标数的第一个位置
public static int upper_bound(int[] nums, int target) {
    int low = 0, high = nums.length - 1;
    while (low < high) {
        int mid = (high - low) / 2 + low;
        // System.out.println(mid);
        if (nums[mid] <= target) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

2.并查集

class UF {
    int[] p, r;
    int setCount;

    public UF(int n) {
        this.setCount = n;
        this.p = new int[n];
        this.r = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = i;
            r[i] = 1;
        }
    }

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

    public boolean merge(int x, int y) {
        int xx = find(x), yy = find(y);
        if (xx == yy) return false;
        if (r[xx] >= r[yy]) {
            p[yy] = xx;
            r[xx] += (r[xx] - r[yy]);
        } else {
            r[xx] = yy;
        }
        setCount--;
        return true;
    }
}

3.约瑟夫环递推公式

f(n, k) = (f(n-1, k) + k) % n; // n, k 时最后剩余的编号
f(1, k) = 0; // 递归结束

int find(int n, int k) {
    if (n == 1) return 0;
    return (find(n - 1, k) + k) % n;
}

4.Trie：前缀树（字典树）

class Trie{
    // 表示当前字母后面的字母
    private Trie[] children;
    private boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }

    public void insert(String word) {
        Trie node = this; // 根结点
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        // 新插入时最后一个字母节点的isEnd为true
        node.isEnd = true;
    }

    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private Trie searchPrefix(String prefix) {
        Trie node = this;
        for (int i = 0 ;i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            // 无当前字符
            if (node.children[index] == null) {
                return null;
            }
            node = node.children[index];
        }
        return node;
    }
}

5.判断回文串预处理

// i 和 j之间的字符串是否是回文串
boolean[][] dp = new boolean[n][n];
// 必须初始化
for (int i = 0; i < n; i++) Arrays.fill(f[i], true);
// 注意 i 从 n-1 开始，否则状态重复，计算结果错误
for (int i = n - 1; i >= 0; i--) {    
    for (int j = i + 1; j < n; j++) {        
        dp[i][j] = (s.charAt(i) == s.charAt(j)) && dp[i + 1][j - 1];    
    }
}

6.快速幂-求拟元

mod为质数，则i 的逆元就是$\frac{1}{i}=i^{mod-2}\% mod$

用快速幂求$i^{mod-2}$，算法时间复杂度为$O(logN)$

static final int MOD = 998244353;
static long quick_pow(long a, long b) {    
    long ret = 1;    
    // if(b < 0){   
    //     b = -b;    
    //     a = 1 / a;    
    // }    
    while (b > 0){        
        if ((b & 1) == 1) ret = ret * a % MOD;        
        a = a * a % MOD;        
        b >>= 1;  // b /= 2;    
    }    
    return ret % MOD;
}

// 快速求拟元
inv(i) = quick_pow(i, MOD-2) % MOD;

7.计算组合数模板

$C_{a}^{b} = \frac{a!}{(a - b)!\ b!}$

static final int MOD = 998244353;
static final int N = (int) 1e5 + 6;
static long[] fact = new long[N]; 
//  存储阶乘
static long[] inFact = new long[N]; 
// 存储阶乘逆元
static long quick_pow(long a, long b) {    
    long ret = 1;    
    while (b > 0){        
        if ((b & 1) == 1) ret = ret * a % MOD;        
        a = a * a % MOD;       
        b >>= 1; // b /= 2;    
    }    
    return ret % MOD;
}

static long comb(int a, int b) {    
    // 初始化    fact[0] = inFact[0] = 1;    
    for (int i = 1; i < N; i++) {        
        fact[i] = fact[i - 1] * i % MOD;        
        inFact[i] = inFact[i - 1] * quick_pow(i, MOD - 2) % MOD;    
    }    
    return fact[a] * inFact[a - b] % MOD * inFact[b] % MOD;
}

// 预处理小范围组合数
long[][] comb = new long[2010][2010];
int MOD = (int) 1e9 + 7;
comb[0][0] = 1; // 初始化
for (int i = 1; i < 2010; i++) {
    comb[i][0] = 1;
    for (int j = 1; j < 2010; j++) {
        comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % MOD;
    }
}

8.树状数组

// 单点修改，区间求和
class BIT {
    int[] arr;
    
    public BIT(int n) {
        this.arr = new int[n + 10];
    }
    
    public int lowbit(int x) {
        return -x & x;
    }
    
    public void add(int x, int val) {
        while (x < arr.length) {
            arr[x] += val;
            x += lowbit(x);
        }
    }
    
    public int query(int x) {
        int res = 0;
        while (x > 0) {
            res += arr[x];
            x -= lowbit(x);
        }
        return res;
    }
}

// 单点修改，区间求最大值
class BIT {
    int[] arr; // 记录数值
    int[] max; // 记录最大值
    
    public BIT(int n) {
        this.arr = new int[n + 10];
        this.max = new int[n + 10];
    }
    
    public int lowbit(int x) {
        return -x & x;
    }
    
    public void update(int x, int val) {
        arr[x] = val; // 单点更新
        while (x < arr.length) {
            max[x] = arr[x];
            int lx = lowbit(x);
            for (int i = 1; i < lx; i <<= 1) {
                max[x] = Math.max(max[x], max[x - i]);
            }
            x += lowbit(x);
        }
    }
    
    public int query(int l, int r) {
        int ans = 0;
        while (l <= r) {
            ans = Math.max(ans, arr[r--]);
            while (r - lowbit(r) >= l) {
                ans = Math.max(ans, max[r]);
                r -= lowbit(r);
            }
        }
        return ans;
    }
}

9.线段树（待简化）

int N = (int) 1e5 + 10;
int[] tree = new int [N]; // 线段树
int[] arr = new int[N]; // 被管理的数组
int size;

// 递归建树：node：树中节点编号
public static void build(int node, int start, int end) {
    if (start == end) {
        tree[node] = arr[start];
    } else {
        int mid = (start + end) / 2;
        int left_node = 2 * node + 1;
        int right_node = 2 * node + 2;
        build(left_node, start, mid);
        build(right_node, mid + 1, end);
        tree[node] = tree[left_node] + tree[right_node];
    }
} 

// 更新单个值
public static void update(int node, int start, int end, int idx, int val) {
    if (start == end) {
        arr[idx] = val;
        tree[node] = val;
    } else {
        int mid = (start + end) / 2;
        int left_node = 2 * node + 1;
        int right_node = 2 * node + 2;
        if (idx >= start && idx <= mid) {
            update(left_node, start, mid, idx, val);
        } else {
            update(right_node, mid + 1, end, idx, val);
        }
        tree[node] = tree[left_node] + tree[right_node];
    }
}

// 区间求和
public static int query(int node, int start, int end, int L, int R) {
    if (R < start || L > end) {
        return 0;
    } else if (L <= start && end <= R) {
        return tree[node];
    } else if (start == end) {
        return tree[node];
    } else {
        int mid = (start + end) / 2;
        int left_node = 2 * node + 1;
        int right_node = 2 * node + 2;
        return query(left_node, start, mid, L, R) + query(right_node, mid + 1, end, L, R);
    }
}

10.最大公约数：GCD

public int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

11.马拉车算法（Manacher’s Algorithm)

用来查找字符串中最长回文串的线性方法。

总体时间复杂度：$O(n)$

// 生成新的辅助String, eg: abc123成为#a#b#c#1#2#3#2#1#
public static char[] manacherStringString(String str) {
    char[] c = str.toCharArray();
    char[] res = new char[c.length * 2 + 1];
    int index = 0;
    for (int i = 0; i != res.length; i++) {
        // 两个一样效果, 填充符号"#"
        res[i] = (i % 2) == 0 ? '#' : c[index++];
        // res[i] = (i & 1) == 0 ? '#' : c[index++];
    }
    return res;
}

// 返回最长回文串长度
public static int maxLcpsLength(String str) {
    if (str == null || str.length() == 0) {
        return 0;
    }
    char[] charArr = manacherStringString(str);
    // 辅助回文长度数组, pArr[i]表示以当前点为对称中心的最大回文串长度
    int[] pArr = new int[charArr.length];
    // 中心点
    int C = -1;
    // 最右边界
    int R = -1;
    int max = Integer.MIN_VALUE;
    for (int i = 0; i != charArr.length; i++) {
        // i在右边界内, i`到C的长度和到i到R的距离, 哪个小, 哪个就是起码成为回文的区域
        // 否则为1, 自身
        pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
        // 检查边界
        while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
            if (charArr[i + pArr[i]] == charArr[i - pArr[i]]) {
                // 左右字母相等, 扩1, 直到不能扩为止
                pArr[i]++;
            } else {
                // 不能扩
                break;
            }
        }
        // 如果大于R, 那更新回文右边界和中心点
        if ((i + pArr[i]) > R) {
            R = i + pArr[i];
            C = i;
        }
        // 记录最佳中心点: 如果要返回字符串可以用
        // if(pArr[i] > max) best_center = C / 2;
        
        // 如果需要, 则更新max
        max = Math.max(max, pArr[i]);
    }
    // 返回最大回文长度
    return max - 1;
}

12.循环数组索引加减变化

// offset_index 可正可负
index = ((now_index + index_offset) % n + n) % n;

13.最长上升子序列(LIS)

public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n + 10];
    int pos = 0;
    for (int i : nums) {
        int l = 0, r = pos;
        while (l < r) {
            int mid = (r - l) / 2 + l;
            // 找到 nums[i] 大于的第一个数的位置
            // if(dp[mid] <= i){ // 最长非降子序列
            if (dp[mid] < i) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        dp[l] = i;
        if (l == pos) pos++;
    }
    return pos;
}

14.KMP算法：在字符串中查找子串

15.随机打乱数组

static final Random random = new Random();
static void shuffleSort(int[] a) {
    int n = a.length;//shuffle, then sort 
    for (int i = 0; i < n; i++) {
        int oi = random.nextInt(n), temp = a[oi];
        a[oi] = a[i]; 
        a[i] = temp;
    }
    // Arrays.sort(a);
}

16.质因数分解

public List<Integer> get(int n) {
    List<Integer> res = new ArrayList<>();
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0) n /= i;
            res.add(i);
        }
    }
    if (n != 1) res.add(n);
    return res;
}

17.下一个排列

public int[] nextPermutation(int[] arr) {
    int[] res = arr.clone();
    // 从后往前找到满足res[k] < res[k + 1]的位置
    int k = -1;
    for (int i = arr.length - 2; i >= 0; i--) {
        if (arr[i] < arr[i + 1]) {
            k = i;
            break;
        }
    }
    if (k == -1) {
        // 完全是降序的，已经是最大的排列了，下一个排列就是最小的排列，直接反转即可
        reverse(res, 0, arr.length - 1);
        return res;
    }
    // 从后往前找到第一个满足arr[t] > arr[k]的位置
    int t = -1;
    for (int i = arr.length - 1; i >= 0; i--) {
        if (arr[i] > arr[k]) {
            t = i;
            break;
        }
    }
    // 交换arr[t],arr[k]
    int tmp = res[k];
    res[k] = res[t];
    res[t] = tmp;
    // 反转k后边的数组
    reverse(res, k + 1, arr.length - 1);
    return res;
}

public void reverse(int[] arr, int l, int r) {
    while (l < r) {
        int t = arr[l];
        arr[l] = arr[r];
        arr[r] = t;
        l++;
        r--;
    }
}