快速幂

快速幂算法用于处理大数问题，由于一般Number类型的精度无法处理过大的数字，所以对幂乘操作进行优化，用时间换精度的解决方案
快速幂算法复杂度：

  • 时间复杂度：O(log n)

快速幂算法使用场景：
用于对某个数做大数幂乘，幂乘过大导致超过精度范围，一般包括两个参数(base,exp)

快速幂问题解题思路：

  1. 将指数部分拆解为多个幂次的和
    比如 $3^{13}$ ,我们可以将其拆解为 $3^1*3^4*3^8$，为什么这么拆？从二进制角度考虑13 = 1101
  2. 基数和幂次的转化
    通过基数base和幂次exp之间的转化逐步累积结果，即根据幂次的特性，每次exp/2可以等价互换base*base
  3. 通过前两步累积有贡献的位次
    我们设定res初始值为1，那么通过每次循环exp = Math.floor(exp / 2)，检查最低位为1，并计入结果res = (res*base) % MOD，同时更新base的值为base = (base * base) % MOD
    以$3^{13}$为例，快速幂乘从低位到高位逐步处理：
    • $3^1$对应最低位1，base对应$2^0$部分 => 有贡献,res*=base
    • $3^2$对应次低位0，base对应$2^1$部分 => 无贡献
    • $3^4$对应次低位1，base对应$2^2$部分 => 有贡献,res*=base
    • $3^8$对应次低位1，base对应$2^3$部分 => 有贡献,res*=base
    • 结果即$3^{13} = 3^1*3^4*3^8$

javascript下的具体样例：

点击查看具体代码 
1
2
3
4
5
6
7
8
9
10
11
12
function fastPower(base, exp) {
    let res = BigInt(1);
    base = BigInt(base);
    while (exp > 0) {
        if (exp % 2 === 1) {            // 如果指数是奇数，累积乘法
            res = (res * base) % MOD;
        }
        base = (base * base) % MOD;     // 基数平方并取模
        exp = Math.floor(exp / 2);      // 指数减半
    }
    return res;                         // 返回结果
}

滑动窗口

滑动窗口算法一般用于处理数组或字符串的子串问题，其核心思路为寻找符合条件的子串，后在其基础上进行延申，即维护一个字串窗口

滑动窗口算法复杂度：

  • 时间复杂度：O(n)~O(n^2)视情况而定

滑动窗口算法使用场景：
该算法一般用于寻找符合条件的字串数量问题上，并且需要格外注意的一点是该算法下要求的字串必须是连续字串
另外，滑动窗口的使用场景一般还与双指针有一定的互补性：

  • 双指针：双指针算法的左右指针一般处于数组两端，在次基础上压缩找阈限值/极值
  • 滑动窗口：滑动窗口的左右边界则都从起点开始，找到阈限后在此基础上延申，包括寻找满足条件的字串或元素数量、字符串匹配等

滑动窗口一般解题步骤：

  1. 遍历拓展右边界：右边界遍历整串数组，逐步拓展窗口
  2. 根据条件压缩左边界：左边界根据场景条件逐步追赶右边界，并确保窗口内数组符合场景条件
  3. 实时比较和更新不断比较窗口和中间值，直到遍历完整串数组后找出结果

具体样例：

点击查看具体样例 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var lengthOfLongestSubstring = function(s) {
    let mySet = new Set();
    let left = 0;
    let maxLength = 0;

    // 右边界遍历数组
    for (let right = 0; right < s.length; right++) {  
        // 根据场景条件移动左边界
        while (mySet.has(s[right])) {
            mySet.delete(s[left]);
            left++;
        }
        mySet.add(s[right]);

        // 判断终值
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
};

哈希表

哈希表的键值对模式可以直接映射键值关系，同时哈希表中查找数据的代价很低，因此哈希表相关算法通过反复添加记录并查找已有记录的方式确定结果，值得一提的是，有些题目的键值对关系非常直观，可以一眼看出，但大部分问题的键值对需要对题设做一定变换，而往往找到这层变换才是难点所在

哈希表算法复杂度：

  • 时间复杂度：O(n)

哈希表算法使用场景：
该算法一般用于需要大量对现有值或关系进行查找或变化的场景，或者需要查看数据之间联系紧密的场景，比如寻找拥有相同规律的数或者拥有相同字符的字符串等，包括：

  1. 频繁查找场景：如缓存机制、寻找重复元素等
  2. 数据分组和分类：如字符串异位问题
  3. 快速匹配问题：如寻找特定数字对

哈希表一般解题步骤：

  1. 分析相关性：找到需要记录的数据之间的相关性
  2. 构建哈希表：遍历数组，根据相关性设置哈希表
  3. 实时更新与查询：根据键值关系实时修改数据，记录结果

冲突处理：

  1. 链地址法：哈希表核心是键值对的设立，当键值冲突时后者会覆盖前者，此时通过链表或数组存储键对应的值来处理冲突
  2. 开放地址法：通过查找当前位置前后的空位来解决冲突
具体样例 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    let res = []
    let map1 = new Map()

    for(let i of strs){
        let tmp = i.split('').sort().join('')   // 对字符串排序设置键值
        if(map1.has(tmp)){
            map1.get(tmp).push(i)    // 构建哈希表
        }
        else
            map1.set(tmp,[i])
    }

    return Array.from(map1.values());
};