快速幂

快速幂算法用于处理大数问题，由于一般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());
};

图论（DFS）

图论相关算法一般用于解决指向性明确的二维地图相关问题，其中最基本的两个搜索算法分别是，DFS深度优先搜索——递归遍历所有节点，BFS广度优先搜索——找到具有相同特性的节点扩散遍历所有节点，两者的使用区别在于特殊节点之间是否存在某种共性，来决定是递归遍历还是扩散遍历，本节优先考虑DFS算法

DFS算法复杂度：

  • 时间复杂度：O(mn)

DFS算法使用场景：

  1. 连通性检测：递归遍历来检测节点之间的连通性
  2. 检测环的存在：通过递归能够检测遍及的节点中是否存在环
  3. 图像分割：将整张图像中的区块按照某种规则进行划分

DFS算法解题思路：
核心思想：DFS算法核心目的在于图的遍历，因此，核心思想就是找临界条件，避免节点的重复访问

  1. 遍历二维图：从某一节点出发，dfs遍历所有节点
  2. 确定终止条件：根据题目要求确定临界条件，作为递归终止符
  3. 节点标记：对遍历过的节点做标记防止重复遍历
  4. 向不同方向遍历：逐渐拓展当前节点，递归遍历

具体样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
var numIslands = function(grid) {
    let m = grid.length
    let n = grid[0].length
    let res = 0

// dfs遍历
    function dfs(x,y){
        // 确定终止条件
        if(x<0||x>=m || y<0 || y>n ||grid[x][y] !== '1'){
            return
        }

        // 标记现有节点，防止重复遍历
        grid[x][y] = '2'

        // 逐渐递归拓展节点
        dfs(x-1,y)
        dfs(x+1,y)
        dfs(x,y-1)
        dfs(x,y+1)

        return
    }

// 遍历全图
    for(let i = 0;i<m;i++){
        for(let j = 0;j<n;j++){
            if(grid[i][j] === '1'){
                res++;
                dfs(i,j)
            }
        }
    }

    return res
};

图论（BFS）

上面讲了DFS深度优先搜索，接下来讲讲BFS广度优先搜索，BFS是一种层次遍历算法，可以看作是对特异点进行“传染”来进行全图遍历的一种手段

BFS算法复杂度：

  • 时间复杂度：O(mn)

BFS使用场景：

  1. 最短路径问题：因为BFS是基于“特异点”的扩散，因此可以追踪每一步从而找到最短路径
  2. 层次遍历：通过逐层扩散遍历来达到层次遍历的效果

BFS一般解题步骤：

  1. 确定初始特异点：根据题意确定初始特异点，通过维护一个队列来存储这些特异点
  2. 层次扩散：确定扩散方向，对第一步确定的特异点进行扩散
  3. 条件追踪：如果需要记录层次等需求，可以设置一个额外参数进行条件追踪

具体样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
var orangesRotting = function(grid) {
    let m = grid.length
    let n = grid[0].length
    let queue = []

    // 确定最先的特异点
    for(let i = 0;i<m;i++){
        for(let j = 0;j<n;j++){
            if(grid[i][j] === 2)queue.push([i,j,0])
        }
    }

    // 确定遍历方向
    let res = 0
    let direction = [[-1,0],[1,0],[0,1],[0,-1]]

    // 遍历特异点，维护一个参数来记录层次
    for(let [i,j,t] of queue){
        for(let [x,y] of direction){
            if(i+x >=0 && i+x<m && j+y>=0 && j+y <n &&  grid[i+x][j+y] === 1){
                //逐渐扩散
                queue.push([i+x,y+j,t+1])
                grid[i+x][j+y] = 2
                res = Math.max(t+1,res)
                
            } 
            
        }
    }

    for(let i = 0;i<m;i++){
        for(let j = 0;j<n;j++){
            if(grid[i][j] === 1)res = -1
        }
    }
    // 获取最深层次
    return res
};