快速幂

LC 50 Pow(x, n)

var myPow = function(x, n) {
    let res = 1
    if(n < 0){
        x = 1/x
        n = -n
    }
    while(n){
        if(n & 1){
            res *= x
        }
        x *= x
        n >>>= 1 // 进行无符号右移1位，此处不能使用有符号右移（>>）
    }
    return res
};

并查集

//初始化集合，i表示每个集合的编号，arr[i]表示集合i的父节点
for(let i = 1; i <= n; i++){
    arr[i] = i
}
// 查询某个点所在的集合，当该集合的arr[i]等于它自己，则说明是根节点
const find = (x) =>{
    if(arr[x] !== x){ 
        arr[x] = find(arr[x])
    }
    return arr[x]
}
// 合并两个集合
const merge = (a, b) =>{
    if(arr[find(a)] !== arr[find(b)]){
        arr[find(a)] = find(b)
    }
}

最大公约数gcd

const gcd = (a, b) =>{
    return b ? gcd(b, a % b) : a
}

KMP

如何更好的理解KMP-知乎回答

KMP算法的时间复杂度O(N+M)的。对于原字符串s和匹配串p，对应的索引是i和j+1（即i, j之间错一位）。

// 注意，s和p的idx都是从1开始，为了后面好计算，前面多加个空子串占位。
s = ' ' + s
p = ' ' + p
const ne = new Array(N+1).fill(0) // 初始化为0

// 只有字符串长度大于1的时候，才会存在非平凡前后缀。next[1]的值固定是0
// 求next数组，注意这里i是从2开始。
for(let i = 2, j = 0; i <= n; i++){
    while (j && p[i] !== p[j + 1]) j = ne[j]
    if (p[i] === p[j + 1]) j++
    ne[i] = j
}

// 匹配过程，这里i从1开始。
for(let i = 1, j = 0; i <= n; i++)
{
    while(j && s[i] != p[j + 1]) j = ne[j];
    if(s[i] == p[j + 1]) j++; //当前元素匹配，j移向p串下一位
    if(j == m)
    {
        //匹配成功，进行相关操作
        j = next[j];  //继续匹配下一个子串
    }
}